Logical Clocks

Posted on
Reading time 3

This is a great presentation.

Logical clocks are used to agree on order in which events occur. The absolute/real time is not important in this concept.

Event ordering can be based on any number of factors. In a local system, CPU time can be used. But in a distributed system, there is no perfectly synchronized time or clock that can be used, and local times may not be in sync (and probably are not). Lamport suggested a logical clock be used to address this.

Key concepts

  • Processes exchange messages
  • Message must be sent before received
  • Send/receive used to order events and synchronize logical clocks

Properties

  • If A happens before B in the same process (or system), then A -> B
  • A -> B also means that A sent the message and B means the receipt of it
  • Relation is transitive: e.g A -> B and B -> C implies A -> C
  • Unordered events are concurrent: A !-> B and B !-> A implies A || B

Lamport’s Logical Clocks

  • If A -> B then timestamp(A) < timestamp(B)

Lamport’s Algorithm

diagram image

Note: A -> B implies L(A) < L(B), but L(A) < L(B) does not necessarily imply A -> B. In other words, A -> B implies that the logical clock of A is less than that of B, but the logical clock of A being less than that of B does not imply that A -> B.

Totally Ordered Multicast

Example: We have a large distributed database. We need to make sure that replications are seen in the same order in all replicas. This requires us to cast the replicas to all systems in an absolutely total order.

Example Situation: The following events occur:

  • A) We have $1000 in a bank account.
  • B) We add $100
  • C) We calculate 1% interest on the balance.

If the order is ABC, then the 1% interest will be $1100 * 0.01 = $11. But if the order is ACB, then the interest will be $1000 * 0.01 = $10. In this case, the order matters as the interest is different.

Lamport’s logical clocks can be applied to implement a totally‐ordered multicast in a distributed system.

Implementation

Assumptions:

  • No messages are lost
  • Messages from the same sender are received in the same order as they were sent

Process P(i) will send out a message M(i) to all others with timestamp T(i). An incoming message is queued according to it’s timestamp. P(i) will pass a message to its own application if it meets 2 criteria: the message is at the head of the queue, the message has been acked by all other processes.

diagram image

All processes will end up with the same messages with the same timestamps, so order can be sorted out locally and therefore all messages are delivered in the same order.