Key Question
Does L(a) < L(b) always mean a happened before b? And if not, what good are Lamport clocks?
Deep Dive
Lamport’s algorithm was designed to satisfy one specific property: if a → b, then L(a) < L(b). This is called the “clock consistency condition.” We can prove it holds by considering each case:
Case 1: Same process. If a and b are in the same process and a → b, then a’s Lamport clock is strictly less than b’s. This is trivial — the counter always increases within a process.
Case 2: Send-receive. If a is a send event and b is the corresponding receive event, then L(a) < L(b). The send attaches its timestamp to the message. The receiver computes max(C_receiver, T_sender) + 1. Since T_sender = L(a), the receiver’s clock after the receive is at least L(a) + 1 > L(a). So L(a) < L(b).
Case 3: Transitivity. If a → b and b → c, then L(a) < L(b) (by case 1 or 2) and L(b) < L(c) (by case 1 or 2). Therefore L(a) < L(b) < L(c), so L(a) < L(c).
The proof is straightforward, and it means Lamport clocks correctly capture happened-before ordering. If you know that a → b, you can be confident that a has a smaller Lamport timestamp.
The limitation: the converse is NOT true.
L(a) < L(b) does NOT imply a → b. In other words, Lamport clocks can produce false positives — they can suggest a causal relationship where none exists.
Here is a concrete counterexample showing why:
Process A Process B
| |
a1 (L=1) |
| b1 (L=1)
a2 (L=2) |
| b2 (L=2)In this scenario, A and B never communicate. All events are local.
- Within A: a1 → a2. L(a1)=1, L(a2)=2. ✓
- Within B: b1 → b2. L(b1)=1, L(b2)=2. ✓
- Across processes: a1 || b2 (concurrent, no causal link).
- But L(a1) = 1 and L(b2) = 2. Since 1 < 2, the Lamport clock suggests a1 → b2 — but that is FALSE. There is no message, no causal chain.
The problem is that Lamport clocks are just counters. They advance independently on each process until a message carries a timestamp across the boundary. Without communication, the counters on two processes have no relationship to each other, even though both are increasing. A counter of 2 on Process B means “B’s second event” — it has no relation to “A’s first event.”
Why can’t we fix this? To determine whether a and b are causally related, we would need to know whether there is any chain of messages connecting them. A single integer cannot encode that information when there are multiple processes. This fundamental information deficit is why Lamport clocks cannot detect concurrency.
The practical consequence: Lamport clocks are useful for establishing a consistent total order (every observer agrees on the order of events) but not for detecting conflicts (determining whether two events were independent). For conflict detection, we need vector clocks, which explicitly track the per-process counters.
Check Your Understanding
- In the space-time diagram above (Process A events a1, a2 and Process B events b1, b2), is L(a2) < L(b1)? Does a2 → b1? What does this show about the converse property?
- State the one property that Lamport clocks guarantee (the “clock consistency condition”).
- Why can’t Lamport clocks detect concurrent events?
The “So What?”
Lamport clocks are everywhere — but the common mistake is to treat them as “timestamps” in the physical sense. If you see code that compares Lamport counters and draws conclusions about ordering, ask: “Does this system only need total ordering (for which Lamport clocks work), or does it also need to detect concurrency (for which they don’t)?” Using Lamport clocks for conflict detection is like using a thermometer to measure weight — the tool is not designed for the job.
✏️ 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.