Notesdistributed🌱 seedling
Lamport Clock
Also: Lamport Timestamp · Logical Clock · Logical Timestamp
One integer counter per process, incremented before each event and carried on every message; a receiver jumps to max(own, received) + 1. If a happened before b then L(a) < L(b), but not the reverse.
Why it exists
To order events consistently with causality using no synchronized time at all.
How it works
- Rule 1: increment the counter before every event and stamp the event with it.
- Rule 2: send the counter with each message; on receipt set counter = max(own, received) + 1.
- Clock condition: a → b ⇒ L(a) < L(b).
- Total order: sort by (counter, process ID). Every node computes the same order, consistent with causality.
- Limits: L(a) < L(b) is compatible with a ∥ b, so it can't detect concurrency. And the total order is only known after collecting timestamps from everyone, which is too late for decisions like "who claimed this username first".
Trade-offs
| Gains | Costs |
|---|---|
| tiny: one integer per message | can't tell causal order from concurrency |
| no clock synchronization | numbers unrelated to wall time; can't query "as of 10:00" |
| total order for free | that order is only final after hearing from every node |
In practice
- The original use (1978) was a distributed mutual-exclusion algorithm: every process orders lock requests by timestamp.
- Raft terms and Kafka epochs are Lamport-style counters: monotonic numbers that let nodes recognize stale messages.
Pitfalls
- Reading L(a) < L(b) as "a caused b".
- Using it where real-time order matters (two users with no shared channel); see TrueTime.
Connections
- Contains
- Hybrid Logical Clock
- Contrasts with
- Vector Clock
- Mentioned
- TrueTime
Recall
These cards are also in your review deck, scheduled with spaced repetition.