Distributed systems / consensus deep dive

Raft leader election: why randomized timeouts prevent a silent split-brain

A replicated service can lose its leader without losing any data, yet still become unavailable if every surviving node tries to take over at once. Raft’s randomized election timeout is a small timing rule that turns that race into a likely single-winner election. The deeper rule is term fencing: a node may become leader, but an old leader must never remain authorized to act.

Distributed systems / consensus deep dive · quorums, RequestVote, randomized timers, terms, PreVote, and stale-leader fencing

2026-08-27

The concrete problem

Suppose five servers replicate the state of a metadata service. Clients need one authoritative writer because two different answers to “what is the current value?” are worse than a short outage. The leader normally sends heartbeats. If it dies or the network path to it disappears, a follower must take over.

The obvious replacement algorithm is: wait for the leader, then when a timeout expires, declare yourself leader. That fails in a particularly annoying way. If all followers use the same timeout, they wake together, vote for themselves, and divide the votes. No candidate reaches a majority. They try again together, collide again, and the cluster remains unavailable even though a majority of machines are healthy.

Raft’s election state machine

Raft gives each server three relevant roles: follower, candidate, and leader. Every server stores a monotonically increasing currentTerm. A message carrying a higher term forces a server to update its term, forget its old vote, and step down to follower. A message carrying a lower term is stale and cannot grant authority.

A server grants at most one vote per term. In the full protocol it also checks that the candidate’s replicated log is at least as up to date. That log check is not a cosmetic extra: it prevents a candidate that would erase committed history from becoming leader. This lesson concentrates on election timing and term authority, but the election rule is not safe when detached from that vote predicate.

Why one timeout is not enough

Let the heartbeat interval be H, and let each follower choose an election deadline in a range [T, 2T). A healthy leader sends heartbeats more frequently than the minimum election timeout, so followers continually reset their deadlines. When heartbeats stop, the follower with the smallest deadline starts first.

Randomization does not make collision impossible. It makes the first deadline likely to be separated from the rest by enough time for the candidate’s vote requests to arrive. A fixed timeout makes collision deterministic; a randomized timeout turns it into a bounded probability that decreases as the timeout range grows relative to network delay and scheduling jitter.

The interval must be chosen against the system’s real timing. If the lower bound is shorter than normal heartbeat delay, healthy followers start elections. If the range is too narrow, packet delay and stop-the-world pauses produce repeated split votes. If it is too long, failover is safe but clients see a long outage.

Message and control flow

Here is the election path after a follower’s local timer expires. A timeout is a local suspicion, not proof that the leader is dead: the network may simply be partitioned or delayed.

Resetting the timer on the right events matters. A follower should not reset merely because it received an invalid or stale packet; an attacker or a delayed peer could otherwise keep the cluster from electing anyone. Implementations normally reset after accepting a valid leader heartbeat or granting a vote, not after every message-shaped object.

Terms are fencing tokens, not timestamps

A term is a logical epoch. It does not measure elapsed time and does not need synchronized clocks. Its job is to make old authority recognizable. Consider a network partition:

1. Server A is leader in term 8 but becomes isolated from a majority.
2. Servers B, C, and D elect B in term 9. B can commit new entries because it has a quorum.
3. A is still alive and may continue accepting client requests from its isolated side.
4. When A or a client reaches a term-9 server, the higher term causes A to step down. Its term-8 writes cannot be committed over the quorum’s term-9 history.

This is why “there is only one leader” is an imprecise statement. During a partition, two servers may each believe they are leader from their local view. Only the leader with a current term and a quorum can make progress that survives reconciliation. The term is the fence that makes stale authority fail closed.

Important open-source implementation landmarks

The etcd/raft library is a widely used Go implementation of the Raft state machine. The names below refer to the current etcd-io/raft source; source links are implementation landmarks, not a stable application API.

etcd’s RawNode API exposes the state-machine boundary to a host application: the application feeds messages and ticks in, persists HardState and entries, sends returned messages, and applies committed entries. That separation is useful for debugging because the library can decide protocol state while the host owns transport, disk, and process lifecycle.

