Elijah's Notes

Failure Detectors, Leases, and Leader Election

7 min read

Purpose

The machinery underneath consensus and critical-state management: how a system decides someone is dead, how it grants time-bounded authority, and how it keeps two nodes from both acting as leader. The theory says perfect detection is impossible; the engineering answer is to make wrong detection safe and merely slow.

Suspicion is all you get

In an asynchronous system — unbounded message delay, unbounded processing pauses — a crashed process and a slow one are indistinguishable by any observation. This is the operational content of the FLP impossibility result (Fischer, Lynch, Paterson 1985): deterministic consensus is unsolvable with even one possible crash, because no protocol can safely wait out the ambiguity. Every real “failure detector” is therefore a suspicion mechanism whose verdicts can be wrong, and every correct system design starts from the question: what happens when it is?

Chandra and Toueg (1996) turned this into a taxonomy by scoring detectors on two axes — completeness (crashed processes get suspected) and accuracy (correct processes do not) — and asking how much accuracy consensus actually needs. The hierarchy: a perfect detector (never suspects a correct process) requires synchrony no real network has. The consequential class is eventually strong : suspicion can be arbitrarily wrong for an arbitrary prefix, as long as eventually some correct process stops being suspected by anyone. Their two theorems frame all of practice: consensus is solvable with plus a majority of correct processes, and (with Hadzilacos) nothing weaker suffices — /, the “eventual leader oracle,” is the weakest detector for consensus. The translation: a system does not need reliable failure detection, only an eventually-stable leader hint plus quorums — which is exactly the shape of Paxos and Raft.

Practical detectors approximate with heartbeats and timeouts. The tuning tension is fundamental: short timeouts detect fast but suspect wrongly under load spikes (and a wrongly-suspected leader triggers a gratuitous election, which causes more load — a classic metastable loop); long timeouts are calm but leave the system leaderless longer after real crashes. Two refinements are standard. The phi-accrual detector (Cassandra, Akka) replaces the binary verdict with a suspicion level computed from the observed heartbeat-interval distribution, letting the timeout adapt to current network behavior. SWIM-style protocols decouple detection (randomized pings, with indirect probes through third parties before declaring suspicion) from dissemination (gossip), keeping per-node load constant as the cluster grows.

stateDiagram-v2
    [*] --> Alive
    Alive --> Suspected: missed heartbeats / phi crosses threshold
    Suspected --> Alive: heartbeat or indirect ack arrives
    Suspected --> Declared_Dead: suspicion confirmed, disseminate
    Declared_Dead --> [*]

Suspicion is a reversible state — the Suspected -> Alive edge is what makes wrong verdicts survivable, and everything downstream (elections, leases, fencing) exists to make traversing it cheap.

Leases: authority with an expiry date

A lease (Gray and Cheriton 1989) is a grant of authority — cache validity, lock ownership, leadership — valid for a bounded time and renewable by communication. The crucial property: expiry needs no communication. If the holder crashes or partitions, the grantor waits out the term and reassigns; a lock with a timeout is a lease. Correctness does not require synchronized clocks, only bounded drift rate: grantor and holder each measure the term on their own clock, and if clocks tick within (say) 1% of true rate, the grantor adds a small margin and the holder conservatively expires early. Bounded-rate assumptions are among the safest in systems practice — this is the same clock discussion as Clocks, but leaning only on rates, not on synchronization.

The stalled leaseholder

The trap is what the holder does at the edge. Kleppmann’s distributed-locking critique: a client acquires a lease, then stalls — GC pause, VM migration, swap storm — past its expiry. The lease service correctly reassigns. The stalled client resumes believing it holds the lease (its check ran before the pause) and writes to shared storage: two writers, data corrupted, and no amount of timeout tuning fixes it, because the pause can exceed any timeout.

The fix is the fencing token: the lease service issues a monotonically increasing number with each grant, every write to the protected resource carries it, and the resource rejects tokens older than the highest seen. The stale writer’s token is stale; the write bounces.

sequenceDiagram
    participant C1 as Client 1
    participant L as Lease service
    participant S as Storage

    C1->>L: Acquire lease
    L-->>C1: Granted, token 33
    Note over C1: GC pause exceeds lease term
    L->>L: Lease 33 expires
    participant C2 as Client 2
    C2->>L: Acquire lease
    L-->>C2: Granted, token 34
    C2->>S: Write (token 34)
    S-->>C2: OK
    Note over C1: Pause ends, still believes it holds the lease
    C1->>S: Write (token 33)
    S--xC1: Rejected: 33 < 34

The same mechanism recurs as Raft’s term numbers, ZooKeeper’s zxid epochs, and Chubby’s lock generation numbers — versioned authority, checked at the point of effect, is the universal answer to “the detector was wrong and the old leader is still moving.”

The safety/liveness split in one sentence

Timeouts and elections provide liveness (a dead leader is eventually replaced), while quorums and fencing provide safety (a falsely-suspected leader cannot do damage) — wrong suspicion may slow the system, but must never corrupt it.

Leader election in practice

Chubby (Burrows 2006) is the canonical packaging: a Paxos-replicated, five-node lock service exposing a small filesystem with advisory locks, built explicitly for coarse-grained use — locks held for hours, not milliseconds, so the cost of an election amortizes. Clients hold sessions maintained by keepalive RPCs with a ~12-second lease; if a session’s lease lapses, the client enters a ~45-second grace period (“jeopardy”) in which caches are disabled but handles survive, masking brief master failovers. Applications elect leaders by racing to acquire a lock file: GFS and Bigtable both pick masters this way, and the winner writes its identity into the file for discovery. Ephemeral files double as liveness signals. Burrows’s deployment observation is a design lesson in itself: a service intended for election and configuration became, in practice, a name server — coarse coordination points attract every use that needs “one agreed value, rarely changed.”

ZooKeeper’s election recipe: every candidate creates a sequential-ephemeral znode; the lowest sequence number is leader; each other node watches only its immediate predecessor. When the leader’s session dies, its znode vanishes and exactly one successor wakes — avoiding the thundering herd of everyone re-racing. etcd exposes election directly over its lease API: campaign on a key bound to a lease, leadership persists while the lease is kept alive, and the key’s creation revision serves as the fencing token. Raft internalizes election into the consensus protocol: followers that miss heartbeats become candidates after a randomized timeout (the randomization is the entire split-vote-avoidance mechanism), majority vote elects, and the incremented term number fences the old leader — any RPC carrying a stale term is rejected by protocol rule.

All three reduce to the same layering:

suspicion:  heartbeats + timeouts        (approximate an eventual leader hint)
liveness:   election on suspicion        (randomized or ordered tie-breaking)
authority:  lease with bounded term      (self-expiring, renewable)
safety:     epoch/term/fencing token     (checked by every downstream effect)

A coordination service sells this stack as a primitive so that applications above it — masters, shard owners, singleton workers — inherit consensus-grade safety while writing only lock-acquire loops. That inheritance has a condition: the resources those applications write to must check the fencing token too. A leader elected perfectly through Chubby can still corrupt a storage system that accepts unfenced writes; the election machinery bounds who may act, but only token checks at the data bound what a zombie can do.

Sources

Graph View