Day 5: Logical Clocks and Causality

Phase 1 · May 24, 2026

Agenda (2–3 hours)

• Read (45 min): Lamport "Time, Clocks, and the Ordering of Events in a Distributed System" (1978) — the full paper is only 9 pages
• Study (45 min): Work through vector clock examples by hand; trace a causal anomaly
• Practice (45 min): Implement Lamport clock and vector clock in Rust (simple structs, no networking)
• Challenge (30 min): Given a set of events with vector timestamps, determine all causal relationships and any concurrent pairs

Why Physical Clocks Fail

Physical clocks drift. NTP corrects drift but not atomically — a node can observe time going backward.

Consequences:

• You cannot use wall-clock timestamps to order events across nodes
• "Created at 14:00:01.003" on node A may be causally before "Created at 14:00:01.001" on node B
• Spanner uses atomic clocks + GPS with TrueTime to bound uncertainty to ~7ms; most systems can't afford that

Lamport Timestamps (1978)

Happens-before (→): event A happened before B if:

1. A and B are on the same process and A occurred first, OR
2. A is a send event and B is the corresponding receive event, OR
3. ∃C such that A → C and C → B (transitivity)

Lamport clock rule:

• Each process maintains counter L
• On event: L += 1
• On send: attach L to message
• On receive: L = max(L, msg.L) + 1

If A → B then L(A) < L(B). But L(A) < L(B) does not imply A → B.

Vector Clocks

Fix Lamport's false positive: vector clocks capture exactly the happens-before relation.

Each process i maintains vector V[1..n]:

• On event at process i: V[i] += 1
• On send from process i: attach current V
• On receive at process j from i: V[j][k] = max(V[j][k], msg.V[k]) for all k; then V[j][j] += 1

Comparing timestamps:

• A → B iff V(A)[k] ≤ V(B)[k] for all k, with at least one strict inequality
• Concurrent iff neither A → B nor B → A

Version Vectors vs Vector Clocks

Version vectors track replica state divergence (not event ordering):

• DynamoDB, Riak, Cassandra use them to detect write conflicts
• Each replica has an entry: {replica_id: last_write_version}
• Conflict = neither version vector dominates the other → application must resolve

Amazon's Dynamo paper introduced this; Riak later moved to DVV (Dotted Version Vectors) to avoid false conflicts from client-assigned versions.

Key Takeaways

• Wall-clock ordering is unreliable across nodes — use logical clocks
• Lamport clocks: total order, but can't distinguish happens-before from concurrent
• Vector clocks: precise happens-before tracking; O(n) space per message
• Version vectors: detect replica divergence for conflict resolution

Tomorrow: CRDTs — data structures designed to merge concurrent updates without coordination.