Lamport Clock

A Lamport clock is a counter maintained by each process in a distributed system, used to order events without relying on physical time. Leslie Lamport introduced it in a 1978 paper that remains the standard reference for reasoning about order in distributed systems.

The paper first defines the happened before relation from what a system can actually observe: one event precedes another if both occur in the same process in that order, or if one is the sending of a message and the other is its receipt, plus transitivity. Events not related in either way are concurrent — a structural statement about information flow rather than about wall-clock simultaneity.

The clock implements that relation with two rules. Each process increments its counter between events. Every message carries the sender’s counter, and on receipt the recipient sets its own counter to more than the larger of its current value and the received one. The result is that if one event happened before another, its counter is smaller.

The limitation is the converse, and it is the part most often missed. A smaller counter does not imply happened-before: two concurrent events can have any counters at all. Concurrent events can also have equal counters: two processes can each record their first event as 1. To extend the causal partial order to a total order, compare the counter and then break ties using a fixed ordering of process identifiers. That chooses an order for concurrent events rather than discovering their physical order. Counter values cannot be read backwards: seeing that one timestamp is smaller than another tells you only that the second did not happen before the first — the two may be causally related or merely concurrent. That is why vector clocks exist for cases where distinguishing concurrent from ordered actually matters.

The durable lesson is broader than the mechanism. Order in a distributed system is only definable through information that actually flowed between the parts, so events from two systems that never communicated are concurrent in Lamport’s sense no matter what their timestamps say — which is precisely the problem when merging streams from separate sources.

How this compares to approaches that quantify physical clock error instead, such as TrueTime, is worked through in Replication, Consistency, and Time.

References

• Leslie Lamport, Time, Clocks, and the Ordering of Events in a Distributed System (1978)