Partial Ordering with Lamport and Vector Clocks

One computer is precise, a million are merely accurate.

This is from the series of entries covering topics of note from PyCon 2015. More articles from this series can be found here.

This entry covers only a portion of topics from a talk given by @lvh. A video can be seen here.

Lamport Clocks

Lamport timestamps are a mechanism by which distributed systems can achieve partial ordering of events. Perfect time synchronization is not possible in a distributed system. In reality and from experience with modern technology, it is possible to compare events within seconds in a distributed system. However events within large systems often happen many millions of times per second and as messages move between nodes it is important to know ordering of events in order to choose logic branches.

Lamport clocks work as follows. Each process in a distributed system (P1, P2, P3...) maintains a counter of operations. Upon communicating an operation with another process, the source of the communication sends the current counter from its sequential clock along with the message. If the clock of the receiving system is behind (less than) that of the sending system, it will jump forward to the received counter.

Lamport clocks guarantee:

A --> B iff C(A) < C(B)

read: Event A happened before event B if and only if the clock at event A is less than the clock at event B.

A more precise understanding might be with C(A) < C(B), A may have happened before B or be incomparable with B, but A did not happen after B

Consider the following example. Three processes keeping Lamport clocks on their events. Periodically, some processes sync with others. The letters on the event indicate the perceived order for each process. The numbers are the current Lamport timestamps.

Lamport timeline

The above sequence guarantees the following.

  1. P1-A --> P2-B as 1 < 2
  2. P2-A --> P2-B as 1 < 3
  3. P3-B --> P3-B as 2 < 3
  4. P3-C --> P2-B as 3 < 6

However, as important is the information that cannot be gleaned from the Lamport timestamps.

  1. We do not know if P1-A or P3-A occurred first or they were concurrent.
  2. We do not know if P2-A or P3-A occurred first or they were concurrent.
  3. We do not know if P1-C or P2-B occurred first or they were concurrent.

Vector Clocks

Vector clocks are a more complex idea on top of that supplied by Lamport clocks. Instead of each process storing only its own timestamp, each process stores a vector of timestamps. The length of the vector is the number of processes in a distributed system which need to share a synchronized clock or in other words the number of process in the system which need to determine order of communication with one another. Each process also knows its own timestamp's position in the vector.

Vector clocks are subject to the following rules:

  1. Each time a process experiences an event is increments its own clock in the vector clock by one.
  2. Each time a process sends a message it sends the entire vector clock (after the increment in rule 1).
  3. Each time a process receives a message, it increments its own timestamp in the vector by one and sets all other timestamps in the vector to the maximum of the value for each node in its own vector clock or in the received vector clock.

Given the distributed system using vector clocks it is possible to determine the following about any two events A and B:

  • If all of the timestamps in the vector for event A are less than for equal to those in the vector for event B and at least one timestamp in the vector for event A is strictly less than that for event B, the two events were not concurrent and event A occurred before event B.
  • If all of the time stands in the vector for event A are greater than or equal to those in the vector for event B and at least one timestamps in the vector for event A is strictly larger than that for event B, the two events were not concurrent and event A occurred after event B.
  • If the vector clock for event A contains a mix of timestamps some of which are greater than and some of which are less than and possibly some of which are equal to those for event B, the events are considered concurrent and we cannot determine the order thereof.

Consider the following example. Three processes keeping vector clocks on their events. The example is centered around event P2-D.

Vector timeline

The above guarantees the following in comparison to event P2-D:

  • Events P1-A, P1-B, P2-A, P2-B, P2-C, P3-A were not concurrent with and occurred before event P2-D.
  • Events P1-D, P2-E, P3-D, P3-E were not concurrent with and occurred after event P2-D.
  • No determination can be made with events P3-B, P3-C and P2-D and as such they are considered concurrent.

Why is this necessary?

Because distributed systems usually take requests or interact as a single entity it is necessary for them to make coordinated decisions. Often the order of events is important in race conditions and authoritative selection of an element.

Creative Commons image used for banner. Image credit: halfrain@