Concept of the day · distributed systems

Vector Clocks and Logical Time

Wall clocks cannot order events across machines; counters can.

The mechanism. A Lamport clock is a counter per node: increment on every local event, and on receiving a message set your counter to max(local, received) + 1. This guarantees that if A caused B then time(A) < time(B). It does not tell you the converse, so you cannot distinguish concurrency from causality. A vector clock fixes that: each node keeps a vector of counters, one per node. Compare two vectors element-wise — if every element of A is ≤ B, A happened before B; if neither dominates, the events are genuinely concurrent.

What that buys you. Concurrency becomes detectable rather than silently resolved. Dynamo used vector clocks so a conflicting write surfaced as siblings the application could merge, instead of last-write-wins quietly deleting a user's shopping cart item. Git's commit graph is the same idea made concrete: parents encode causality, and a merge is how you resolve a concurrent pair.

Why wall clocks fail. NTP drift, leap seconds, VM pauses and clock skew between machines are all larger than the intervals you are trying to order. "Last write wins by timestamp" means "whichever machine's clock is fastest wins", which is a data-loss policy, not a conflict-resolution policy. Google's TrueTime and Spanner's commit-wait exist precisely because getting ordering from physical clocks requires bounding the uncertainty in hardware.

The cost. Vectors grow with the number of writers, so long-lived objects accumulate entries. Hybrid logical clocks (HLC) are the common compromise: a physical timestamp plus a logical counter, so values are human-readable, close to real time, and still respect causality.

Takeaway. If two replicas disagree, the question is never "which is newer" but "are these concurrent". Only logical time can answer it.

← edition of 2026-10-28cheatsheet