Clock synchronization
A Socratic walk-through of clock synchronization — reasoned out one step at a time, not lectured.
The question we started with
THE QUESTION #Why can two computers never fully agree on the order in which two events happened?
Two machines each timestamp an event. One reads 12:00:00.003, the other 12:00:00.001. Which happened first?
The instinctive answer is that the second one did, and that the residual doubt is a hardware problem — buy better oscillators, sync more often, and the doubt shrinks toward zero. That intuition is half right and half a category error, and separating the halves is the interesting work. One half is a measurement limit that can be made small but never removed. The other half is that for many pairs of events there is no answer being approximated at all.
Reasoning it through
REASONING #Start with the measurement. How does one machine learn another's time? It asks. It notes its own clock at send, the reply carries the server's clock, and it notes its own clock at receipt. Subtract, and you have a round trip and an estimate of the offset.
But look at what that estimate assumes. The client knows the total round trip. It does not know how that total split between the outbound and return legs — and nothing in the four timestamps can tell it, because separating them would require the two clocks to already agree. So the honest output is not a number but an interval: the true offset lies within plus or minus half the round trip. Halve the round trip and you halve the uncertainty; you never reach zero, and a path systematically faster one way than the other biases the answer by half the asymmetry, undetectably, forever.
Then there is drift between requests. A commodity quartz oscillator is typically specified within a few tens of parts per million, and fifty parts per million is about four and a third seconds a day. So the error sawtooths: corrected at each sync, growing until the next. Google's Spanner makes this explicit rather than hiding it — its clock interface returns an interval, and its published design budgets a worst-case drift of 200 microseconds per second between syncs 30 seconds apart, which is 6 milliseconds of accumulated uncertainty by the end of the interval. Its response is not to pretend the interval is a point but to wait it out: a transaction holds its locks until the uncertainty window has passed, buying a guarantee about ordering by paying latency for it.
Now the second half, which no hardware improves. Suppose the two machines never communicated between the two events, directly or indirectly. What would it even mean for one to have happened first? Nothing in the system depends on the answer; no observer inside it could be affected by either ordering. Leslie Lamport's 1978 formulation takes this seriously: the only ordering a distributed system genuinely has is happens-before, defined by steps within one process and by messages between them. It is a partial order, and two events with no chain of messages between them are simply concurrent — not "of unknown order" but unordered.
So the two machines cannot agree on an order because there is no order there. Any total ordering you impose — by timestamp, by node identifier, by whoever the coordinator asked first — is a convention chosen for convenience, and different conventions give different answers without any of them being wrong.
The analogy
THE ANALOGY #Think of two letters posted in different cities on the same morning, with no telephone call between the writers. You can ask the post offices for franking times and refine them indefinitely, but you are answering a question about clocks, not about the letters — neither writer knew of the other's letter, so nothing either wrote could depend on the other. If one had written replying to yours, the order would be settled without consulting any clock at all.
Letters exist in one world with a single true chronology, so a sufficiently good clock really would settle the postal case, whereas in special relativity two spacelike-separated events genuinely have no frame-independent order — the analogy understates how deep the problem goes, though for machines a few metres apart the practical limit is network asymmetry and drift, not physics.
Clarifying the model
THE MODEL #Three clarifications.
First, better clocks do help, and it matters not to overclaim. Hardware timestamping in the network interface, as the Precision Time Protocol uses, removes most software-stack jitter and reaches sub-microsecond agreement on a controlled network. That is a genuine win. It shrinks the interval without abolishing it, and it is defeated by exactly the thing it cannot see: path asymmetry.
Second, note what the relativity clause is and is not doing. Relativistic effects are real and measured — GPS satellites need a correction of roughly 38 microseconds a day, dominated by the gravitational term — but they are not why your two servers disagree. Invoking physics for a datacentre problem confuses a nanosecond-scale effect with a millisecond-scale one. The deep point stands on Lamport's argument alone, which needs no physics at all.
Third, the practical consequence is a redirection rather than a fix. Most systems do not need to know what time it is; they need to know what depended on what. Logical clocks give exactly that: a Lamport counter yields a total order consistent with happens-before, though a lower number does not prove causation, and vector clocks distinguish "before" from "concurrent" precisely at the cost of state proportional to the number of participants. Both have a limit worth naming — they see only the channels they instrument, so two events coordinated through a path the system does not track are reported as concurrent when they were not.
A picture of it
THE PICTURE #How to readThe two lines are two machines, and a commit is an event on one of them. Order along a single line is real — each machine knows its own sequence. The pair to look at is A writes x and B writes y: no path of arrows connects them in either direction, and that absence is the whole point. They are concurrent, and no clock reading discovers an order the structure does not contain. Then follow the join. Once A's message reaches B, everything on A's line up to the send is definitely before everything on B's line after the receipt — so B writes z is unambiguously after A writes x, and the messages, not the clocks, established it.
What became clearer
WHAT CLEARED #Two limits are usually collapsed into one. The measurement limit is real but bounded: you can only ever bracket another machine's clock within an interval, because splitting a round trip into its two legs would require the agreement you are trying to establish, and asymmetric paths bias the estimate invisibly. Better clocks narrow the interval and never close it — which is why the most careful systems return an interval and wait it out rather than reporting a point. The second limit is not about clocks at all: for events with no chain of messages between them, there is no order to measure, only a convention to pick. What a system usually needs is not the time but the record of what could have influenced what — and messages already carry that.
Where to go next
ONWARD #- How consensus protocols get a single agreed order without trusting any clock, and what they charge for it.
- Why leases and lock services are the one place a distributed system must reason about real elapsed time rather than causal order.
Key terms
TERMS #| Term | What it means |
|---|---|
| Clock skew / drift | the instantaneous difference between two clocks, and the rate at which that difference grows between corrections. |
| Happens-before | Lamport's partial order: within a process by program order, across processes by message send preceding receipt. |
| Concurrent events | a pair with no happens-before relation in either direction; unordered rather than of unknown order. |
Every term the collection defines is gathered in the glossary.