Module 13 · Distributed fundamentals · Lesson 9 of 18
Lamport timestamps
The simplest logical clock: one counter per process, bumped on every event and on every message. The two rules, how (counter, node id) yields a total order every node agrees on, what it guarantees and what it cannot tell you.
The video walkthrough is part of Pro.
See what Pro includesWhy it matters
Lamport's 1978 paper gave distributed systems their first clock that did not lie: a counter that is guaranteed to be smaller for a cause than for its effect. It is tiny (one integer), cheap to carry on every message, and still the mechanism behind consistent ordering of writes, logs and operations in many systems. Knowing its two rules and its one limitation is a standard interview check.
The idea
Each process keeps an integer counter, its Lamport clock, starting at zero.
- 1
Rule 1: local events
Before any local event (including sending a message), increment the counter. The event's timestamp is the new value. - 2
Rule 2: receiving a message
The message carries the sender's timestamp. On receipt, set the counter to max(own counter, received timestamp) + 1, and that is the receive event's timestamp.
With these rules, if event A happens before event B, then L(A) is less than L(B): along a chain of local steps and messages the counter strictly increases. That is the guarantee.
A total order everyone agrees on
Two concurrent events can have the same counter. Break ties with the process id: order events by (counter, id). Every node computing this order from the same set of timestamps gets the same answer, so Lamport timestamps give a total order of all events in the system that is consistent with causality. That is enough to build a replicated log where all replicas apply operations in the same sequence, a distributed mutual exclusion algorithm where the lowest timestamp request gets the lock, or a deterministic winner for concurrent writes that is at least not dependent on clock skew.
What it cannot tell you
The implication runs one way only. L(A) less than L(B) does not mean A caused B: in the diagram, P3's event with timestamp 1 is concurrent with everything on P1, yet it sorts before P1's event stamped 2. So a Lamport timestamp cannot detect conflicts. If two replicas hold versions with timestamps 7 and 9, you know 9 did not happen before 7, but you cannot tell whether 7 happened before 9 (safe to overwrite) or they were concurrent (a conflict to surface). For that you need vector clocks, next lesson.
| Question | Lamport answer |
|---|---|
| Did A happen before B? | If L(A) ≥ L(B), definitely not. If L(A) < L(B), maybe |
| Are A and B concurrent? | Cannot tell |
| Give me one order all nodes agree on | Yes: sort by (counter, node id) |
| How big is the timestamp? | One integer, regardless of cluster size |
Where it is used
Ordering operations in replicated state machines and logs; timestamps for versioned writes in some key-value stores where a deterministic winner suffices; distributed mutual exclusion (Lamport's own algorithm and Ricart-Agrawala); ordering messages in chat and collaboration systems so all participants render the same sequence; and as the counter component inside hybrid logical clocks, which combine a physical timestamp with a Lamport-style counter to stay close to wall time while preserving causality.