Why Consensus Does Not Trust Clocks: Leases
On this page
Learning Objective
Explain why consensus algorithms use logical clocks rather than wall-clock time for safety, identify the specific places where real systems do depend on physical time and what they assume, and describe how Spanner's TrueTime makes a clock-based guarantee sound by bounding and exposing its own uncertainty.
Concept Explanation
A recurring design rule across every algorithm in this course is that safety never depends on clocks. Raft orders events by term, Paxos by ballot number, ZAB by zxid, and all three are logical counters that advance because something happened, not because time passed. The reason is that physical clocks on separate machines are unreliable in ways that are hard to bound: NTP can step a clock backwards or forwards abruptly when correcting drift, virtual machine clocks drift badly and jump after live migration, a machine with a failed time source can drift by seconds per day, and leap seconds have historically caused widespread failures. An algorithm whose correctness depends on two machines agreeing about the current time inherits every one of those failure modes, whereas a logical counter is correct even if every clock in the cluster is wrong by hours.
That said, real systems do use physical time, and being precise about where is what separates a sound design from a fragile one. Election timeouts use physical time, but only for liveness: a clock that runs fast causes unnecessary elections and a clock that runs slow delays failover, and neither can cause two leaders or lost data, because winning an election still requires a majority of votes. Session and lease expiry in coordination services uses physical time, and it is the mechanism that decides when an ephemeral key disappears, which is why a garbage collection pause longer than the session timeout is indistinguishable from a crash. Client request timeouts use physical time and affect only the client. In all three cases a wrong clock costs availability or unnecessary failover, never correctness.
There is exactly one common case where physical time is load-bearing for safety, and it should be recognised as such whenever it appears: the lease-based read. A leader that serves reads locally while it believes its leadership lease is unexpired is relying on followers not electing a new leader before that lease ends, and that comparison happens on two different machines with two different clocks. If a follower's clock runs ahead enough, it can elect a new leader while the old leader still considers its lease valid and continues serving reads from state the new leader has already superseded, producing a stale read that violates linearisability. This is why implementations that offer lease reads bound the lease well inside the election timeout, why they document the clock assumption explicitly, and why ReadIndex, which confirms leadership with actual messages instead of with time, remains the safer default.
Google Spanner is the well-known system that deliberately makes clocks load-bearing, and the interesting part is how it handles the honesty problem. Rather than pretending its clocks are correct, TrueTime exposes uncertainty as a first-class value: a call to TT.now() returns an interval with an earliest and a latest bound, guaranteed to contain the true time. The interval width, epsilon, is kept small - Google reported an average of a few milliseconds and a maximum around seven - by deploying GPS receivers and atomic clocks in every datacentre and having servers poll multiple time masters. Spanner then uses this to provide external consistency through commit wait: after assigning a transaction a commit timestamp, it deliberately waits until the timestamp is definitely in the past according to the latest bound before making the transaction visible. That wait, typically a few milliseconds, guarantees that any transaction starting afterwards receives a strictly later timestamp, so timestamp order matches real-world order globally.
The lesson generalises beyond Spanner and is the practical takeaway. Using time for correctness is possible but requires bounding and exposing the uncertainty rather than ignoring it, and paying the cost of that bound explicitly. Spanner pays with specialised hardware in every datacentre and with a deliberate delay on every commit. A system without that infrastructure should keep time out of its safety argument entirely and use logical clocks, treating physical time only as a hint about liveness. When reviewing a distributed design, the productive question is not whether it uses clocks but whether any safety property would be violated if one machine's clock were wrong by thirty seconds, and if the answer is yes, whether the uncertainty is bounded, measured, and paid for.
| Use of Time | What Depends On It | Cost If the Clock Is Wrong |
|---|---|---|
| Raft terms, Paxos ballots, zxids | Nothing: these are logical counters, not time | None, correctness is unaffected by any clock error |
| Election and heartbeat timeouts | Liveness only | Unnecessary elections or delayed failover; never two leaders |
| Session and lease expiry | When ephemeral keys are deleted | Premature failover, or a slow client treated as dead |
| Lease-based reads | Safety: linearisability of reads | A stale read if a follower's clock outruns the leader's lease |
| Spanner commit wait | Safety: external consistency of timestamps | Bounded by design; TrueTime exposes and waits out its own uncertainty |
Worked Example: Where Clock Skew Does and Does Not Break Things
Running the same thirty seconds of clock error through four different mechanisms shows clearly which parts of a consensus system are immune to it and which are not.
# Node C's clock is 30 SECONDS AHEAD of the rest of the cluster.
# --- 1. RAFT TERM ORDERING: completely unaffected ---
A (leader, term 7) -> C : AppendEntries(term=7, ...)
C compares 7 against its own currentTerm. It never consults a clock.
# Terms advance because an ELECTION happened, not because time passed.
# Every clock in the cluster could be wrong by a year with no effect on
# safety whatsoever. This is why logical clocks are the default.
# --- 2. ELECTION TIMEOUT: liveness only ---
# C's fast clock makes its 300ms election timeout elapse in ~300ms of
# ITS time, which is fine - a timeout measures an INTERVAL, and only a
# wrong CLOCK RATE (not a wrong absolute time) distorts an interval.
# Even if C's rate were wrong and it started elections constantly:
# C still needs a MAJORITY of votes to become leader.
# Voters still apply the up-to-date log check.
# Worst case: needless elections. There is no path to two leaders.
# --- 3. LEASE-BASED READ: SAFETY genuinely at risk ---
Leader A holds a read lease granted at A's t=1000, valid 10s -> t=1010.
Follower C, 30s ahead, sees its own clock at t=1035.
C concludes: "the lease expired 25 seconds ago" -> starts an election.
C wins (it has a current log), becomes leader, and commits x=2.
Meanwhile A's own clock reads t=1004: A still believes its lease is
valid and serves a local read returning x=1.
# A STALE READ has been served AFTER a newer value was committed.
# Linearisability is violated, and no message was dropped or delayed.
#
# Mitigations used in practice:
# - bound the lease to a FRACTION of the election timeout, so skew
# must exceed that margin to cause harm (TiKV does this)
# - subtract an assumed maximum clock skew from the lease validity
# - or use ReadIndex instead, which confirms leadership with actual
# MESSAGES rather than with time, and is immune to skew entirely
# --- 4. SPANNER: time made load-bearing, honestly ---
# TrueTime does not return a timestamp. It returns an INTERVAL that is
# GUARANTEED to contain the true time:
TT.now() -> [earliest=1000.000, latest=1000.006] # epsilon = 6ms
# Commit protocol:
s = TT.now().latest # pick a timestamp definitely >= real now
commit_transaction(timestamp=s)
while TT.now().earliest < s: # COMMIT WAIT: block until s is
sleep(0.1ms) # definitely in the PAST everywhere
make_visible()
# The wait (a few ms) guarantees that any transaction STARTING after
# this one becomes visible must receive a strictly greater timestamp,
# anywhere on Earth. Timestamp order then matches real-world order
# globally: external consistency.
#
# The price is explicit and paid in two currencies:
# - GPS receivers and atomic clocks in EVERY datacentre, to keep
# epsilon in the single-digit milliseconds
# - a deliberate few-millisecond delay on EVERY commit
# Without that hardware, epsilon would be hundreds of milliseconds and
# commit wait would make the system unusable - which is precisely why
# systems lacking it keep time out of their safety argument entirely.
# THE REVIEW QUESTION TO ASK OF ANY DESIGN:
# "Which safety property breaks if one machine's clock is wrong by
# 30 seconds?"
# If the answer is "none", clocks are being used for liveness only:
# correct. If the answer names a property, that uncertainty must be
# bounded, measured, and paid for the way Spanner pays for it.Real-World Examples
- Google Spanner, described in the 2012 OSDI paper, deploys GPS receivers and atomic clocks in every datacentre so that TrueTime can bound clock uncertainty to single-digit milliseconds, and uses commit wait to delay making a transaction visible until its timestamp is definitely in the past. This is the clearest production example of making time load-bearing for a safety property by bounding and paying for the uncertainty rather than assuming it away, and the hardware investment is a direct measure of what that guarantee costs.
- The 2016 leap second caused a documented outage at Cloudflare when code in its DNS resolver computed a time interval that went negative during the inserted second, producing errors for a subset of queries. The incident is a compact illustration of why consensus algorithms keep clocks out of their safety arguments: a single unexpected discontinuity in wall-clock time produced a failure in code whose logic was otherwise correct, and the same discontinuity would have been entirely invisible to a system ordering events by logical counters.
Review Questions & Answers
Because a logical counter advances only when something happens - an election begins, a proposal is made - and is therefore correct no matter how wrong any machine's clock is. Physical clocks can step backwards or forwards under NTP correction, drift badly on virtual machines, jump after live migration, and misbehave around leap seconds, and an ordering built on them would inherit every one of those failure modes. Since the purpose of the counter is to establish which of two events supersedes the other, and that relationship is causal rather than temporal, a counter incremented by the protocol itself is both sufficient and strictly more robust.
Because becoming leader requires a majority of votes, and the clock plays no part in that decision. A node with a fast clock times out sooner and starts elections more often, but each attempt still needs a majority of peers to grant votes, and each of those peers still applies the up-to-date log check and the one-vote-per-term rule. So the cost of a bad clock is extra elections and the availability gaps they cause, never two leaders committing simultaneously. That separation - time influencing when things are attempted, quorum deciding whether they succeed - is the design pattern that keeps clock error confined to liveness.
The lease is granted at one moment on the leader's clock and evaluated for expiry on followers' clocks. If a follower's clock runs ahead, it can conclude the lease has expired while the leader still considers it valid. The follower participates in electing a new leader, which commits a new value, while the old leader continues serving reads from its local state without any network confirmation, because it believes its lease protects it. A client reading from the old leader then receives a value that has already been superseded by a committed write, which is a stale read and a linearisability violation. Nothing was dropped or delayed; the two machines simply disagreed about the time.
TrueTime returns an interval with an earliest and a latest bound, guaranteed to contain the true time. Returning an interval makes the uncertainty explicit and usable rather than hidden: an ordinary clock call returns a single value with unknown and unbounded error, so any algorithm built on it is silently assuming something it cannot verify. With an interval, Spanner can reason soundly about what is definitely in the past, which is exactly what commit wait needs. The honesty is the mechanism: by refusing to pretend it knows the exact time, TrueTime lets an algorithm make a correct guarantee despite imperfect clocks.
Because the guarantee is bought with GPS receivers and atomic clocks in every datacentre, which is what keeps the uncertainty interval in single-digit milliseconds, and with a deliberate commit wait on every transaction. Without that hardware the interval would be hundreds of milliseconds or worse, and waiting it out on every commit would make the system unusably slow, so the same design is not merely expensive elsewhere but ineffective. A system lacking it should keep time out of its safety argument entirely: order events with logical counters, use physical time only for timeouts and expiry where errors cost availability, and prefer ReadIndex over lease reads so that leadership is confirmed by messages rather than by clocks.