Lamport Clocks

Back in the late 1970's Leslie Lamport wrote a paper in which he introduced logical clocks. The paper had three main points: firstly, if a distributed system is built up of multiple independent servers, and some of the servers never interact with each other, then there is little theotical need for the non-interacting server clocks to be sychronised since any difference would never be observed. Secondly, in distributed systems, he showed that time is less important than agreement across components of the order of events in which things occur. And finally, he provided algorithms for partial causal ordering and an extension which provides total ordering.

Lamport clocks are event counters that are incremented with every interaction. They are incremented and sent as a part of a message by a sending process and are in turn incremented by a receiving process before it sends it on to the business logic. The value produced by a Lamport clock is a Lamport timestamp.

A Lamport clock offers us a single guarantee – if we have two timestamp values a and b, and when comparing them we see that a < b, then we can guarantee that the clock value of a was smaller than the clock value of b. When different processes have a < b, it means that they all agree that a happened before b.

Adding a Lamport timestamp on the sending side can be done by:

long time = 0;
...
void send(byte[] message)
{
    time = time + 1;
    send(message, time);
}

And on the receiving side it is:

long time = 0;
...
void receive(byte[] message, long timeStamp)
{
    time = max(timeStamp, time) + 1;
    //do stuff with message and new time
    process(message, time);
}

Visually, the behavior of Lamport Clocks is as follows:

The above example illustrates how Lamport Clocks can give ordering to the causal event flows Event C -> Event D and Event A -> Event B -> Event E within the process space of Process A. Note that we cannot say anything about Event A causing Event C. It also shows how Lamport Clocks may result in duplicate clock values across processes, and how clock values cannot be taken to be reliable representative of the real-world happend before.

Lamport Clocks can be extended to provide total ordering with multiple processes. In this case, you will need to introduce a tie breaker value such as a derived process identifier, and have each process hold two values - the Lamport timestamp value (timestamp) and process identifier (id). The process identifier could be constructed from a process specific value such as an IP address. If we consider two processes, m and n: (m.Timestamp, m) < (n.Timestamp, n) then we have total ordering if and only if m.Timestamp<n.Timestamp or (m.Timestamp=n.Timestamp and m<n). Note this does not necessarily relate to actual event ordering.

Lamport clocks cannot tell us if a message was concurrent, and cannot be used to infer causality between events. Vector clocks are a more sophisticated variant which gives us more guarantees, including knowledge of concurrency & causal history.

---

Backlinks

---

References

---

Change log

• Added 11 December 2020