Clock Synchronization

The big picture#

Read the core sections top to bottom for the full mental model. The collapsible "Go deeper" box on logical clocks holds the alternative paradigm — ordering events without trustworthy physical time — that you can skip on a first pass and return to later.

Start here: there is no global clock#

If every machine's clock were perfectly accurate, distributed systems would be much simpler — timestamps could be compared directly, TTLs would expire exactly on time, 'last write wins' would actually mean the most recent write won. None of that holds in practice. There is no central clock every machine reads from; each host keeps its own time using a quartz crystal oscillator, and those crystals are imperfect.

A quartz clock drifts. Its frequency depends on temperature, supply voltage, and physical aging, so a typical computer clock gains or loses on the order of tens of parts per million — roughly a few milliseconds every few seconds in the worst case, and seconds per day even in normal conditions. Two machines that agree exactly at noon will visibly disagree by evening. Crucially, they drift at different rates and in different directions, so the gap between any two clocks keeps changing.

• Event ordering breaks: if machine A timestamps an event 'after' an event on machine B, but A's clock runs slow, the timestamps can claim the wrong order — A's later event looks earlier.
• TTLs and cache expiry misfire: a 60-second TTL set by one server and checked by another expires early or late depending on the skew between them.
• Leases and locks become unsafe: a node may believe it still holds a lease that the grantor already considers expired, so two nodes act as leader at once.
• 'Last write wins' picks the wrong winner: LWW conflict resolution (Cassandra, DynamoDB) compares wall-clock timestamps, so a write from a fast-running clock can clobber a genuinely newer write from a slow one.

Cristian's algorithm: sync to an authority#

Cristian's algorithm (Flaviu Cristian, 1989) assumes one thing the Berkeley algorithm doesn't: a server whose clock is trusted — synced to a GPS receiver or an atomic clock, for instance. A client wanting the correct time talks to it directly and corrects for the round trip.

1. The client records T0 — the time on its OWN (possibly wrong) clock — and sends a request to the server.
2. The server stamps its reply with Ts, its own current time, and sends it back immediately.
3. The client records T1 — again on its own clock — the moment the reply arrives.
4. Round-trip time RTT = T1 − T0. Assuming the network delay was symmetric (half the RTT each way), the server's time at the moment the reply is processed is Ts + RTT/2 — the server's clock adjusted forward for the trip back. The client sets its clock to that.

Because the accuracy is bounded by RTT/2, real implementations send several requests and keep the reply with the smallest RTT — the one least perturbed by queuing and congestion. They also slew rather than jump: instead of slamming the clock to the new value (which could make time run backward), they speed up or slow down the local clock until it converges, preserving monotonicity for code that assumes time only moves forward.

The Berkeley algorithm: sync to each other#

Sometimes there's no authoritative clock at all — just a set of peer machines, all equally fallible. The Berkeley algorithm (Gusella & Zatti, 1989) designates one of them a coordinator (the 'time daemon') not because it's more accurate, but because something has to collect the readings and do the math.

1. The coordinator polls every node (including itself) for its current time, using the same RTT/2 correction Cristian's algorithm uses for each poll.
2. It computes a robust average — typically discarding any reading too far from the others as a fault — so a node whose clock is wildly off (or just plain broken) can't drag the result toward nonsense.
3. It averages the remaining, trusted readings into a single reference value.
4. Instead of telling each node to jump to that absolute value, it sends each node a delta — 'advance by X' or 'go back by Y' — which the node applies to its own clock (by slewing, never a backward jump). Sending relative adjustments rather than absolute times keeps every node's correction tailored to its own current skew.

NTP: Cristian's idea, scaled to the internet#

The Network Time Protocol (NTP, currently NTPv4 in RFC 5905) is the algorithm that actually keeps the world's computers roughly in sync. At its core it is Cristian's algorithm — query a server, measure the round trip, correct by half — wrapped in a hierarchy and a pile of statistical filtering to make it robust over the messy public internet.

• Strata form a tree. Stratum 0 is a reference clock (atomic clock, GPS receiver). Stratum 1 servers are directly attached to those. Stratum 2 servers sync from stratum 1, stratum 3 from stratum 2, and so on — each level one hop further from the source and slightly less accurate.
• Four timestamps per exchange. NTP records the client's send time, the server's receive time, the server's transmit time, and the client's receive time. From these it computes both the clock offset (how far off the client is) and the round-trip delay — the server's processing time is subtracted out, not blamed on the network.
• Filtering and selection. NTP collects many samples, keeps the ones with the lowest delay (least jitter), and runs intersection/clustering algorithms across multiple servers to reject 'falsetickers' (lying or broken servers) and combine the survivors.
• Discipline, not jumps. NTP normally slews the local clock — adjusting its rate via a feedback loop — so time stays monotonic. It only steps the clock for large offsets at startup.

The payoff: NTP typically holds clocks within a few milliseconds to tens of milliseconds over the open internet, and well under a millisecond on a quiet LAN — all from the same RTT/2 estimate, made trustworthy by sampling and filtering.

Accuracy is bounded by the network#

The fundamental limit on synchronizing physical clocks is not the algorithm — it's the network. Because a client can only ever measure the round trip, not the one-way delay, the uncertainty in 'what time is it really?' is bounded by the asymmetry and variability of the path. You cannot sync two clocks more precisely than your uncertainty about how long messages take.

