Key Question
What fundamental problem prevents Lamport clocks from detecting conflicts, and why does this lead directly to vector clocks?
Deep Dive
Lamport clocks guarantee that if a → b then L(a) < L(b). But the converse does not hold. This means there is a “gap” between the ordering information we want (causality) and the ordering information we get (counter comparison). This gap is not a bug — it is a fundamental consequence of using a single integer to track causality across multiple processes.
Let us examine a concrete scenario where this gap causes problems. Consider a distributed key-value store with three replicas:
Client sends write "X" Client sends write "Y"
| |
Replica A Replica B
a1 (L=1, local) b1 (L=1, local)
a2 (L=2, write X) b2 (L=2, write Y)
a3 (L=3, replicate to B) ───────────→ b3 (L=3, receive write X)
b4 (L=4, internal)Now let us see what happens when a third replica creates a read:
Replica A (write "X") Replica B (write "Y") Replica C (read)
a1 (L=1) b1 (L=1) c1 (L=1)
a2 (L=2, write X) b2 (L=2, write Y)
a3 (L=3, replicate) ───────→ b3 (L=3, recv X) c2 (L=2)
b4 (L=4)
b5 (L=5, replicate Y) ─────→ c3 (L=3, recv Y)
c4 (L=4, read)The conflict: Two clients concurrently wrote different values to the same key. X was written at Replica A, Y at Replica B. Both replicas accepted the writes because they did not coordinate. Later, the values propagated: X arrived at B, Y arrived at C.
Using Lamport clocks: Can we detect that X and Y are in conflict?
- X was written at a2 with L(X) = 2.
- Y was written at b2 with L(Y) = 2.
L(X) = L(Y) = 2. We know the events are concurrent because… wait, not quite. The Lamport counters are equal. Can we conclude concurrency from equal counters? No! Two causally related events can never have the same Lamport timestamp (the counter always increases). But equal counters does not guarantee concurrency either — it just means they have the same count on different processes.
Actually, with Lamport clocks, if L(a) = L(b), we know a is NOT causally related to b (because if a → b then L(a) < L(b)). So equal counters do indicate concurrency in this case. But the real problem is: what if L(P1’s write) = 2 and L(P2’s write) = 3? With Lamport clocks, we cannot tell whether one was before the other (P2’s write → P1’s write, or P1 → P2 via an unseen path) or they are concurrent. The counter values do not distinguish.
The critical failure mode:
Process A Process B Process C
| | |
a1 (L=1) | |
a2 (L=2, msg) ─────→ b1 (L=3) |
| | |
| b2 (L=4, msg) ────→ c1 (L=5)
| | |
Later, unrelated write by A:
a3 (L=3, write X) | |
b3 (L=?) c2 (L=?)Now suppose B also does a concurrent write Y. L(Y) on B might be 5 (if B has done many events). L(X) on A is 3. L(X) < L(Y) but X and Y are concurrent — no causal link. The Lamport clock incorrectly suggests X → Y.
This is the gap problem: Lamport clocks cannot distinguish between “a’s counter is smaller because b’s action is causally after a’s action” and “a’s counter is smaller because its process happened to process fewer events.”
The practical implication for databases: a Dynamo-style database using Lamport clocks for conflict detection would miss conflicts. When two replicas accept concurrent writes, the Lamport timestamps alone cannot tell the database that these writes are in conflict. The database might silently overwrite one value with the other, losing data.
This is the direct motivation for vector clocks. By keeping one counter per process (rather than one counter total), vector clocks can distinguish between “I processed fewer events” and “your event is causally after mine.” A vector clock carries the complete picture of what each process has observed, making conflict detection possible.
Check Your Understanding
- In the first scenario above (Replica A writes X, Replica B writes Y, no coordination), are the writes concurrent? What do their Lamport timestamps tell us?
- What does “the gap problem” refer to in Lamport clocks?
- Why does the gap problem make Lamport clocks unsuitable for conflict detection in a Dynamo-style database?
The “So What?”
Whenever you see a system that uses Lamport-like counters for conflict resolution (some NoSQL databases, some distributed caches), you should ask: “What happens with concurrent writes?” If the system cannot detect concurrency, it will silently lose data in the worst case. This is not a theoretical concern — early versions of Riak and other Dynamo-inspired databases shipped with Lamport-style conflict detection before switching to vector clocks. The gap between Lamport clocks and conflict detection is one of the most important lessons in distributed systems design.
✏️ 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.