Leader Leases and Fencing Tokens in Failover

Promoting a follower is the moment a replicated system is most likely to corrupt itself. The old leader may be alive, unreachable, and still convinced it holds the role. It has clients connected to it, buffers full of writes it has not yet shipped, and no way to learn that a replacement has taken over. Every failover mechanism is an answer to the question of how to stop that node from continuing to act.

The demoted leader that does not know

Consider the simplest single-leader setup: one leader, one follower, and an operator who notices the leader is unreachable and promotes the follower. The old leader is not dead. It sits behind a failed switch, or in a partition, or paused in a long garbage collection, or suspended by a hypervisor. From its own point of view nothing has changed.

Two failure modes follow. The first is divergent writes: the old leader accepts writes, the new leader accepts different writes for the same keys, and when the partition heals there are two histories with no ordering between them. The second is worse and less visible: both nodes believe they are leader and both write to the same shared resource — a block device, a network file system, a downstream service that is not itself replicated. The downstream resource has no concept of leadership and will happily accept writes from whichever connection arrives first.

A timeout does not fix this. “If I have not heard from the leader in five seconds, promote the follower” is a statement about the observer’s knowledge, not about the leader’s state. The old leader has no obligation to stop writing just because someone else stopped hearing from it.

Leases as a bounded window

A lease is a promise with a deadline. The leader is granted the right to act until time t; before t it may issue writes without asking anyone, and after t it must stop until it renews. The follower is told the same deadline, and may take over after t. The mechanism works because both sides agree on when the old grant expires, so there is no need for the old leader to be reachable at the moment of takeover.

The correctness of a lease rests on two assumptions that are easy to state and hard to guarantee. First, the clocks of leader and follower must not drift apart by more than the safety margin built into the lease. Second, a node must not be able to pause for longer than the lease term and then resume believing no time has passed. The second assumption is the one that fails in practice: a virtual machine can be suspended, a process can be stopped by a debugger or a stop-the-world collector, and the wall clock it reads afterwards has moved on while its own notion of elapsed time has not.

For that reason lease-based systems subtract a safety margin from the nominal term. A lease of ten seconds might be treated as valid for eight, with the remaining two covering clock skew and scheduling delay. The margin is a guess about the worst case, and the guarantee is only as good as that guess. Distributed file systems have used this structure since the 1980s for cache consistency, where the lease is short and the consequence of expiry is merely a cache miss rather than a diverged write.

Fencing: making the old leader harmless

A fencing token removes the need to trust the old leader’s clock or its cooperation. Each time a node is granted leadership it receives a monotonically increasing number — a token. Every write the leader sends to a shared resource carries the token. The resource rejects any write whose token is lower than the highest it has already seen.

The consequence is that the old leader can keep running, keep accepting client requests, and keep sending writes. They are simply refused. Nothing about the old leader’s internal state has to be correct, because the resource enforces the ordering. This is the difference between a mechanism that depends on the failing component behaving well and one that does not.

Fencing requires the protected resource to participate. A block device does not understand tokens by default; the standard way to make it participate is to revoke the old leader’s access at the storage layer — detaching the volume, changing the export list, or resetting the connection. Power-off of the old node, sometimes called shoot-the-other-node-in-the-head, is the crudest version and works because a powered-off machine issues no writes.

Tokens also solve a subtler problem: the ordering of grants. If leadership can change twice quickly, tokens let a downstream system distinguish the second grant from the first even when both come from the same physical node. A resource that only tracks “current connection” cannot do that; a resource that tracks “highest token seen” can.

Where each mechanism is load-bearing

A useful way to read a replication design is to ask which of the three protections it relies on for each shared resource:

Resource	Protection that actually works
Replicated log on quorum storage	quorum intersection; the old leader cannot commit without a majority
Shared block volume	fencing token checked by the volume, or access revocation
External service with no token support	access revocation only; timeouts do not help
Clients reading from a follower	lease expiry, with clock assumptions stated

The first row is why consensus protocols do not need leases for safety: a leader that cannot reach a majority cannot commit anything, no matter how long it believes it is leader. Its uncommitted tail is discarded by the next leader. Leases are then used only to keep reads fast — a follower can serve a read without contacting the leader if it holds a lease saying no new leader has been elected.

The third row is the one that catches designs out. An external service that accepts unauthenticated writes and has no notion of epochs cannot be protected by any amount of cleverness on the replication side. The only options are to revoke network access or to make the write idempotent and reconcilable.

The interaction with client-visible state

Fencing protects the shared resource, not the client. A client connected to the old leader during the takeover receives acknowledgements for writes that were then refused by the resource. From the client’s point of view those writes succeeded and then vanished. This is a real anomaly and it is not fixable at the storage layer; the client must be told, or the writes must be replayed by the client after reconnecting.

The usual arrangement is that the old leader, upon discovering its token is stale, terminates its own connections and reports failure for in-flight requests. That requires the old leader to eventually learn the token is stale, which happens on its next write attempt. In the interval between the takeover and that attempt, it may have already acknowledged writes it cannot deliver. The size of that interval is a property of the workload, not of the protocol.

Reads have a parallel problem. A follower serving a stale read under an expired lease is not violating a safety property if reads are not linearizable, but it is returning data that no longer matches the current leader. Whether that matters depends on the consistency model, which is why the read path of a replicated system is usually specified separately from the write path — see quorum intersection and stale reads for the arithmetic that makes read guarantees checkable.

Why clock-based failover keeps being chosen

Given that leases depend on clock behaviour and that fencing depends on the resource cooperating, lease-based failover remains the common design for a structural reason. The alternative — requiring a majority of nodes to agree on the new leader, as in Paxos or Raft — costs a round trip and requires a majority to be reachable. For a two-node primary/standby pair, there is no majority that excludes either node, so agreement cannot distinguish “the primary is dead” from “the link is broken”. A lease at least bounds the damage.

The honest description of such a system is that it provides availability with a bounded window of possible divergence, not safety. Systems that need safety over availability use a quorum, accept that a minority partition cannot write, and get fencing for free because the quorum itself refuses the stale leader’s commits. The choice between the two is the choice between topologies, and the failure model decides it: if the network can partition, leases alone cannot provide both safety and availability.