PreVote: liveness protection for a disconnected node

A node that is partitioned away from the quorum cannot win an election, but it can keep incrementing its term whenever its local timer expires. When it eventually reconnects, its high term can force the healthy leader to step down even though the isolated node cannot itself collect a majority. Repeatedly doing this creates avoidable leadership churn.

The optional PreVote phase asks peers, “would you vote for me if I started an election?” without incrementing the real term. Only after a node receives a quorum of pre-votes does it begin the disruptive term increment. This changes liveness behavior, not the fundamental safety proof: real elections still use one vote per term, a log up-to-date check, and a majority.

PreVote is a good example of a production refinement that is easy to misunderstand. It is not a replacement for randomized timeouts, quorum rules, or durable term state. It reduces a partitioned node’s ability to disturb a healthy quorum.

Tradeoffs and failure modes

• False leader churn. CPU starvation, long garbage-collection pauses, overloaded disks, or a noisy virtual network can look like leader failure. Measure heartbeat round-trip and scheduling delay before changing election constants.
• Split vote loops. Several candidates can each receive fewer than a quorum. They must randomize the next timeout and retry; a fixed retry deadline recreates the same collision.
• Stale writes. A client may keep a connection to an old leader. The server must reject or redirect requests after learning a higher term, and the client must retry against the current leader with an idempotency strategy.
• Unsafe persistence. If a node crashes after sending a vote but before persisting it, a restart can vote again in the same term. The transport path and the durable HardState path must have a deliberate ordering.
• Membership mistakes. A quorum calculation is only meaningful for the configured membership. Stale configuration, duplicate IDs, or unsafe membership changes can make two groups believe they each have a majority.
• Byzantine behavior. Raft tolerates crashes and partitions, not malicious nodes that forge messages or equivocate. Use authenticated transport and a protocol designed for Byzantine faults when that threat is in scope.

Security implications

Leader election is an authorization protocol inside the cluster. Authentication must bind a message to a configured server identity, and integrity must protect its term, candidate ID, and log metadata. Encryption without peer authentication is not enough: an attacker able to impersonate a member can manufacture vote requests or heartbeats and create an availability attack.

Operators should also treat the admin path as privileged. An API that changes cluster membership, resets data, or forces leadership is more powerful than a normal client write. Audit membership changes, restrict who can reach the peer port, rotate certificates safely, and alert on repeated term increases or leader changes. A term that rises rapidly is often a partition, a timeout-calibration problem, or an attack—not “normal consensus noise.”

How to debug an election storm

1. Plot leader changes and term numbers on one time axis. A rapidly increasing term with no stable leader points to election churn; a stable term with slow requests points elsewhere.
2. For every node, record election timeout, heartbeat arrival time, timer reset reason, election start, vote decision, and the term observed in each message. Never log only “election failed”; the timing is the diagnosis.
3. Compare the configured election timeout with measured p99 heartbeat delay, p99 scheduler pause, disk fsync latency, and packet loss. The lower timeout must leave headroom above normal tail latency.
4. Check quorum reachability as a graph, not as a node count. Three healthy processes split 2–1 have a quorum; five processes split 2–3 have one; two isolated groups of 2 in a five-node cluster have none.
5. Verify persistence ordering around HardState. A restart loop that repeatedly reuses a vote or term is a correctness bug, not a timeout problem.
6. Inspect whether PreVote is enabled and whether all members agree on election and heartbeat settings. Mixed assumptions make incident traces deceptively random.

Compact reproducible lab: see the collision probability

Goal: run a small timing model that makes the reason for randomized timeouts visible. It models five followers, a candidate’s request round-trip delay, and the rule that a unique earliest timeout wins only when the next timeout is sufficiently later. This is not a complete Raft implementation; it isolates the timing mechanism.

Prerequisites: Python 3.9 or newer. No packages or network access are required.

cat > /tmp/raft-election-race.py <<'PY'
import argparse
import random

