Time and order

The natural next instinct is to reach for timestamps: if every machine records when things happened, surely you can reconstruct the order later. The instinct is wrong, and it is wrong in a way that corrupts data quietly rather than loudly.

What is wrong with clocks

Physical clocks drift — cheap quartz gains or loses on the order of tens of parts per million, seconds per day if uncorrected. NTP corrects them over the network, holding typical machines within a few milliseconds of truth on a good day and much worse under load — and the correction itself can step the clock backwards. Meanwhile a same-datacenter message arrives in half a millisecond. The conclusion is arithmetic: two machines’ timestamps routinely disagree by more than the time a message takes, so “compare the timestamps” can order a reply before the request that caused it. A last-write-wins store keyed on wall clocks will, on a bad day, let a stale write erase a newer one and log that all was well.

One immediately practical rule falls out before any theory: your language exposes two clocks. The wall clock tells humans the time and may jump. The monotonic clock only moves forward and is the only one fit for measuring durations. Every timeout and every latency metric belongs on the monotonic clock; a surprising number of production incidents trace to violating this sentence.

Happens-before — order without time

Lamport’s 1978 move was to stop asking when events happened and ask what could have caused what. Define happens-before (written a → b) by three rules: if a and b are in the same process and a came first, a → b; if a is the sending of a message and b its receipt, a → b; and the relation chains (a → b and b → c gives a → c). Events connected by no chain are concurrent — not “simultaneous”, but causally unrelated: neither could have known about the other. Order in a distributed system is a partial order, and pretending otherwise is where the bugs come from.

A Lamport clock makes this executable. Each process keeps a counter: increment on every local event; stamp outgoing messages with it; on receipt, set the counter to max(local, message) + 1. Walk an example: A’s counter reaches 5 and it sends a message stamped 5; B, sitting at 2, receives it and jumps to 6. Now anything B does next is numbered after the send that influenced it — causality is respected. The limitation: if two events have stamps 5 and 6 you cannot conclude the 5 caused the 6; unrelated events also get ordered numbers. Lamport clocks give you a consistent order, not the ability to detect concurrency.

Vector clocks buy that ability by keeping one counter per process. Each process increments its own slot; messages carry the whole vector; receivers take the element-wise max, then increment their slot. Now comparison is meaningful: [2,1,0] happened before [3,1,0] (every element ≤, one strictly less), while [2,1,0] and [1,2,0] are concurrent (each ahead somewhere) — which is precisely the signal a replicated store needs when two datacenters accepted writes to the same key and must decide: supersede, or genuine conflict? Dynamo, in Stage 5, deploys exactly this.

In practice

• Real systems mostly buy order structurally: a Kafka partition or a Raft log is a place where order is assigned once, so consumers never re-derive it. When you need cross-machine order, the honest options are “put it through one log” or “carry causality metadata” — not “trust the timestamp”.
• Hybrid logical clocks (HLC) combine a wall clock with a logical counter — timestamps that are readable by humans and respect happens-before; several modern databases use them.
• And the exception that proves the rule: Google’s Spanner (Stage 5) gets away with timestamp ordering only by measuring clock uncertainty with GPS and atomic clocks and deliberately waiting it out. If you are not doing that, you do not have its guarantee.