When a leader stops talking, every follower starts asking the same dangerous question:

Is it my turn yet?

If everyone answers yes at the same time, the cluster does not get a leader. It gets a split vote, a higher term, and another try.

Raft’s leader election is often explained as “wait a random timeout.” That description is accurate and weirdly undersells the idea. The timeout is not just a delay. It is a spacing device.

The cluster is trying to arrange for exactly one server to cross the starting line early enough that its RequestVote messages reach the others before they cross it too.

That gap is the election.

What Raft Is Buying

Raft was designed as a more understandable foundation for practical replicated logs than the Paxos family that dominated consensus discussions.1 It separates consensus into leader election, log replication, and safety. During election, a follower that has not heard from a leader for an election timeout becomes a candidate, votes for itself, and sends RequestVote RPCs to the other servers. A candidate becomes leader if it receives votes from a majority in the same term.2

The safety rule is not “the fastest clock wins.” Each server votes at most once per term, and majorities intersect. Timing affects whether the system makes progress quickly, not whether two leaders can safely be elected for the same term.

The Raft paper states the timing requirement this way:

\[\text{broadcastTime} \ll \text{electionTimeout} \ll \text{MTBF}.\]

The left side says heartbeats and vote RPCs must be much faster than the timeout. The right side says the timeout should be much shorter than the time between failures, so recovery does not dominate availability.3

Randomness lives in the left side. If all followers use the same deterministic timeout, a leader crash can make them become candidates together. If each follower samples from a range, the first candidate usually has a head start.

The head start only has to be long enough for the candidate’s message to arrive.

A Small Race Model

This lab is not a full Raft implementation. It isolates one race:

  1. A leader disappears.
  2. Each follower samples an election timeout uniformly from the same interval.
  3. The first server to time out becomes a candidate.
  4. We call the round “clean” if the second timeout is more than one RPC broadcast window later.

That is stricter than Raft’s real majority rule, but it is a useful lens: if the first timeout has enough separation, the story is simple. One candidate starts, the others hear about it, and the term converges.

For \(n\) servers with timeout spread \(W\) and RPC window \(b\), the clean-gap probability is

\[P(\text{second timeout} - \text{first timeout} > b) = \left(1 - \frac{b}{W}\right)^n, \quad 0 < b < W.\]

That formula is the whole post in miniature. More randomness buys separation. More servers create more chances for someone else to be close behind. Larger RPC windows eat the gap.

Default audited facts:

  • nodes: 5;
  • timeout range: 150-300ms;
  • RPC window: 15ms;
  • clean election rate: about 60.8% over 1200 deterministic trials;
  • closed-form clean probability: 59.0%;
  • median first-to-second timeout gap: about 19.9ms;
  • retry multiplier from the formula: about 1.69x;
  • audit grid: 96 / 96 parameter cases passed.
clean first timeout split-risk window follower timeout formula curve retry cost

Deterministic toy race, not a full Raft implementation. The audit checks simulated clean-election rates against the order-statistic formula, monotone gap quantiles, finite outputs, and wider-spread improvements across 96 parameter settings.

Set Random spread to zero. The timeouts pile up. The formula goes to zero, which matches the Raft paper’s experiment where no randomness led to repeated split votes and election delays beyond ten seconds.4

Increase RPC window. The shaded danger interval gets wider. This is the operational reason the paper wants broadcast time to be much smaller than the election timeout.

Increase Nodes. More servers improve fault tolerance, but in this tiny race model they also create more opportunities for the second timeout to land close behind the first. The spacing problem gets stricter.

Why the Minimum Timeout Still Matters

The clean-gap probability above depends on spread, RPC time, and node count. It does not care whether the interval is 150-300ms or 500-650ms; the offsets inside the interval have the same shape.

Real availability cares a lot.

If the minimum timeout is too large, a crashed leader is detected slowly. If it is too small, ordinary heartbeat jitter can look like leader failure. Raft’s timing inequality is doing two jobs at once:

  • keep heartbeats safely inside the timeout;
  • keep recovery time small relative to actual failures.

The lab’s timeout/RPC metric is a crude version of the first job. At the default 150ms minimum timeout and 15ms RPC window, the ratio is 10x, right on the “order of magnitude” heuristic in the Raft paper. Lower the minimum timeout without improving the RPC window and the cluster becomes more eager to hold unnecessary elections.

This is why “make failover faster” is not a scalar knob. It is a budget split between detection, message latency, disk persistence, retry behavior, and the tail of the network.

Randomness Is for Liveness

The subtle part is what randomness does not do.

Random election timeouts do not make Raft safe. The safety argument comes from terms, one vote per term, log up-to-dateness checks, and majority intersection. Randomness helps the cluster escape an availability pattern where several candidates keep colliding.

That distinction is a useful systems habit:

  • safety says what must never happen;
  • liveness says whether something good eventually happens;
  • timing assumptions usually belong to liveness;
  • randomization often turns a repeated symmetry into a fast escape.

This is also why Raft is easier to reason about than “the leader is whoever looks alive from here.” The random timeout creates a candidate. The voting rules decide whether that candidate is legitimate. The term clock records whether the conversation is stale.

The timer opens the door. It does not certify the leader.

The Practical Lesson

When setting election timeouts, do not ask only for a number. Ask for a shape:

  • What is the normal and tail latency of a broadcast round?
  • How much stable-storage delay is inside RequestVote and AppendEntries?
  • How synchronized are followers after leader heartbeats?
  • How wide is the random spread relative to the RPC window?
  • What is the cost of one extra term with no leader?

The random timeout is a small idea with a large job. It gives one candidate enough solitude to be heard.

Consensus still needs quorums, terms, and logs.

But progress begins with a gap.

  1. Leslie Lamport, “Paxos Made Simple”, ACM SIGACT News, 2001. ↩

  2. Diego Ongaro and John Ousterhout, “In Search of an Understandable Consensus Algorithm”, extended version of the 2014 USENIX ATC paper. See the USENIX record for the published version: USENIX ATC 2014. ↩

  3. Ongaro and Ousterhout, Section 5.6, “Timing and availability,” in the extended Raft paper. ↩

  4. Ongaro and Ousterhout, Section 9.3 and Figure 16. Their five-server experiment used a broadcast time of roughly 15ms; without randomness, elections repeatedly split, while 150-300ms timeouts provided conservative availability. ↩