def run(nodes, low, high, one_way_delay, trials, seed):
    rng = random.Random(seed)
    split = 0
    win = 0
    for _ in range(trials):
        deadlines = sorted(rng.randint(low, high) for _ in range(nodes))
        first, second = deadlines[:2]
        # The first candidate needs a request and a vote response to cross
        # the network before the next follower starts its own election.
        if second - first <= 2 * one_way_delay:
            split += 1
        else:
            win += 1
    return win, split

parser = argparse.ArgumentParser()
parser.add_argument("--low", type=int, default=150)
parser.add_argument("--high", type=int, default=300)
parser.add_argument("--delay", type=int, default=5)
parser.add_argument("--trials", type=int, default=10000)
args = parser.parse_args()
win, split = run(5, args.low, args.high, args.delay, args.trials, 7)
print(f"range={args.low}..{args.high}ms delay={args.delay}ms")
print(f"unique-winner rounds: {win}/{args.trials} ({100 * win / args.trials:.1f}%)")
print(f"collision-prone rounds: {split}/{args.trials} ({100 * split / args.trials:.1f}%)")
PY

python3 /tmp/raft-election-race.py
python3 /tmp/raft-election-race.py --low 200 --high 200
python3 /tmp/raft-election-race.py --low 150 --high 300 --delay 40

Expected result: the 150–300 ms range with a 5 ms one-way delay produces many unique-winner rounds; the fixed 200 ms range produces collisions in every round; the same randomized range with 40 ms delay collides much more often. Exact percentages vary if you change the seed or model, but the direction should remain.

Observations: the model uses only the gap between the first two deadlines. That is the key quantity: adding more nodes makes the earliest two deadlines statistically closer, while increasing the timeout range gives them more room to separate. In a real implementation, scheduler pauses, retransmissions, batching, and log checks add to the effective delay.

Revealing variations:

• Change --low 50 --high 100. The collision rate rises because the timing window is now small relative to the fixed 5 ms message round trip.
• Change run(5, ...) to run(3, ...) or run(7, ...). More voters increase the chance that two timers are near the minimum, which is one reason timeout tuning depends on cluster size and tail latency.

Environment note: this lab is pure Python and should run on macOS or Linux. It does not prove quorum safety or persistence correctness; those require the implementation tests and fault-injection tools of a real Raft library.

Discussion: what Raft is really guaranteeing

Resilience is not everyone agreeing all the time; it is preserving safety while allowing useful progress.

Production shape

In an etcd-backed Kubernetes control plane, an etcd leader serves the replicated metadata log. Kubernetes controllers can tolerate a short etcd leader transition, but an election storm turns a small network or latency problem into control-plane-wide write failures. In a Consul server set, Raft leadership similarly gates writes to the catalog and sessions. In systems such as CockroachDB, many Raft groups run independently, so the same mechanism appears repeatedly at a smaller shard scope; a single bad timeout policy can create a storm across thousands of groups.

The operational lesson is to tune from measurements: heartbeat and election settings should be comfortably above normal p99 or p99.9 communication and scheduling tails, while still meeting the desired failover budget. Then test the failure you are tuning for—leader kill, packet loss, asymmetric partition, long pause, and restart during vote persistence—in a staging environment.

The design in one sentence

Raft does not solve leader failure with a magical timeout; it combines randomized local suspicion, one-vote-per-term quorum rules, durable fencing tokens, and immediate demotion on higher terms so that one node usually wins quickly and an old node cannot remain authoritative.

Primary sources

• In Search of an Understandable Consensus Algorithm (Raft) — the original paper, including randomized election timeouts, leader completeness, terms, and the election safety argument.
• Diego Ongaro’s dissertation — extended treatment of Raft’s design and implementation considerations.
• etcd-io/raft raft.go — production state machine with timers, terms, vote handling, PreVote, and role transitions.
• etcd-io/raft node.go — the application-facing tick/message/persistence boundary around the state machine.
• etcd: why a distributed key-value store — how Raft-backed replication supports a strongly consistent control-plane store.
• HashiCorp Consul consensus documentation — a production description of Raft servers, quorum, and leader behavior.