Skip to main content

Problems of Lamport's clock; vector clock

Short answer

Lamport clocks only guarantee that if a happens before b then C(a) < C(b); the converse fails, so concurrent events cannot be identified. Vector clocks keep a vector per process, increment the own entry on events, merge maxima on receive, and then increment own entry. Comparison gives a before b if and only if its vector is strictly smaller.

What is the issue in Lamport's timestamp? How do you avoid the issue? Explain with your alternate algorithm. (List the problems of Lamport's clock with example. How is vector clock more beneficial than Lamport's clock? Explain with implementation rules of vector clock.)

Issue in Lamport's timestamp

Lamport clocks guarantee only one direction: a → b implies C(a) < C(b). The converse is false: C(a) < C(b) does not mean a happened before b. So by looking at timestamps we cannot tell whether two events are causally related or concurrent.

Example: P1 does event a with C=1 and P2 independently does event b with C=2, with no message between them. The timestamps say 1 < 2, but a and b are concurrent. Also, total ordering by timestamp may impose an artificial order, and causal violations cannot be detected (for example in causal message delivery, or when detecting inconsistent updates in replicas).

Solution: Vector clocks

A vector clock for a system of N processes is a vector VCi[1..N] kept by each process Pi. VCi[i] counts events at Pi; VCi[j] is Pi's knowledge of the number of events at Pj.

Implementation rules

  1. Initially VCi[j] = 0 for all j.
  2. Before each local event (and before a send), Pi increments its own entry: VCi[i] = VCi[i] + 1.
  3. A message sent carries the vector t = VCi.
  4. On receiving (m, t), Pi updates VCi[j] = max(VCi[j], t[j]) for every j, then increments VCi[i] = VCi[i] + 1.

Comparison

  • V = W if all entries are equal.
  • V ≤ W if V[j] ≤ W[j] for all j.
  • V < W if V ≤ W and V ≠ W.
  • Event a → b if and only if V(a) < V(b).
  • If neither V(a) < V(b) nor V(b) < V(a), a and b are concurrent.

Example (two processes):

 P1:  a(1,0) ------------------------------------ d(2,3)
          \  m                                    ^
           \                                     / m'
 P2:  b(0,1) --- c(1,2) ------------- e(1,3) ---+
  • a: P1 sends m with (1,0).
  • b: local event at P2, (0,1).
  • c: P2 receives m: max((0,1),(1,0)) = (1,1), then own entry +1 gives (1,2).
  • e: P2 sends m' with (1,3).
  • d: P1 (at (1,0)) receives m': max((1,0),(1,3)) = (1,3), then own entry +1 gives (2,3).

a (1,0) and b (0,1) are incomparable, so they are concurrent, while a (1,0) < d (2,3) shows a → d. Lamport clocks would give a = 1 and b = 1; from Lamport values alone we can never tell whether two events are related or concurrent, but the vector comparison shows it directly.

Why vector clock is better

  • Captures causality exactly (if and only if), not just consistency.
  • Detects concurrent events and conflicting updates.
  • Used for causal ordering of messages, replicated databases and versioning (Dynamo, Riak).
  • Cost: a vector of size N per message, so more storage and bandwidth than one integer.

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Distributed System chapter 5 questions →