• WAN / open internet: round trips of tens of milliseconds, variable queuing → typical accuracy of a few to tens of milliseconds with NTP.
• LAN / same datacenter: sub-millisecond RTTs and low jitter → sub-millisecond accuracy with well-tuned NTP.
• PTP (IEEE 1588) with hardware timestamps: timestamps taken at the network-interface hardware remove software/OS jitter → microsecond or even sub-microsecond accuracy.
• GPS / atomic reference clocks: a local stratum-0 source removes the network from the critical path almost entirely → tight, externally-accurate time.

The accuracy ladder — and an escape hatch#

Once NTP is understood, the rest of the landscape is mostly 'how do we shrink the uncertainty further?' — plus one genuinely different idea: stop trying to sync physical clocks at all.

• NTP — software timestamps over IP; milliseconds on the WAN, sub-ms on a LAN. The default everywhere.
• PTP / IEEE 1588 — hardware timestamping at the NIC, designed for LANs; microsecond to sub-microsecond accuracy. Used where time is money: finance, telecom, datacenters.
• GPS / atomic reference clocks — local stratum-0 sources (GPS-disciplined oscillators, rubidium/cesium clocks) that give tightly bounded, externally-accurate time without depending on a distant server.
• Google TrueTime (Spanner) — combines GPS and atomic clocks across datacenters and, crucially, exposes time as an interval [earliest, latest] with a bounded uncertainty ε, rather than pretending to know the exact instant.

The unavoidable trade-offs#

Every approach to time in distributed systems is a choice among the same tensions: how close to real time, how strong the ordering guarantee, and how much latency or hardware you're willing to spend to get there.

• Bounded, never perfect: physical clocks can be kept within a known error, but that error is never zero. Designs that assume exact agreement (comparing raw timestamps for ordering) are bugs waiting to fire.
• Physical accuracy vs logical correctness: NTP/PTP give you approximate real time but can still misorder near-simultaneous events; logical/vector clocks give exact causal ordering but no real time. Pick the one the problem actually needs.
• External accuracy vs no authority: Cristian's/NTP pull toward a trusted source (accurate, but you must have and trust one); Berkeley needs no authority (robust to a missing reference, but only internally consistent).
• Latency for correctness — commit-wait: TrueTime makes time honest by exposing uncertainty ε, but Spanner must then WAIT out that uncertainty (a few milliseconds) before committing a transaction, so that no later transaction can possibly be assigned an earlier timestamp. You buy external consistency with a small, deliberate delay on every commit.

How clock sync goes wrong#

• Asymmetric latency: the RTT/2 assumption fails whenever the request and reply paths differ, silently biasing the estimate by half the asymmetry — undetectable from the round trip alone.
• Drift between syncs: a clock is only corrected at each sync; between syncs it free-runs and drifts, so accuracy decays until the next correction. Longer sync intervals mean larger worst-case skew.
• Leap seconds: UTC occasionally inserts a leap second, creating a 23:59:60 that naive code can't represent — historically the cause of real outages. Many operators 'smear' the leap second over hours (AWS, Google) so the clock never has to repeat or skip a second.
• Clock-skew bugs in algorithms: lease and lock protocols that compare timestamps across machines can let two nodes both believe they hold a lease if their clocks disagree — a classic source of split-brain.
• Jumping vs slewing: stepping a clock to a new value can make time go backward, breaking monotonic assumptions (durations measured as negative, ordering inverted). Slewing — adjusting the rate so the clock catches up gradually — avoids this but converges slowly.

Cristian vs Berkeley vs NTP vs logical clocks#

Where clock sync runs in the wild#

• NTP — everywhere. Every laptop, phone, and server runs an NTP (or chrony) client syncing to pool.ntp.org or a vendor service. It's the invisible default that keeps log timestamps and TLS certificate checks roughly honest.
• PTP in finance and datacenters — exchanges and trading systems use PTP with hardware timestamps to order trades to the microsecond (regulations like MiFID II mandate tight clock accuracy), and large datacenters use it for high-precision telemetry.
• Google Spanner / TrueTime — TrueTime's bounded-uncertainty interval plus commit-wait is what lets Spanner offer externally-consistent, globally-distributed transactions: it assigns commit timestamps and waits out ε so the order is provably correct across continents.
• AWS Time Sync Service — Amazon runs satellite-connected and atomic reference clocks in every region, reachable from EC2, with a PTP hardware clock for microsecond accuracy and automatic leap-second smearing.

Common misconceptions & gotchas#

In an interview#

Open with the headline: there is no global clock — quartz oscillators drift, so timestamps from different machines are never directly comparable, and that breaks ordering, TTLs, leases, and last-write-wins. Then name the fork in the road: is there a trusted time source? If yes, Cristian's algorithm (or NTP, its real-world descendant). If every node is a peer, Berkeley's averaging — internally consistent but not externally accurate.

Be ready to derive RTT/2 unprompted: it's the mechanism every physical-sync algorithm depends on, and the error bound (±RTT/2) is the whole point. The most common follow-up is 'what if the delay isn't symmetric?' — the estimate is off by half the asymmetry, undetectable from the round trip. Mention the accuracy ladder (NTP ms → PTP µs → TrueTime bounded interval) to show range.

Land the key insight: you can bound clock error but never eliminate it, so when ordering must be exact, reach for logical clocks (Lamport for total order, vector clocks for true concurrency detection) instead of wall-clock timestamps. If the conversation turns to databases, explain TrueTime + commit-wait as the way Spanner buys external consistency with a few milliseconds of latency. Then open the simulator: let drift build up, sync, and watch the skew close; switch to Berkeley and watch an outlier node get excluded from the average.

References & further reading#