Clocks and Time in Distributed Systems

A physical clock is a hardware device — typically a quartz crystal oscillator — that counts oscillations and converts that count into a time-of-day value maintained by the operating system. Because no two crystals are manufactured identically, and because temperature, voltage, and age all affect oscillation frequency, every machine's clock ticks at a slightly different rate from "true" time (as defined by a reference standard such as UTC, Coordinated Universal Time, maintained by atomic clocks). The discrepancy between a clock's rate and the true rate is called clock drift, typically bounded by a drift rate ρ, so that over an interval of real time Δt, a clock's reported time can be off by at most ρ·Δt. Typical quartz oscillators drift at roughly 1–100 parts per million (ppm), meaning an unsynchronized clock can drift by several seconds per day. The instantaneous difference between two clocks' readings at the same real moment is called clock skew. Synchronization is the process of periodically adjusting a clock (or computing a correction offset) to keep skew within an acceptable bound. There are two flavors of synchronization: external synchronization, where nodes synchronize to an authoritative external time source (like a GPS or atomic clock reference), and internal synchronization, where a group of nodes agree with each other, without necessarily matching true external time. External synchronization to within bound D means that for any node's clock C and true time t, |C(t) − t| ≤ D. Internal synchronization to within bound D means that for any two nodes' clocks Ci and Cj, |Ci(t) − Cj(t)| ≤ D, even if both are wrong about the actual UTC time. The fundamental obstacle to synchronization is that clock readings must be communicated over a network, and message delay is variable and largely unknown to the receiver ahead of time. If node A sends its clock reading to node B, by the time B receives it, real time has advanced by the message's transit delay — and B has no direct way to know exactly how large that delay was. All physical clock synchronization algorithms are, at their core, strategies for estimating and compensating for this unknown network delay using statistical or worst-case reasoning.

Cristian's algorithm

Cristian's algorithm synchronizes a client to a single, trusted time server, assuming the client can reach the server directly and that round-trip delay is (approximately) symmetric. ``` CristianSync(client, server): T0 <- client.localClock() # time request is sent send REQUEST to server wait for RESPONSE containing T_server T1 <- client.localClock() # time response is received RTT <- T1 - T0

# Assume network delay is symmetric: half of RTT each way estimatedDelay <- RTT / 2 newClientTime <- T_server + estimatedDelay client.setClock(newClientTime) uncertainty <- RTT / 2 # worst-case bound on error return (newClientTime, uncertainty) ``` The reasoning: the server reads its own clock, T_server, at the moment it prepares the response, which occurs somewhere between T0 and T1 in the client's timeline. Cristian's algorithm assumes the request-leg delay equals the response-leg delay, each roughly RTT/2, so it estimates that T_server actually corresponds to client time `T_server + RTT/2`. This estimate is exact only if the network is perfectly symmetric; in practice, the client typically issues several requests and keeps the response with the smallest RTT, since a small RTT bounds the possible asymmetry error more tightly (the true error can be at most RTT/2, so minimizing RTT minimizes the worst-case error bound).

Berkeley algorithm

The Berkeley algorithm was designed for clusters without a reliable external time source. Instead of trusting one authority, an elected time master polls all machines, computes a fault-tolerant average, and tells each machine how to adjust (not overwrite) its clock. ``` BerkeleyMasterSync(master, workers): T_master <- master.localClock() readings <- [ (master, T_master) ] for each worker in workers: T0 <- master.localClock() send TIME_REQUEST to worker wait for TIME_RESPONSE containing T_worker T1 <- master.localClock()

# Estimate worker's time compensated for round-trip delay,

# same idea as Cristian's algorithm (one-way delay ~ RTT/2) adjustedWorkerTime <- T_worker + (T1 - T0) / 2 readings.append( (worker, adjustedWorkerTime) )

# Discard outlier readings (clocks that are wildly off, e.g. faulty) filtered <- discardOutliers(readings) average <- mean( time for (node, time) in filtered ) for each (node, time) in filtered: delta <- average - time # can be negative send ADJUST(delta) to node # node applies delta to its own clock ``` Every participant, including the master, receives a relative adjustment rather than an absolute time. This means the whole cluster converges to a mutually consistent time even if none of them is close to true UTC time — internal synchronization rather than external synchronization. Faulty clocks are excluded from the average using outlier rejection (for example, discarding readings that deviate from the median by more than some threshold), so a single wildly wrong clock cannot drag the entire cluster's time in the wrong direction.

Network Time Protocol (NTP)

NTP is the internet-scale synchronization protocol used almost everywhere. It organizes time sources into a hierarchy of strata:

• Stratum 0: reference clocks themselves — atomic clocks, GPS receivers — not directly on the network.
• Stratum 1: servers directly connected to stratum-0 devices.
• Stratum 2: servers that synchronize with stratum-1 servers, and so on, up to stratum 15.

