Vector Clocks & Lamport Timestamps

In a single computer, the operating system kernel assigns monotonic timestamps using CPU cycles. In a distributed system consisting of thousands of servers across global availability zones, relying on physical wall-clock timestamps (like System.currentTimeMillis() or NTP) to determine the true causal ordering of events is fundamentally flawed:

• Clock Drift & Skew: Quartz oscillators drift due to microscopic thermal variations. Even with Network Time Protocol (NTP) synchronization, clock skew between servers routinely ranges from 10ms to 500ms.
• NTP Jumps & Leap Seconds: NTP daemons can step clocks backwards or freeze time, violating the fundamental law of time monotonicity.
• The Last-Write-Wins (LWW) Hazard: If Node A writes at true time T=10 (local clock T=12) and Node B writes at true time T=11 (local clock T=9), an LWW database will silently overwrite Node B's newer data with Node A's older data, causing catastrophic silent data loss.

To order events without relying on physical hardware clocks, Leslie Lamport invented Logical Clocks.

A Lamport Timestamp is a simple monotonically increasing integer counter maintained independently by each node:

1. Each node initializes its counter to L = 0.
2. Before executing a local event, a node increments its counter: L = L + 1.
3. When sending a message over the network, the node attaches its current timestamp L.
4. When receiving a message with timestamp L_{msg}, the receiver updates its local clock:

L_{local} = \max(L_{local}, L_{msg}) + 1

The Limitation of Lamport Timestamps:

Lamport clocks guarantee that:

If Event A → B (A causally preceded B), then L(A) < L(B)

However, the converse is NOT true:

If L(A) < L(B), you CANNOT determine if A → B or if A and B were concurrent!

To detect whether two operations are causally related or occurred concurrently in conflict, systems use Vector Clocks.

A Vector Clock for a cluster of N nodes is an array of N logical counters:

V = [c_1, c_2, \dots, c_N]

Vector Clock Algorithm Rules:

1. Node i increments its own index before executing an event: V_i[i] = V_i[i] + 1.
2. When sending a message, Node i includes a copy of its entire vector V_i.
3. When receiving a message with vector V_{msg}, Node i updates every element:

V_i[k] = \max(V_i[k], V_{msg}[k]) \quad \forall k \in [1, N]

and then increments its own index: V_i[i] = V_i[i] + 1.

Concurrency Comparison Rules:

• A Causally Precedes B (A → B): If V_A[k] ≤ V_B[k] for all k, and V_A \ne V_B.
• Concurrent Conflict (A \parallel B): If neither vector dominates the other (e.g., V_A = [2, 1, 0] and V_B = [1, 2, 0]). The system detects that both nodes wrote concurrently without knowledge of each other!

When a conflict is detected, systems like Dynamo preserve both versions as siblings and delegate conflict resolution to application business logic (e.g., merging shopping cart items).