Raft & Paxos Consensus: Leader Elections, Term Epochs & State Machine Replication

Executive Summary

Replicated state machines are the foundation of strongly consistent distributed infrastructure. By ensuring that a cluster of independent nodes executes the exact same sequence of deterministic state transitions, the cluster acts as a single, fault-tolerant entity. Ongaro and Ousterhout's Raft protocol decomposed consensus into understandable subproblems: leader election, log replication, and safety invariants.

1. The Quorum Formula

To tolerate $F$ node crashes, a Raft cluster must contain at least $2F + 1$ nodes. The minimum quorum size $Q$ required to elect a leader or commit a log entry is: $$Q = \left\lfloor \frac{N}{2} \right\rfloor + 1$$ For a 5-node cluster ($N=5$), $F=2$, and $Q=3$. Any two quorums of size $Q$ must overlap in at least one node, guaranteeing that the winning candidate has seen every previously committed entry.

2. Raft Leader Election & Term Epochs

• Randomized Election Timeouts (150ms - 300ms): Prevents split-vote livelocks where multiple candidates start elections simultaneously.
• Pre-Vote Extension: Candidates first send low-overhead Pre-Vote probes without incrementing their term. If they cannot reach a majority, they do not trigger a disruptive cluster-wide re-election.
• Leader Completeness Property: A voter denies its vote if the candidate's log is less up-to-date than its own log ($ ext{Term}{candidate} < ext{Term}{voter}$ or $ ext{Index}{candidate} < ext{Index}{voter}$).

3. Fencing Tokens: Eliminating Zombie Leaders

When a network partition temporarily isolates a leader, it may experience a "zombie" state where it still believes it is the leader while the rest of the cluster has elected a new leader with a higher term epoch. Fencing tokens (monotonically increasing integer term numbers) are passed with every downstream RPC:

Client Request -> Leader (Term 5, FencingToken: 5) -> Storage
New Leader Elected (Term 6, FencingToken: 6) -> Storage rejects Term 5 RPCs with FENCING_TOKEN_STALE