Each NTP client exchanges timestamped messages with one or more servers and computes both an offset (the estimated difference between the client's and server's clocks) and a round-trip delay, using four timestamps per exchange. ``` NTPExchange(client, server): T1 <- client.localClock() # client send time send REQUEST(T1) to server

# server receives at T2, replies at T3 (both on server's clock) receive RESPONSE(T1, T2, T3) from server T4 <- client.localClock() # client receive time delay <- (T4 - T1) - (T3 - T2) # total RTT minus server processing time offset <- ((T2 - T1) + (T3 - T4)) / 2 return (offset, delay) ``` The offset formula follows from assuming the outbound delay (T2 − T1, measured against true time) and inbound delay (T4 − T3) are equal. Let the true one-way delay be d for both directions, and let the true clock offset (server minus client) be θ. Then: ``` T2 = T1 + d + θ T4 = T3 + d - θ ``` Adding: T2 + T4 = T1 + T3 + 2d, so d = ((T2 - T1) + (T4 - T3)) / 2, matching the `delay` computed above (rearranged). Subtracting: T2 − T4 = (T1 − T3) + 2θ, so θ = ((T2 − T1) − (T4 − T3)) / 2 = ((T2 − T1) + (T3 − T4)) / 2, exactly the `offset` formula. This derivation is exact only under the symmetric-delay assumption; asymmetric routing (common on the real internet) introduces error proportional to the delay asymmetry. A real NTP client does not act on a single exchange. It gathers samples from multiple servers over time, applies a clock filter (keeps the sample with the lowest delay in a window, since low delay bounds worst-case error), performs intersection and clustering algorithms to discard servers whose offsets disagree with the consensus (falsetickers), and then combines the remaining "truechimers" into a weighted average. The local clock is not reset abruptly (which could make time appear to run backwards, breaking applications); instead NTP slews the clock, temporarily speeding it up or slowing it down until the correction is absorbed, or steps it only for large corrections during startup. ``` NTPClientLoop(client, serverPool): loop forever: samples <- [] for server in serverPool: (offset, delay) <- NTPExchange(client, server) samples.append( (server, offset, delay) ) filtered <- clockFilter(samples) # keep low-delay, consistent samples truechimers <- intersectionAlgorithm(filtered) # reject outlier servers combinedOffset <- weightedAverage(truechimers) # weight by inverse delay/dispersion if abs(combinedOffset) > STEP_THRESHOLD: client.stepClock(combinedOffset) # rare: large jump, e.g. at boot else: client.slewClock(combinedOffset, maxRatePpm = 500) # gradual correction sleep(pollInterval) # pollInterval adapts, typically 64s to 1024s ```

Message and time complexity. Cristian's algorithm requires one round trip per synchronization (O(1) messages), so its cost is dominated by network latency, not computation. Repeating k times to select the minimum-RTT sample costs O(k) messages and O(k) time to compare RTTs, still trivial compared to real-world polling intervals. The Berkeley algorithm requires the master to poll n workers, giving O(n) messages per round and O(n log n) time if outlier rejection uses sorting (or O(n) with a linear-time median-based filter); this is efficient because the number of machines in a cluster is typically small (tens to low hundreds) relative to polling frequency. NTP's per-exchange cost is O(1) messages, but a client typically polls m servers (commonly 4–8) per cycle, and the filtering/clustering algorithms operate on the last few samples from each server, giving overall per-cycle cost O(m·w) where w is the filter window size (typically 8) — still small and constant relative to m and w, i.e., independent of network size.

Correctness / error bound reasoning. The central correctness claim for Cristian's algorithm is a bound, not an exact value: if the true one-way delays satisfy d_out + d_in = RTT and each is at least 0, then the true server time at the moment of measurement lies within RTT/2 of the estimate `T_server + RTT/2` in the worst case (when delay is maximally asymmetric, e.g. d_out ≈ 0, d_in ≈ RTT, or vice versa). Formally, if we assume min_delay ≤ d_out, d_in and d_out + d_in = RTT, the maximum possible error between the estimate and the true value is RTT/2 − min_delay, which shrinks toward zero only as RTT shrinks toward the true minimum delay — this is why the algorithm is typically run several times and the response with smallest RTT is kept: it directly minimizes the provable error bound. For NTP, the same symmetric-delay assumption underlies the offset formula derived above; the proof that offset = ((T2−T1)+(T3−T4))/2 exactly cancels the unknown one-way delay d only holds when both directions truly share the same delay d. When delay is asymmetric by an amount ε (d_out = d + ε, d_in = d − ε), algebra shows the computed offset differs from the true offset θ by exactly ε — so asymmetric routing directly injects clock error, and no amount of averaging removes this systematic bias, only random jitter is reduced by averaging. This is an honest limitation: NTP's stated accuracy (commonly 1–50 ms over the public internet, sub-millisecond on a well-controlled LAN) is fundamentally bounded by network path symmetry, not by algorithmic cleverness.

