Leader Failover: Detection Windows, Fencing, and Split-Brain Avoidance

The failure that failover must handle is not the one where a machine stops. It is the one where the machine appears to stop. A leader whose network cable is pulled is, from the outside, indistinguishable from a leader whose process is descheduled for forty seconds while its clients keep waiting, or from a leader that is running fine but partitioned away from the majority of its replicas. Every failover mechanism is built on an answer to that ambiguity, and the answer is never perfect: it is a timeout, which is a bet that a silent leader is a dead leader.

Detection is a timeout, and a timeout is a guess

A replica that receives no heartbeat for T seconds declares the leader suspect. The declaration is not knowledge. If the leader is merely slow — a long garbage collection pause, a stalled disk, a saturated network link — then the replica promotes itself while the old leader is still alive and still accepting writes from clients that can reach it. The system now has two leaders. This is split-brain, and it is worse than an outage because it produces divergence that survives the incident.

The size of T sets the shape of the failure. A short timeout detects genuine failures quickly and promotes on transient slowness constantly, which causes repeated unnecessary elections. A long timeout does the reverse. There is no value of T that separates the two cases, because the observable is the same: silence. Every production system therefore tunes T against the tail of its own pause distribution and accepts a nonzero rate of false positives.

The heartbeat path itself matters. A heartbeat that travels on the same network path as the replication stream is silent when that path fails, and so is a genuinely dead leader. A heartbeat on a separate path detects network partition as a leader failure, which may be the correct interpretation, but it also means a partition of the heartbeat path alone triggers failover while replication is healthy. Neither design is wrong; they fail in different directions and the choice is a policy decision.

Why a majority is not optional

The reason a minority cannot promote itself is arithmetic, not caution. Suppose three replicas hold the log, and one of them loses contact with the other two. If the isolated one promotes itself, and the other two also promote one of their number, both leaders accept writes. Nothing in the system prevents it, because each side believes the other is gone.

A majority rule fixes this by making promotion require votes from more than half of a fixed membership. Two disjoint majorities cannot exist in the same membership set, since each would need more than half of the same N nodes. The isolated node gets one vote, which is not a majority of three, and stays a follower. The remaining two form a majority and elect a leader. The guarantee is purely combinatorial and depends on one thing: that the membership is fixed and agreed. A membership that two sides disagree about can produce two majorities, which is why membership changes are themselves a consensus problem and not an administrative afterthought. The same arithmetic governs the read and write quorums discussed in quorum intersection, with the same caveat: it holds for independent failures, not for a shared failure domain.

The vote is also where the log’s continuity is enforced. A candidate whose log is behind a voter’s log cannot win that voter’s vote, so the elected leader is always at least as current as any majority of the membership. This is the property that makes failover safe with respect to acknowledged writes: if a write was acknowledged by a majority, any new leader’s majority must intersect that set and therefore contains at least one node with the write, which refuses to vote for a candidate lacking it. The Raft election restriction states this explicitly; Paxos derives it from the ballot structure.

The old leader that is still alive

Majority voting solves the election but not the write path. The deposed leader does not know it has been deposed. It is partitioned from the new majority, its clients can still reach it, and it will happily acknowledge writes that the new leader never sees. Those writes are lost when the partition heals, and the clients were told they succeeded.

The fix is not detection, because the old leader cannot detect its own isolation — the absence of messages is exactly what a partition produces on both sides. The fix is to make the old leader unable to do harm. Two mechanisms are used.

Fencing. Every leadership term carries a monotonically increasing number. A storage system or a downstream service that accepts writes is given the term number and rejects any request carrying a term lower than the highest it has seen. The old leader’s writes fail at the boundary even though the old leader believes it is still the leader. This requires the fence to be enforced by something that both leaders talk to, and the classic failure is a fence that only guards some of the resources. A leader that can still write to one unguarded store has not been fenced.

Self-termination on lease expiry. The leader holds a lease granted by the majority, with an expiry time. It may serve writes only while it believes the lease is valid, and it must stop when the lease expires even if it has heard nothing. The lease is safe only if the leader’s clock runs no faster than the grantor’s by more than the assumed margin; the standard treatment of this problem is to bound the clock drift and subtract it from the lease duration, so the leader’s own deadline is strictly earlier than the grantor’s.

Neither mechanism is free. Fencing requires every write path to check the token, including the paths that were added after the failover code was written. Leases require a bound on clock skew, and the bound must hold across the machines involved or the guarantee is void.

# Fencing at the storage boundary: the term is checked, not the caller's belief.
class FencedStore:
    def __init__(self):
        self.high_water = 0

    def write(self, term, key, value):
        if term < self.high_water:
            raise StaleLeader(term, self.high_water)
        self.high_water = max(self.high_water, term)
        self._put(key, value)

The check must be inside the same atomic step as the write. A separate “is this term still valid” query followed by a write is a race, and the race is exactly the window the old leader needs.

What failover does to the log

Promotion does not produce a leader with the full log. It produces a leader with the longest log among the majority that voted for it, which may be shorter than the old leader’s log. The suffix the old leader had but the new one lacks is lost, and the replicas that held it must discard it. This rollback is the least discussed part of failover and the most damaging to assumptions.

The discard is safe for acknowledged writes only under synchronous acknowledgement, as described in the commit boundary. Under asynchronous replication, an acknowledged write can sit in that discarded suffix. The client was told the write happened; after failover it did not. Nothing in the replication machinery can recover it, because the only copies were on nodes that are now behind the new leader’s position.

Some systems reduce the window by requiring a quorum acknowledgement before returning to the client, which turns the failover into a no-loss event for acknowledged writes at the cost of the latency described earlier. Others accept the loss and make it visible: the discarded suffix is reported, and the operator knows the size of the gap. The one option that is not acceptable is silently discarding it and continuing as if the guarantee held.

There is also the question of what a replica does with a suffix that conflicts with the new leader’s. It must truncate to the point of divergence and re-fetch. Finding the divergence point is a log comparison, and the cost is proportional to the length of the divergent suffix in the worst case, though implementations reduce it by comparing positions and walking back. A replica that cannot find a common prefix with the new leader at all cannot rejoin and must be rebuilt from a base copy.

Automatic failover and its preconditions

Automatic promotion is a program making a decision that a human would make with more information. The preconditions that make it safe are worth stating explicitly, because each one is a thing that can be missing.

The membership must be fixed and known to all voters. The voters must be able to reach a majority. The promotion must be fenced at every write boundary. The new leader must be able to serve reads at a position that is consistent with what it acknowledged. And the old leader, if alive, must be prevented from writing.

When the last condition cannot be met, the correct behaviour is to stop accepting writes rather than to guess. A system that promotes anyway and relies on the old leader eventually noticing has chosen availability over consistency, and it should say so in its documentation rather than in an incident report. The distinction between a system that fails closed and one that fails open is the single most important property to know about a failover mechanism, and it is not visible from the configuration syntax.