Clocks and ordering

Why machines disagree about time, and how to order events anyway.

System design conceptCoordination and consistency1 Nov 2026

01The intuition

The problem it solves

Two auction servers in two cities receive two bids on the same item. Server A's clock says its bid arrived at 12:00:00.500. Server B's clock says 12:00:00.498. B's bid wins by two milliseconds. But B's clock runs three milliseconds fast, so A's bid actually came first. The computers did not agree about what time it was, and that disagreement decided who paid.

Every computer has a quartz clock that drifts, by tens of parts per million, which is seconds a day. Network time protocol pulls them back, but only to within a few milliseconds in a good data center and tens of milliseconds across the internet. So a timestamp from one machine cannot be compared to a timestamp from another at fine resolution. Yet systems must order events: which write is newest, which bid came first, which version of a document wins. The way out is to stop asking clocks and start asking what happened before what.

Build it one piece at a time

Step 1: happened-before. Event X happened before Y if they are on the same machine and X came first, or if X is the sending of a message and Y its receipt, or by a chain of such steps. If neither happened before the other, they are concurrent, and no clock can honestly order them.

Step 2: a Lamport clock, a counter that respects that. Each machine keeps an integer. It increments it for each local event and stamps outgoing messages with it. On receiving a message stamped m, the receiver sets its counter to max(own, m) + 1. Now if X happened before Y, X's stamp is smaller. Ties between concurrent events are broken by machine ID.

Event	Machine A counter	Machine B counter	Note
A: bid received	1	0	local event
A sends "bid" to B	2	0	message stamped 2
B receives it	2	max(0, 2) + 1 = 3	B now knows it is after A's bid
B: its own bid	2	4	ordered after A's

Step 3: vector clocks, to detect concurrency. A Lamport stamp orders everything, even concurrent events, so it cannot tell you two edits conflict. A vector clock keeps one counter per machine: [A:2, B:4]. Compare two vectors: if every entry of one is ≤ the other's, it happened before; otherwise they are concurrent, and the application must merge. This is how a replicated store knows "these two versions of the shopping cart were edited independently; keep both items".

Step 4: hybrid logical clocks, when you want real time too. Combine the wall clock with a counter: use the physical time when it is ahead, otherwise increment the logical part. Stamps now look like real timestamps, stay close to real time, and still respect happened-before. Many modern databases use this for versions.

Step 5: bounded uncertainty, the TrueTime idea. If the clock service tells you not "it is 12:00:00.500" but "it is between 12:00:00.496 and 12:00:00.504", a system can wait out the uncertainty: commit, then wait 8 ms before acknowledging, so any transaction that starts after the acknowledgement surely has a later timestamp. With GPS and atomic clocks the interval is a few milliseconds, and global ordering by timestamp becomes safe. Without such hardware, the interval is tens of milliseconds and the wait is too long, which is why most systems use logical clocks instead.

Why it works, with the numbers

Lamport's property is the whole guarantee:

if X → Y then L(X) < L(Y); the converse is not promised

Vector clocks add the converse for concurrency detection at a cost of one integer per participating machine per version, which is why they are kept per key and pruned. The commit-wait of a bounded clock costs exactly the uncertainty interval, about 7 ms in published numbers, per write. The failure modes: trusting wall-clock timestamps from different machines for ordering (the auction bug), vector clocks that grow with every client that ever wrote, and a clock that jumps backwards after a time sync, which a monotonic clock source avoids for local durations.

The trade-off you must say out loud

Physical timestamps are readable and cheap but wrong at the millisecond; logical clocks are correct but say nothing about real time. Say which events you must order, whether concurrency must be detected or just resolved, and who breaks ties. The follow-up is "what does last-write-wins mean on your system", and the honest answer is "the write with the largest timestamp from a clock that may be wrong, so we only use it where losing a concurrent write is acceptable".

Where it shows up in the 100 Google problems

Online auction: bids are ordered by a single sequencer per item, not by the servers' clocks.
Globally consistent database: TrueTime and commit-wait give externally consistent timestamps across continents.
Offline-first sync: vector clocks or version vectors tell a merge "these edits are concurrent".
Unique ID generator: time-ordered IDs embed a clock and must handle it running backwards.
Distributed tracing: spans from different machines are ordered by parent-child links, with their clocks only roughly aligned.