Why physical clocks still cannot totally order events. Even a "perfectly" synchronized system, internally consistent to within bound D, still has D > 0 (D = 0 is physically unachievable because message delay is never zero and jitter is never eliminated). Consider two events e1 on node A and e2 on node B that are, in real causal time, separated by less than D — for instance, A sends a message and B receives it and immediately performs an action, with the whole exchange taking less time than the clock uncertainty D. It is entirely possible for B's timestamp on e2 to be numerically smaller than A's timestamp on e1, even though e1 causally preceded e2 (A's message caused B's action). This is not a bug in the synchronization algorithm; it is a mathematical consequence of D being strictly positive. Formally: physical clock synchronization can guarantee |Ci(t) − Cj(t)| ≤ D for all t, but it cannot guarantee that timestamp order matches causal (happens-before) order whenever two causally related events occur within a real-time window smaller than D. This is precisely the gap that motivates purely logical mechanisms — Logical Clocks and Lamport Timestamps — which order events by causality rather than by wall-clock value, sidestepping the synchronization-error problem entirely.

Suppose a client synchronizes with an NTP server three times in quick succession, and we want to see how the algorithm behaves, including a case where the naive Cristian-style estimate would be misleading without the minimum-RTT selection rule.

(All times in seconds, using a hypothetical "true" clock timeline for illustration; the server clock genuinely runs 0.025 s ahead of the client's clock in this example, and network jitter varies attempt to attempt.) Applying the offset formula to attempt 1: offset = ((1000.050 − 1000.000) + (1000.051 − 1000.120)) / 2 = (0.050 − 0.069) / 2 = −0.0095 — wait, let's recompute carefully using the actual numbers: (T2 − T1) = 0.050, (T3 − T4) = 1000.051 − 1000.120 = −0.069. Sum = −0.019, divided by 2 = −0.0095 s. This illustrates a key point: attempt 1's large asymmetric delay (a slow return trip) badly distorts the offset estimate, even though it "looks like" a normal exchange. Redo attempt 2: (T2 − T1) = 0.020, (T3 − T4) = 2000.021 − 2000.045 = −0.024. Sum = −0.004, offset = −0.002 s. Much closer to the true value. Redo attempt 3: (T2 − T1) = 0.500, (T3 − T4) = 3000.501 − 3000.560 = −0.059. Sum = 0.441, offset = +0.2205 s — wildly wrong, driven by a huge, asymmetric network delay spike (a queuing delay burst on the return path). An NTP client's clock filter would examine the delay column (0.120, 0.045, 0.560) and retain the sample with the smallest delay, attempt 2 (delay = 0.044 s), because low delay bounds the worst-case asymmetry error most tightly. It would discard attempts 1 and 3 as unreliable, even though all three "succeeded" at the transport level. This demonstrates why NTP never trusts a single exchange, and why minimum-delay selection — not averaging all samples blindly — is the statistically sound approach: averaging attempt 1, 2, and 3's offsets naively would give (−0.0095 + −0.002 + 0.2205)/3 ≈ +0.0697 s, a badly biased result compared to trusting attempt 2's −0.002 s, which is much closer to reasonable expectations for a well-behaved link.

The problem of synchronizing distributed clocks became formally important as computer networks grew beyond single machines in the 1970s and 1980s, but its intellectual roots trace to the deeper realization that "simultaneity" is not absolute — an idea most famously associated with relativity, later reinterpreted for the very different setting of message-passing computer networks.

Nearly every large-scale distributed system depends on some form of physical time synchronization, even when it also uses logical mechanisms for correctness-critical ordering. Operating systems ship with NTP or its successor, chrony, running as a background daemon to keep the local clock aligned with public time servers. Financial exchanges use highly precise time synchronization — often via Precision Time Protocol (PTP), a refinement of NTP-style ideas for sub-microsecond accuracy — because regulations require verifiable, accurate ordering of trades across matching engines. Distributed tracing and observability tools (used to debug Partial Failure scenarios in microservice architectures) stitch together spans from many machines using timestamps, and inaccurate clocks directly translate into misleading trace visualizations. Certificate validation (TLS), Kerberos authentication, and OAuth token expiry all silently assume that clocks across communicating parties are reasonably close, and clock skew is a frequent, hard-to-diagnose cause of authentication failures in real production incidents. Google's Spanner database uses a system called TrueTime, which does not report a single timestamp but an interval [earliest, latest] guaranteed to contain the true time, explicitly encoding the uncertainty this article describes, and it waits out that uncertainty window before committing certain transactions to guarantee external consistency. Distributed databases such as CockroachDB adopt similar "commit-wait" strategies inspired directly by Spanner's approach. Understanding physical clock synchronization is thus a prerequisite for understanding both the practical operation of nearly all networked infrastructure and the theoretical motivation for logical clocks, vector clocks, and hybrid logical clocks that layer causal reasoning on top of (or instead of) wall-clock time.

Ask the tutor: How does Google's TrueTime system use explicit clock uncertainty intervals to guarantee transaction ordering in Spanner?