Wall-Clock Timestamps Do Not Order Distributed Events

A single computer can answer the question “which of these two things happened first” by reading its clock, because one clock is monotone and one process observes both events. Add a second computer and the question becomes unanswerable in the obvious way. Each machine has its own oscillator, its own notion of the current instant, and its own error relative to every other machine. Sorting a log of timestamped records from both machines produces a total order, and that total order is frequently wrong.

Two timelines that only resemble each other

Every general-purpose computer derives wall-clock time from a quartz oscillator, usually a small crystal cut to resonate at a nominal frequency such as 32,768 Hz or 25 MHz. The nominal frequency is not the actual frequency. Manufacturing tolerance, temperature, supply voltage, and aging all shift it, and the shift is specified in parts per million. A crystal specified at ±20 ppm accumulates up to about 1.7 seconds of error per day if left free-running; a ±50 ppm part accumulates about 4.3 seconds. Higher-grade oscillators, oven-controlled or rubidium, reduce this by orders of magnitude and cost correspondingly more, which is why ordinary servers do not have them.

Left alone, two machines therefore diverge at a rate set by the difference of their frequency errors, and the divergence is unbounded. Synchronization exists to bound it. The Network Time Protocol estimates each machine’s offset from a reference and steers the local clock toward it, either by stepping the clock (jumping it, possibly backwards) or by slewing it (running the clock slightly fast or slow until the offset is consumed). Between synchronization exchanges, the offset grows again at the drift rate, so the achievable accuracy is always a function of how long ago the last correction was applied and how good that correction was.

The result is that “the time” is not a property of the system. It is a property of one machine at one moment, with an error bar attached that the machine usually does not report.

What a timestamp actually records

A timestamp written into a record is produced by a call such as clock_gettime(CLOCK_REALTIME, &ts), which reads the kernel’s civil-time clock. That value is a cached software quantity, maintained from a hardware counter plus a correction the kernel applies from the last synchronization, and adjusted by any pending slew. Three separate errors enter before the value reaches the record:

• The offset between the local clock and the reference at the last correction.
• The drift accumulated since that correction.
• The delay between the moment the event happened and the moment the program read the clock, which includes scheduling delay and, for a network event, the kernel’s receive timestamp versus the application’s read.

The third item is not a clock error at all, but it corrupts the same comparison. A message can arrive at a host at one instant and be stamped a millisecond later because the receiving thread was not scheduled; a fast sender and a slow receiver can invert the apparent order of two events that were ordered in real time.

The anomaly, made concrete

Consider two nodes, A and B, with A’s clock reading 100 ms ahead of B’s. A writes a record at true time T and B writes a record at true time T + 10 ms in direct response to receiving A’s message. The two timestamps are T + 100 ms and T + 10 ms. Sorting by timestamp places B’s record first, although B’s record was caused by A’s. No amount of care inside either program fixes this, because the error is in the clocks, not in the code.

The consequence is not merely a misordered log. Any rule of the form “the record with the larger timestamp wins” resolves conflicts by clock error rather than by causality. A last-write-wins register that compares wall-clock timestamps will discard the later of two writes whenever the writer of the earlier write had a clock running ahead. This is the failure mode that motivates every logical clock discussed in the rest of this cluster: Lamport’s happens-before relation exists precisely to order events by communication rather than by oscillator.

The same problem appears at a smaller scale inside a single host. Two processes on one machine read the same clock, so they agree on ordering, but if the clock is stepped backwards by a synchronization correction, a later event can receive an earlier timestamp. Programs that measure durations with the civil clock therefore report negative elapsed times, which is why interval measurement uses a monotonic clock instead, as covered in Monotonic and Civil Clocks in Running Programs.

Why the offset cannot be driven to zero

Synchronization protocols estimate offset by exchanging timestamps and assuming something about the path. In the simplest exchange, a client sends a request stamped with its local send time, a server stamps its receive and transmit times, and the client stamps the arrival. If the request and response take the same time to traverse the network, the offset is computable exactly from the four values. Real paths are asymmetric: queueing, routing changes, and different upstream and downstream capacities make the two directions differ.

The error in the estimate is exactly half the asymmetry of the path: if the outbound leg takes d1 and the inbound takes d2, the computed offset is off by (d1 - d2)/2. That quantity is not observable from the four timestamps, which is why the exchange can only bound the offset from above, never determine it exactly. RFC 5905 handles this by computing, alongside the offset, a root distance that accumulates the measured round-trip delay and the claimed error of each server in the synchronization chain. A client several strata away from a reference carries a larger bound, and a well-behaved client refuses to trust a source whose bound grows too large. The bound is honest but not small: a server synchronized across a wide-area path carries a root distance on the order of milliseconds, and the asymmetry term can be a substantial fraction of the round-trip time.

Physical limits sit underneath this. Light travels about 200 kilometres per millisecond in fibre, so a path of 10,000 km contributes at least 50 ms of one-way delay, and any asymmetry of a few milliseconds across that path is worth hundreds of kilometres of apparent distance. No protocol removes the asymmetry; it can only measure the round trip and divide.

Interval timestamps and what they support

The productive response is to stop treating a timestamp as a point. A reading with a known error bound is an interval, and comparisons are then three-valued: definitely earlier, definitely later, or overlapping. The last case is the honest answer whenever the two error bars intersect, and it corresponds to the region where causality cannot be inferred from time.

def compare(a, b):
    """a and b are (reading, bound) pairs in the same unit."""
    lo_a, hi_a = a[0] - a[1], a[0] + a[1]
    lo_b, hi_b = b[0] - b[1], b[0] + b[1]
    if hi_a < lo_b:
        return 'a before b'
    if hi_b < lo_a:
        return 'b before a'
    return 'indeterminate'   # the error bars overlap

With bounds, a system can still do useful work. Ordering records that are far apart in time is safe. Detecting that two records are concurrent is possible when their intervals overlap and no causal path connects them. Snapshot reads can be made consistent by waiting until the bound has certainly passed, which is the mechanism behind bounded-uncertainty systems discussed in Bounded Clock Uncertainty and the Commit-Wait Rule.

What intervals cannot do is provide a total order that matches causality at arbitrary precision. That requires either a communication step that establishes the order directly, as a total-order broadcast does, or a logical counter that increments on every causal step. Both are constructions on top of message passing, not improvements to the crystal.

The residue

Wall-clock time remains indispensable for the things it does well: human-readable logs, retention windows, cache expiry where a small error is harmless, and ordering events on one machine. Its failure is specifically in the cross-machine case, and the failure is silent, because the sorted output looks exactly like a correct one. Systems that need cross-machine order either accept the error and design around it, or they stop using physical time as the ordering authority and use causality instead.