Time and Ordering in Distributed Systems

Every machine has its own clock, and none of them agree. That single fact is the root of ordering problems in distributed systems: when two machines each believe a different "now," no wall-clock timestamp can tell you which event came first. This article covers why clocks lie, how Lamport and vector clocks order events without time at all, and how hybrid logical clocks and Spanner's TrueTime approximate a usable global time.

Wall clocks lie

NTP keeps machine clocks near UTC, but "near" is doing a lot of work. Skew between two synchronized machines is typically milliseconds and can spike into seconds; clocks drift, NTP steps clocks backward when correction is large, and leap seconds are handled inconsistently across operating systems. A timestamp read from time() is a local opinion, not a fact about the universe.

The consequence is categorical: timestamps from different machines cannot be compared. A later timestamp does not mean a later event — machine A's clock can be ahead of machine B's by more than the interval between two events, and the ordering inverts. Worse, a stepped clock is not even monotonic locally, so a machine can produce a timestamp older than its previous one.

Happens-before and Lamport clocks

Ordering does not need time. Lamport's insight (1978) was to define ordering from causality: event a happens-before b (a → b) if a precedes b on the same machine, or if a is a message send and b is its receive, or by transitivity. This is a partial order — events on different machines with no causal link are concurrent, and no ordering between them exists to be discovered.

A Lamport clock is a counter with simple rules:

local event:  C = C + 1
send:         C = C + 1, attach C to message
receive:      C = max(C, received_C) + 1

The guarantee: if a → b, then C(a) < C(b). The trap is the converse — C(a) < C(b) does not imply a → b. Concurrent events get an arbitrary total order, and nothing in the numbers tells you they were concurrent. Lamport clocks give you a total order consistent with causality, but they cannot detect concurrency, which is exactly the information you need to find conflicts.

Vector clocks

A vector clock gives each process a vector of counters, one per process. On a receive, merge element-wise with the received vector, then increment your own entry:

V(a) ≤ V(b) element-wise  ⟺  a → b  (or a == b)
V(a) and V(b) incomparable ⟺ a and b are concurrent

Now concurrency is detectable: two writes whose vectors are incomparable conflict, and the application can decide (merge, reject, or last-writer-wins with a tiebreaker). The cost is metadata that grows with the number of processes — O(n) per message, forever — which is why vector clocks are used where conflict detection matters (CRDTs, distributed filesystems, Dynamo-style stores) and avoided where a total order is cheaper.

Hybrid logical clocks

A hybrid logical clock (HLC) keeps a physical component — the machine's wall clock — and a logical component that absorbs causality. Each event takes the max of the physical clock and the received HLC; on ties the logical counter increments. The result is a timestamp that is close to real time (bounded by clock error), still monotonic, and causal: if a → b, then HLC(a) < HLC(b). HLCs give you "real-ish" timestamps you can sort by — used by CockroachDB and other systems that need both wall-clock appeal and causal correctness.

TrueTime: Spanner's answer

Spanner's TrueTime sidesteps the whole problem by being honest about uncertainty. Instead of a single timestamp, each clock provides an interval [earliest, latest] known to contain the true time (built from GPS and atomic clocks, which bound the error ε). When Spanner assigns a commit timestamp, it uses the interval's latest bound and then waits out the uncertainty (the commit-wait, roughly 2ε) so that any transaction that commits later gets a timestamp strictly greater. The result: commit timestamps are a total order that matches real time — at the cost of adding the wait to every commit's latency.

commit ts = clock.latest()
wait until real_time > clock.earliest + 2ε
# now any concurrent transaction commits with a strictly larger ts

TrueTime does not make clocks agree; it makes the decision robust to their disagreement.

Practical rules

• Last-write-wins needs a tiebreaker: timestamps alone are ambiguous, so LWW keys on (timestamp, node_id) and still reorders causally dependent writes — use version vectors when that matters.
• TTLs need skew margin: a TTL of 60 seconds on machine A can be 60 seconds minus the skew on machine B. Add margin or your cache entries expire early — or late, which is worse.
• Detect skew, don't assume it: monitoring the max and min clock values across your fleet surfaces badly skewed nodes before their timestamps corrupt ordering decisions downstream.