---
title: "Problems of Lamport's clock; vector clock"
subject: "Distributed System"
chapter: 5
key: "semester_7/distributed_system:lamport-problems-vector-clock"
source: https://www.bctengineer.com/q/semester_7/distributed_system/lamport-problems-vector-clock
site: BCT Engineering
---

# Problems of Lamport's clock; vector clock

Distributed System · Chapter 5: Time and State in Distributed Systems

- Asked in: 2076 Chaitra, 2+8 marks; 2075 Chaitra, 4+4 marks (asked 2 times)
- Video: [Vector Clock 🔥🔥](https://www.youtube.com/watch?v=Q69Thj9vFw4) — Perfect Computer Engineer
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_7/distributed_system/lamport-problems-vector-clock
- Whole chapter: https://www.bctengineer.com/md/semester_7/distributed_system/chapter-5

## Question

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.)

## 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.

## Answer

#### 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):
```text
 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.

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. What is the issue with Lamport timestamps?
   A. a -> b does not imply C(a) < C(b)
   B. They need synchronised physical clocks
   C. They cannot give any ordering at all
   D. C(a) < C(b) does not imply a happened before b, so concurrency cannot be detected
   Answer: D. Only one direction holds, so timestamps cannot tell causal from concurrent events. (Key point: Lamport issue)

2. On receiving (m, t), how does Pi update its vector clock?
   A. VCi[j] = max(VCi[j], t[j]) for all j, then increment VCi[i]
   B. Replace VCi with t
   C. VCi[i] = max(VCi[i], t[i]) only
   D. Add t to VCi entry by entry
   Answer: A. Take the element-wise maximum and then count the receive event by incrementing own entry. (Key point: Vector update on receive)

3. When are two events concurrent according to vector clocks?
   A. V(a) = V(b) in the first entry
   B. Neither V(a) < V(b) nor V(b) < V(a)
   C. V(a) is smaller in every entry
   D. They happen at the same real time
   Answer: B. If the vectors are incomparable, the events are concurrent. (Key point: Detecting concurrency)

4. What is the price paid for vector clocks over Lamport clocks?
   A. They lose the happened-before ordering
   B. They need a time server
   C. A vector of size N is stored and sent with each message
   D. They cannot be used for causal ordering
   Answer: C. More storage and bandwidth are needed in exchange for exact causality. (Key point: Cost of vector clocks)

## Related in Distributed System

- [Lamport's logical clock algorithm](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Alamport-clock) — Distributed System, chapter 5, asked 5×
- [Clock sync problems; Chandy-Lamport](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Aphysical-clock-problems-chandy-lamport) — Distributed System, chapter 5
- [Vector clock synchronization algorithm](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Avector-clock-algorithm) — Distributed System, chapter 5, asked 2×
- [Clock synchronization need; Lamport](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Aclock-sync-lamport-need) — Distributed System, chapter 5
- [Lamport algorithm for mutual exclusion](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Alamport-mutex) — Distributed System, chapter 6
- [Physical vs logical clocks; Lamport](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Alamport-physical-compare) — Distributed System, chapter 5

## Related in other subjects

- [T/F: radial more reliable than network](https://www.bctengineer.com/question.md?key=semester_8%2Ftransmission_and_distribution_system_design%3Atf-radial-more-reliable-network) — Transmission and Distribution System Design, chapter 5, asked 2×
- [RE: no more than 3 a's](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Are-at-most-3-as) — Theory of Computation, chapter 2
- [Why 3D graphics is more complex than 2D](https://www.bctengineer.com/question.md?key=semester_5%2Fcomputer_graphics%3Awhy-3d-more-complex-viewing-pipeline) — Computer Graphics, chapter 4
- [T/F: more circuits rather than higher voltage](https://www.bctengineer.com/question.md?key=semester_8%2Ftransmission_and_distribution_system_design%3Atf-circuits-rather-than-voltage) — Transmission and Distribution System Design, chapter 2