Time, Clocks and Ordering: Lamport and Vector Clocks

Distributed systems constantly need to know what happened first: which write wins, whether a reply came after its message, which version of a record is newer. Physical clocks on different machines disagree, so naive timestamps give wrong answers. Logical clocks (Lamport timestamps, vector clocks) and hybrid clocks track order without trusting wall-clock time.

Why wall clocks lie

• Clock skew: machines' clocks drift and are corrected by NTP to within milliseconds at best, sometimes much worse.
• Clock jumps: NTP corrections, leap seconds and VM migrations can move a clock backwards or forwards.
• No global now: two events on different machines 1 ms apart can carry timestamps in the wrong order.

With last-write-wins by timestamp, a write from a machine whose clock is 50 ms fast can silently overwrite a later write from a correct machine. Data loss with no error.

Happens-before

Leslie Lamport's insight: what matters is causality. Event A happens before B if A and B are on the same process with A first, or A is sending a message that B receives, or there's a chain of these. Events with no such chain are concurrent: neither could have influenced the other.

Lamport timestamps

Each process keeps a counter. Increment it on every event; attach it to every message; on receive, set the counter to max(local, received) + 1.

• Guarantee: if A happens before B, then L(A) < L(B).
• Limitation: the converse doesn't hold. L(A) < L(B) doesn't tell you A caused B; they may be concurrent. Lamport timestamps (with a process ID to break ties) give a total order consistent with causality, which is enough for things like ordering log entries or mutual exclusion.

Vector clocks

A vector clock keeps one counter per process: {A: 2, B: 1, C: 0}. Increment your own entry on each event; on receive, take the element-wise maximum and then increment your own. Comparing two vectors tells you whether one happened before the other (every entry ≤, at least one <) or whether they're concurrent (each is ahead in some entry).

Vector clocks let Dynamo-style databases detect conflicting writes instead of silently dropping one; the application (or a CRDT) then merges them. Their size grows with the number of writers, so systems prune them or use dotted version vectors.

Hybrid logical clocks and TrueTime

• Hybrid logical clocks (HLC) combine physical time with a logical counter: timestamps stay close to wall-clock time (useful for humans and for snapshot reads) while still respecting causality. CockroachDB and YugabyteDB use them.
• Google TrueTime exposes clock uncertainty as an interval using GPS and atomic clocks. Spanner waits out the uncertainty (a few milliseconds) before committing, so timestamp order matches real-time order globally: external consistency.

Practical guidance

• Don't use wall-clock timestamps to decide which concurrent write wins when losing data matters; use versions, logical clocks, or a single leader that orders writes.
• Use monotonic clocks (not wall time) to measure durations and timeouts inside a process.
• Use per-entity sequence numbers from a single writer (a partition leader) to order events for that entity.
• For mergeable data (counters, sets, collaborative text), use CRDTs, which converge regardless of order.