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. So Lamport timestamps can confirm causality but cannot detect its absence, which 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.