Key Question
How can we assign timestamps to events that capture the happened-before relation without using physical clocks?
Deep Dive
Leslie Lamport’s 1978 paper introduced not just the happened-before relation, but also a simple algorithm for capturing it numerically: Lamport clocks. The idea is to replace physical timestamps with logical counters that track causal relationships. Each process maintains a counter, and the counters are updated using a small set of rules that mirror the happened-before relation.
The algorithm uses four rules for each process:
- Initialize: Each process maintains a counter Ci, initially set to 0.
- Local event: Before executing any local event, Ci = Ci + 1.
- Send: Before sending a message, Ci = Ci + 1, then include Ci as the timestamp in the message.
- Receive: On receiving a message with timestamp T, Ci = max(Ci, T) + 1.
The key insight is rule 4. When a process receives a message, it does not simply increment its counter. It takes the maximum of its own counter and the incoming timestamp, then adds one. This ensures the receiver’s clock advances to a value that is causally “after” the sender’s timestamp — regardless of which counter was higher.
Let us walk through a complete example with two processes:
Process A Counter A Process B Counter B
| 0 | 0
a1 (local) 1 |
| |
a2 (send, ts=1) ────────────────→
| 2 b1 (receive, ts=1)
a3 (local) 3 | max(C_B, 1) + 1 = max(0,1) + 1 = 2
| b2 (local) 3
| b3 (send, ts=3)
a4 (receive, ts=3) |
| max(C_A, 3) + 1 = 4 b4 (local) 4
a5 (local) 5 |Step-by-step walkthrough:
- Both counters start at 0.
- A performs local event a1: counter goes to 1.
- A sends a message: counter goes to 2. The message timestamp is 2.
- B receives the message: B’s counter is 0, message timestamp is 2. max(0, 2) + 1 = 3. B’s counter becomes 3. (Note: the receive event itself gets timestamp 3.)
- B performs local event b2: counter goes to 4.
- B sends a message: counter goes to 5. Message timestamp is 5.
- A receives the message: A’s counter is 2, message timestamp is 5. max(2, 5) + 1 = 6. A’s counter becomes 6.
- A performs local event a5: counter goes to 7.
Now let us verify the happened-before relationships against the Lamport timestamps:
| Event | Lamport Clock | Check |
|---|---|---|
| a1 | 1 | |
| a2 | 2 | |
| a3 | 3 | |
| a4 | 4 | |
| a5 | 5 | |
| b1 | 3 | |
| b2 | 4 | |
| b3 | 5 | |
| b4 | 6 |
Wait, let me recalculate more carefully. Let’s redo with the correct application of rules.
For process A:
- Start: C_A = 0
- a1 (local): C_A = 0 + 1 = 1
- a2 (send): C_A = 1 + 1 = 2. Send message with ts=2.
- a3 (local): C_A = 2 + 1 = 3
- a4 (receive ts=3 from B): C_A = max(3, 3) + 1 = 4
- a5 (local): C_A = 4 + 1 = 5
For process B:
- Start: C_B = 0
- b1 (receive ts=2 from A): C_B = max(0, 2) + 1 = 3
- b2 (local): C_B = 3 + 1 = 4
- b3 (send): C_B = 4 + 1 = 5. Send message with ts=5.
- b4 (local): C_B = 5 + 1 = 6
Let’s verify: a2 (ts=2) → b1 (ts=3): 2 < 3 ✓ a3 (ts=3) → b2 (ts=4)? Are they causally related? a3 → b2? a3 is after the send on A. a2 → b1 → b2, so a3 and b2… a2 → b1, a2 → a3, and b1 → b2. We need a3 → b2. a3 is after a2 on A. a2 → b1. So a3 and b2: is a3 → b2? Not directly. But a2 → b1 → b2, and a2 → a3. This doesn’t give us a3 → b2. So a3 || b2 (they’re concurrent). Lamport: 3 < 4, which suggests a3 → b2. But they’re concurrent! This is the limitation we’ll discuss in the next lesson.
For now, the important thing is that the algorithm is simple, decentralized (no central coordinator), and runs in bounded space (just one integer per process). It captures the essential property: if a → b, then L(a) < L(b). This monotonicity is the foundation for distributed ordering.
Check Your Understanding
- In the 2-process example above, what is B’s Lamport clock after receiving the message from A with timestamp 2?
- What is the purpose of the max() operation when receiving a message?
- If two processes never communicate, what happens to their Lamport clock values? Can we compare them?
The “So What?”
Lamport clocks are the simplest logical clock algorithm. They appear in distributed databases for transaction ordering, in distributed debuggers for reconstructing event order, and in consensus protocols as part of the leader election mechanism. When you see a monotonically increasing counter in a distributed system — sequence numbers, transaction IDs, operation IDs — you are looking at a descendant of Lamport’s idea. Understanding the counter algorithm gives you the foundation for more sophisticated clock systems.
✏️ Exercises
Topic 4: Lamport Clocks — Exercises
Exercise 1: Clock Update
Process A has a Lamport clock value of 5. Process B has a Lamport clock value of 3. A sends a message to B.
(a) What is the Lamport timestamp attached to the message? (b) After B receives the message, what is B’s new Lamport clock value? Show the calculation. (c) What is the Lamport clock value associated with B’s receive event?
Exercise 2: Equal Clocks, What Do We Know?
Process A and Process B each have a Lamport clock. You observe that L(a) = 7 and L(b) = 7 for two events a and b on different processes. There is no direct communication between A and B in this timeline.
(a) Can a → b? Why or why not? (b) Can b → a? Why or why not? (c) Are a and b necessarily concurrent? Explain. (d) If L(a) = 7 and L(b) = 8, what can you conclude? What can you NOT conclude?
Exercise 3: Can L(a) == L(b) When a → b?
A student claims: “It is impossible for L(a) == L(b) if a → b, because Lamport clocks always increase.”
(a) Is the student correct? Prove or disprove. (b) Now consider a trickier claim: “If a → b, then L(a) < L(b) ALWAYS holds.” Is this always true? Under what conditions might it fail? (c) Challenge: Design a scenario (or prove it impossible) where a → b is TRUE but L(a) == L(b).
Exercise 4: Lamport Clocks in Dynamo
You are told to build a simple conflict detection system using Lamport clocks for a Dynamo-style distributed key-value store. There are 3 replica nodes.
(a) Describe the scenario where two concurrent writes to the same key produce Lamport clock values of L=5 (at node A) and L=3 (at node B). (b) Explain why L=5 > L=3 does NOT mean the write at node A happened after the write at node B. (c) What specific type of bug would this cause in production? Give a concrete example with user data. (d) After this bug is discovered, your team votes to switch to vector clocks. Explain in one sentence why vector clocks solve this problem.
👁️ View Solutions
Topic 4: Lamport Clocks — Solutions
Solution 1
(a) Before sending, A increments its clock: C_A = 5 + 1 = 6. The message carries timestamp 6.
(b) On receiving, B computes: C_B = max(C_B, T_message) + 1 = max(3, 6) + 1 = 7.
B’s new Lamport clock value is 7.
(c) The receive event itself gets the new clock value after the max+1 operation: 7.
Solution 2
(a) No, a → b cannot be true. The clock consistency condition says: if a → b, then L(a) < L(b). Since L(a) = L(b) = 7, we have L(a) ≮ L(b), so by contrapositive, a → b is false.
(b) Similarly, b → a is false (would require L(b) < L(a), which is also not the case since they are equal).
(c) They are necessarily concurrent. Concurrency means neither a → b nor b → a. We have shown neither holds, so a || b is proven. Lamport clocks CAN detect concurrency when timestamps are equal.
(d) If L(a) = 7 and L(b) = 8, we know:
- b → a is impossible (would need L(b) < L(a)).
- a → b is POSSIBLE but not guaranteed.
We cannot conclude: a → b might be true, or a and b might be concurrent. The Lamport clock cannot distinguish between “b is causally after a” and “b’s process has processed more local events than a’s process.” This is the gap problem.
Solution 3
(a) The student is correct. Within a single process, the counter always increases (rule 1: increment on every event). Across processes via message: the receiver computes max(C, T) + 1, which is strictly greater than T (the sender’s clock). By transitivity, if a → b through a chain, each link increases the counter. So L(a) < L(b) always.
(b) Yes, the claim is always true. It is the clock consistency condition, and it is provable:
- Same process: L(a) < L(b) because the counter increments.
- Message: L(send) < L(receive) because max(C, T) + 1 > T.
- Transitivity: L(a) < L(b) < L(c) implies L(a) < L(c).
No counterexample exists — the algorithm guarantees L(a) < L(b) whenever a → b.
(c) Impossible. The proof: the four update rules (increment on event, increment before send, max+1 on receive) guarantee strict monotonic increase along causal chains. If a → b, there must be at least one message or same-process step where the counter increases. By induction over the length of the causal chain, L(a) < L(b). Therefore L(a) == L(b) when a → b is impossible.
Solution 4
(a) Node A has been busy — it has processed 5 local events (internal computations, other writes) before its counter reached 5. It writes value “X” to key “k.” Meanwhile, Node B has been relatively idle — it has processed only 3 events total. It writes value “Y” to the same key “k.” Neither node communicated before writing.
The Lamport clocks: L(A_write) = 5, L(B_write) = 3. But these writes are concurrent — no message passed between A and B, so neither node knew of the other’s write.
(b) L=5 on node A simply means A has processed more events than B. It does not mean A’s write is causally after B’s write. A might have processed 4 local events before writing, making the counter 5, while B wrote immediately after just 2 local events, making the counter 3. The write of X at A and the write of Y at B are independent — no causal chain connects them.
(c) The bug: silent data loss. Suppose X = { “cart”: { “item”: “shoes”, “qty”: 1 } } and Y = { “cart”: { “item”: “shirt”, “qty”: 2 } }. Both are concurrent additions to a shopping cart. With Lamport clock conflict detection, the system sees L(X) = 5 > L(Y) = 3 and applies “last writer wins” (using Lamport clock ordering). It keeps X and discards Y. The user’s shirt is silently removed from the cart. No error is raised. The user checks out, thinking they ordered both items, but only the shoes are shipped.
(d) Vector clocks solve this because they maintain one counter per process, so the comparison [5, 0, 0] vs [0, 3, 0] reveals that A’s vector has A’s element larger and B’s vector has B’s element larger — neither dominates — meaning the writes are definitively concurrent and must be flagged as a conflict.