Distributed Systems Core · lesson 7 of 11 · about 28 min
Why 'which happened first?' is hard when no two clocks agree: how far real clocks drift, how timestamps put effects before causes, Lamport and vector clocks that order by cause instead of by time, hybrid and TrueTime clocks that get close to real time and stay correct, and the leap second that made a subtraction negative. Tap any for a plain-language card.
Clocks disagree
So at any instant, a fleet of machines has clocks spread over some range. The simulation gives each machine a fixed drift, resets it to within your NTP error at every sync, and measures the largest gap between any two clocks over the interval. Everything that compares timestamps from different machines inherits this uncertainty.
Move the sync interval from 64 seconds to an hour: the typical gap between two clocks grows from tens of milliseconds to hundreds.
10 machines drifting about 50 ppm and re-synchronised every 17 min to within ±5 ms: typically two of their clocks differ by 77 ms, and by 168 ms at worst. Any rule such as "the later timestamp wins" can be wrong whenever events are closer together than that.
Seeded simulation: each machine has a fixed drift ~ N(0, ppm); at a sync its offset is reset to N(0, error); gap = max − min offset across the fleet, sampled across the sync interval over 60 repeats.
Effect before cause
The chance depends on how big the clock error is compared to the gap between the two events (here two one-way trips). With 20 ms of typical skew and a 20 ms round trip, a surprising share of reply-before-request orderings occurs. This is why you must not use wall-clock time to decide the order of events across machines.
Set the skew to 5 ms and see it vanish; set it to 100 ms with a 20 ms round trip and see about 40%.
With each clock off by about 20 ms and 10 ms each way, 23.6% of request/reply pairs come out in the wrong order when sorted by timestamp. The bars show the same for other clock errors. Fix it with logical clocks, which order events by what could have caused what instead of by the time on a wall.
40,000 seeded pairs: each machine's timestamp = true time + N(0, error); wrong when the reply's stamp is smaller than the request's.
Lamport clocks
The converse does not hold: a smaller stamp does not mean “happened before”. Two events on different machines with no message path between them are concurrent, yet the counters still give them different numbers. Below is a seeded run of 3 processes: each row is an event with its Lamport stamp (L). Count how many concurrent pairs the stamps would wrongly present as ordered.
Raise the events and lower the messages: most pairs become concurrent, and the Lamport order invents sequences that never existed.
Of 91 event pairs, 31 are truly ordered by cause and effect and Lamport stamps order every one of them correctly (0 wrong). But 60 pairs are concurrent, and for 47 of them the stamps differ anyway, so reading "smaller stamp = earlier" would invent an order that never existed. Lamport clocks give a consistent order; they cannot tell you when events were independent.
A real Lamport clock on a seeded message-passing run. Pair relations are computed from vector clocks kept alongside (next scene).
Vector clocks
This is the same machinery as the version vectors in the Quorums lesson. The price is size: the vector has one entry per participant, which is fine for a handful of replicas and heavy for thousands of clients. Pick any two events from the run of the previous scene (same seed) and compare what the Lamport stamp and the vector clock each say.
Try events 4 and 14: they are far apart in the list yet unrelated. Lamport still gives them different stamps.
| Event | What happened | Lamport | Vector clock |
|---|---|---|---|
| a = #1 | C sends to A | 1 | [0, 0, 1] |
| b = #14 | A receives from C | 4 | [4, 0, 1] |
Vector clocks say: a happened before b. Lamport stamps say: a looks earlier. Here the two clocks agree; Lamport is always right about causally ordered pairs.
Same seeded run as the previous scene. a ≤ b means every entry of a is ≤ the matching entry of b; incomparable vectors are concurrent.
Best of both
Google Spanner takes a hardware route: exposes the clock as an interval [earliest, latest] of width 2ε, from GPS receivers and atomic clocks in each data centre. To make timestamps globally ordered, a transaction waits out the uncertainty (“commit wait”, about 2ε) before acknowledging. The Spanner paper reports ε between about 1 and 7 ms. A better clock buys faster commits.
Raise the skew and watch the HLC stay within the skew of real time with a small counter, with zero causality violations.
With wall clocks differing by up to ±50 ms, the hybrid clock was never more than 47 ms ahead of a machine's own wall clock, used a counter up to 13, and every received message got a later stamp than its send (0 violations). For TrueTime with ε = 7 ms, a transaction waits about 14 ms to commit, so one hot row can commit about 71 times a second.
HLC update rules from the Kulkarni et al. paper, run on three machines with random offsets and a seeded message pattern. Commit wait = 2ε; throughput per row = 1 ÷ wait.
Which clock?
Wall clocks are for humans, Lamport clocks give an order, vector clocks detect conflicts, hybrid clocks and TrueTime mix real time with correctness. Match the clock to the job. Each answer is worth 20 XP.
Ask: is this for a person to read, to order events, to detect concurrency, or to be both close to real time and causal?
Showing 'posted 5 minutes ago' under a comment.
Tip: press 1 to 4 to answer, Enter for the next one.
Who lives by this
Four published systems and papers about time in distributed systems.
'Time, Clocks, and the Ordering of Events in a Distributed System'
Lamport's 1978 paper defined the happens-before relation and the logical clock that respects it, showing that distributed systems can agree on an order of events without synchronised physical clocks. It is among the most cited papers in computer science.
vector clocks to detect concurrent writes
The Dynamo paper describes using vector clocks to capture causality between versions of an object, so that concurrent updates are detected and handed back to the application to reconcile instead of being silently overwritten by the one with the later timestamp.
TrueTime and commit wait
The Spanner paper describes TrueTime, an API that returns a time interval backed by GPS receivers and atomic clocks, with the uncertainty reported at roughly 1 to 7 ms. Transactions wait out that uncertainty before committing (commit wait), which gives externally consistent timestamps worldwide.
hybrid logical clocks, max clock offset
CockroachDB timestamps transactions with hybrid logical clocks on commodity servers and has a configured maximum clock offset (500 ms by default). Its documentation explains that a node whose clock drifts too far from the rest will shut itself down rather than risk serving inconsistent reads.
Interview angle
Six questions, each worth 20 XP. Time and ordering come up in almost every design that has more than one writer.
Say that you do not trust wall clocks across machines, name the logical clock you would use, and why.
A 50 ppm crystal drifts by about how much a day?
Tip: press 1 to 3 to answer, Enter for the next one.
Break it
The fix is simple and standard: measure durations with a (one that counts elapsed time and never steps; System.nanoTime, time.monotonic, CLOCK_MONOTONIC), and use wall time only for dates. Set the size of the step and how long operations take, and count the damage.
With a 1-second step and 50 ms operations, every operation running at that instant has a negative duration. Then switch to the monotonic clock.
When the clock steps back 1000 ms, the 250 operations in progress at that moment are timed as -950 ms instead of 50 ms: 250 negative durations that any code assuming "elapsed ≥ 0" will mishandle.
Operations in progress at the step = rate × duration. If the step exceeds the duration, the measured time is negative.
Where to go next