Bounded Clock Uncertainty and the Commit-Wait Rule

Every argument in this cluster so far has treated clock error as something to be minimized and then worked around. There is a different design: measure the error, expose it as an explicit interval, and use the interval as a primitive that the system’s algorithms reason about. If the bound is small and the system is willing to wait for it, physical time becomes a usable ordering authority across machines, and the ordering is external — it agrees with an observer’s real-time view of the system.

The interval, not the instant

A bounded-uncertainty clock returns two values: earliest and latest, with the guarantee that the true time lies in [earliest, latest]. The width of the interval is the uncertainty ε. A timestamp is then an interval, and the system’s comparisons are three-valued: two intervals that do not overlap are ordered, and two that overlap are not.

This is the honest form of what an ordinary clock hides. An NTP-synchronized host knows its root distance and could in principle report it, as described in The NTP Four-Timestamp Exchange and Its Asymmetry Limit, and a host with a hardware reference knows the resolution and stability of that reference. The bounded-uncertainty design makes that knowledge part of the API rather than an operational footnote, which changes what the layers above can guarantee.

The infrastructure that produces a small ε is not exotic in principle, only in deployment. A reference clock — an atomic clock or a GPS receiver — is attached to a set of time servers, and those servers compare their own readings and refuse to serve an interval unless a majority of references agree. A machine that loses its reference is not trusted; it is removed from the set, and its clock is considered faulty until it is revalidated. The comparison between servers is itself a network exchange with a delay, so the interval must include the delay, which is why the reference servers are placed with short, symmetric paths to the machines that use them.

Published descriptions of the system that introduced this design report an uncertainty typically in the range of a few milliseconds, growing over time between reference updates and shrinking when a reference is available. The figure is a property of that deployment’s network and hardware, not of the algorithm, and the algorithm is correct for any bound, including a large one. A large ε does not produce wrong answers; it produces long waits, which is the trade this article is about.

Choosing a timestamp the coordinator can defend

A write needs a timestamp s with two properties: it must not be smaller than any timestamp already assigned elsewhere, so that the transaction order does not go backwards, and it must not be further ahead of the coordinator’s true time than the uncertainty, so that the later wait is bounded.

Given an interval [earliest, latest], the choice is s = latest. The value latest is an upper bound on the true time, so it cannot be behind a timestamp that another node assigned from an interval that overlaps this one. The cost of that safety is that s may be up to ε ahead of the coordinator’s true time, which is precisely the amount that commit-wait must later absorb.

The lower bound earliest would be immediately safe in the other direction, since it is certainly not in the future. It is also not usable as a write timestamp on its own: a node whose clock runs behind would produce an earliest below timestamps already committed by a node whose clock runs ahead, and the order would reverse. The asymmetry is deliberate. Writes take the upper bound and pay a wait; reads that can tolerate staleness take the lower bound and pay nothing.

Commit-wait, and why it cannot be skipped

A transaction that commits at s cannot be reported as committed until the true time everywhere exceeds s. Otherwise a client could learn that the transaction committed and then issue a read that is served by a replica whose clock has not yet reached s, and the read would miss the write despite happening after the client learned of the commit. That would violate external consistency: the system’s ordering would disagree with the ordering a real-time observer sees.

Commit-wait implements the delay. After choosing s, the coordinator waits until its local clock’s earliest exceeds s, then releases the commit. Because s was latest and the interval has width ε, the wait is at most ε of real time. In a system with a few milliseconds of uncertainty, the wait is a few milliseconds; in a system with a hundred milliseconds, the wait is a hundred milliseconds and the write latency carries it.

def commit_wait(clock, s):
    """Block until the true time is certainly past s."""
    while clock.now().earliest < s:
        sleep_until(clock.now().earliest)   # wake when the bound moves
    return True

The sleep is not a busy wait in a real implementation; the clock’s earliest advances with the hardware counter, so the implementation can compute the deadline and arm a timer. The correctness requirement is only that the loop does not exit before earliest exceeds s, and that earliest is a genuine lower bound.

Commit-wait is the price of external consistency. A system that skips it and uses raw physical timestamps for commit has a window equal to the clock uncertainty in which a reader can observe the system in a state that contradicts the order of the commits it has acknowledged. Systems that use logical clocks avoid the window entirely by not claiming a relation to physical time, and they pay for it by having timestamps that are not dates.

Reads, snapshots, and the same bound

A read at timestamp T must be served by a replica that has applied every transaction committed at or before T. The replica tracks a safe time: the largest timestamp such that all transactions below it are known to be applied. A read that arrives with T above the safe time waits until the safe time advances, which happens as the replica’s own clock advances and as pending transactions are applied.

The same bound appears on the read path in a different form. A read timestamped at the current latest is safe only after the wait for that value has elapsed; a read timestamped below the coordinator’s current earliest is safe immediately, because every commit at or below that value has already finished its wait. The first is fresh and slow, the second is stale by up to ε and fast. The choice between them is a latency-versus-freshness decision made per read, and it is the read-side analogue of the write-side wait.

This is also why the mechanism suits a system whose clock bound is small. The design does not eliminate the physical clock’s error; it converts the error into a delay that is paid on writes and, optionally, on reads. Doubling the accuracy halves the delay. A deployment that cannot achieve a small bound can still use the algorithm, and its transactions will be correct and slow.

Where the bound comes from, and how it fails

The bound is an engineering claim, and its failure modes are the interesting part. A time server whose reference is wrong can serve a narrow interval around a wrong value, which is worse than serving a wide interval around a right one, because the narrow interval is trusted. The defence is redundancy: several references, majority agreement, and removal of any server whose interval disagrees with the majority. The comparison is done continuously, not once at startup.

A machine that drifts between reference updates widens its own interval, which is safe but slow. A machine whose oscillator fails can jump, and the interval must widen to cover the possibility until a reference confirms the reading. The interval arithmetic is what makes these failures visible: a broken clock produces a wide interval, and the system’s latency degrades before its correctness does.

The failure that the design cannot survive is a bound that is wrong rather than wide — an interval that excludes the true time. That requires the reference itself to be wrong or the comparison to be subverted, and it is the reason the reference set is small, physically controlled, and cross-checked.

What the construction buys

With a bounded clock and commit-wait, a system gets a total order on transactions that matches real time as an external observer would see it, without a centralized sequencer for every write and without a logical clock’s disconnection from dates. The order is established by the timestamps themselves, and the wait enforces the relation between the timestamp and the moment of visibility, in contrast to the log-based order of Total-Order Broadcast.

The cost is a latency floor equal to the uncertainty, paid on every write and on reads that want freshness. That floor is a hardware and network property, and it is the honest price of using physical time as an ordering authority. The alternative — logical clocks and explicit ordering protocols — has no such floor and no claim to real-time order. Choosing between them is choosing which guarantee the application actually needs, and the rest of this cluster is the catalogue of what each choice provides.