Key Question

How can we extend Lamport’s idea to capture causality accurately across multiple processes?

Deep Dive

Lamport clocks use a single integer counter. This is insufficient for detecting concurrency because a single integer cannot distinguish between “I processed fewer events” and “your event is causally after mine.” Vector clocks solve this by using an array of N integers, where N is the number of processes in the system. Each element of the vector tracks the Lamport clock of the corresponding process.

The rules for vector clocks are a direct extension of Lamport’s rules:

1. Initialize: Each process maintains vector V = [0, 0, …, 0] of length N.
2. Local event: V[i] += 1 (increment the element corresponding to this process).
3. Send: V[i] += 1, then include the entire vector V in the message.
4. Receive: For each element j: V[j] = max(V[j], Vm[j]) where Vm is the vector from the message. Then V[i] += 1.

The key difference from Lamport clocks is that the receiver updates ALL elements of its vector to the maximum of its own and the sender’s, not just a single counter. This means each process carries a summary of the last known state of every other process.

Let us walk through a 3-process example step by step:

Process A (idx 0)   Process B (idx 1)   Process C (idx 2)
    V_A = [0,0,0]       V_B = [0,0,0]       V_C = [0,0,0]

Step 1: Process A has a local event.

V_A = [1,0,0]    (V_A[0] incremented)

A’s vector says: “I know my own state is version 1, and I know nothing about B or C.”

Step 2: Process A sends a message to B.

A increments: V_A = [2,0,0]
Message carries: [2,0,0]

Step 3: Process B receives the message from A.

B's current vector: V_B = [0,0,0]
B applies: V_B = max([0,0,0], [2,0,0]) = [2,0,0]
B increments its own: V_B = [2,1,0]

B’s vector says: “I know A is at version 2, I am at version 1, and I know nothing about C.” Crucially, B now knows that it has seen everything A had seen up to A’s version 2.

Step 4: Process B sends a message to C.

B increments: V_B = [2,2,0]
Message carries: [2,2,0]

Step 5: Process C receives the message from B.

C's current vector: V_C = [0,0,0]
C applies: V_C = max([0,0,0], [2,2,0]) = [2,2,0]
C increments its own: V_C = [2,2,1]

C knows: “A version 2, B version 2, C version 1.”

Space-time diagram showing vector evolution:

Process A          Process B          Process C
[0,0,0]            [0,0,0]            [0,0,0]
  |                   |                  |
a1 [1,0,0]            |                  |
  |                   |                  |
a2 [2,0,0] ─────────→ b1 [2,1,0]        |
  |                   |                  |
a3 [3,0,0]            |                  |
  |                   b2 [2,2,0] ───────→ c1 [2,2,1]
  |                   |                  |
  |                   b3 [2,3,0]         c2 [2,2,2]
  |                   |                  |

Now compare events using their vectors:

• a1 = [1,0,0], b3 = [2,3,0] Is a1 → b3? [1,0,0] < [2,3,0] (every element of a1 ≤ corresponding element of b3, and at least one is strictly less). Yes, a1 → b3.

• b2 = [2,2,0], c2 = [2,2,2] Is b2 → c2? [2,2,0] < [2,2,2] (C’s element is greater). Yes, b2 → c2.

• a3 = [3,0,0], c1 = [2,2,1] [3,0,0] vs [2,2,1]: 3 > 2 (A’s element), 0 < 2 (B’s element), 0 < 1 (C’s element). Neither dominates. a3 || c1 (concurrent).

We have successfully detected that a3 and c1 are concurrent — something Lamport clocks could not do.

Check Your Understanding

1. In the 3-process example, what is the vector clock value at b3?
2. What is the purpose of the max() operation when receiving a message, applied to each element of the vector?
3. Why does using N integers (one per process) provide more information than a single integer counter?

The “So What?”

Vector clocks are the standard tool for causality tracking in distributed systems. They appear in Amazon Dynamo (as version vectors), in Bayou’s database replication, in CRDTs for collaborative editing, and in distributed debuggers for causal tracing. The added cost — storing N integers per event and per message — is the price of accurate conflict detection. When you see a system that can tell you whether two updates are in conflict, vector clocks (or their close relatives) are almost certainly at work.

✏️ Exercises

Topic 5: Vector Clocks — Exercises

Exercise 1: Comparing Vectors

Given the following pairs of vector clocks from a 3-process system (processes A, B, C), determine whether the events are causally related (V1 < V2 or V2 < V1) or concurrent (V1 || V2).

For each pair, state whether V1 → V2, V2 → V1, or V1 || V2, and explain your reasoning.

Exercise 2: Causal Ordering

In a 3-process system, the following events occur:

1. Process A: local event X → V_A = [1, 0, 0]
2. Process B: local event Y → V_B = [0, 1, 0]
3. Process A: sends message to C → V_A = [2, 0, 0], message carries [2, 0, 0]
4. Process C: receives message from A → V_C = [2, 0, 1]
5. Process C: sends message to B → V_C = [2, 0, 2], message carries [2, 0, 2]
6. Process B: receives message from C → V_B = [2, 1, 2] (after max, then increment)

(a) Is event X causally related to event Y? What does the vector clock comparison show? (b) After step 6, what is the complete vector clock state on all three processes? (c) If a new event occurs on Process C after step 5 (without any new messages), what would its vector clock be?

Exercise 3: Dynamo Conflict Scenario

A 2-node Dynamo-style key-value store stores a document with key “profile” = { “name”: “Alice” }. The initial version vector is [(A, 1)].

The following events occur concurrently:

• Client 1 reads “profile” from Node A. Gets vector [(A, 1)], value = { “name”: “Alice” }. Client 1 adds field “age”: 30 and writes back to Node A.
• Client 2 reads “profile” from Node B. Gets vector [(A, 1)], value = { “name”: “Alice” }. Client 2 adds field “email”: “alice@example.com” and writes back to Node B.

(a) What is the version vector of Client 1’s write? Of Client 2’s write? (b) A third client reads “profile” from Node A. Node A has received both writes through replication. What vectors does the client receive? Are they concurrent? (c) The application uses a merge function that combines fields: the result should include all fields from both versions. What is the merged value and the merged version vector? (d) After the merge is written back, a fourth client reads the key. What vector does it receive, and what does it tell the reader about this version relative to the two original writes?

Exercise 4: LWW vs. Sibling Preservation

A social media application stores user posts in a Dynamo-style database. Each post has a “like count” and a “comments list.”

(a) Which field would benefit from sibling preservation (returning multiple versions for merge)? Which could safely use LWW? Explain your reasoning. (b) If the like count uses LWW and the comments list uses sibling preservation, how does the application handle a read that returns both a single value (for like count) and multiple siblings (for comments)? (c) Design a scenario where LWW on the like count loses exactly one “like” even though the user pressed the like button. (d) Would a vector clock implementation detect this lost update? Why or why not?