Raft Consensus with a Minority of Nodes

Summary

Raft Consensus with a Minority of Nodes By Rohan Padhye (@moarbugs on X) tl;dr — This post describes a (wacky) modification to the Raft consensus protocol such that progress can be made even if fewer than a majority of nodes are actively participating, given some constraints on exactly which minority of nodes are active. The math behind this comes from the same place as the card game Spot It! (Dobble). Raft Consensus Basics Raft is a consensus protocol for managing a replicated log across a cluster of nodes. Its key goals are: (1) maintain a consistent replicated log of state transitions, (2) tolerate node failures, and (3) ensure a single leader coordinates all changes while multiple followers replicate. Raft is designed to be understandable — it decomposes consensus into leader election, log replication, and safety — and is widely used in systems like etcd, CockroachDB, and TiKV. In steady state, the leader receives client requests and appends them to its log. It then sends AppendEntries RPCs to all followers. Once a majority of nodes (including itself) have appended the entry, the leader considers it "committed" and applies it to the state machine. For example, in a 5-node cluster, the leader needs acknowledgments from at least 2 followers (3 total including itself) before committing. This provides fault tolerance for up two node failures or a network partition where at least a majority of nodes are able to communicative with each other. If the leader crashes, a new one is elected. Any node can become a candidate, start an election for a new "term," and request votes. A candidate wins if it receives votes from a majority of nodes. This guarantees that at most one leader exists per term. Once elected, the new leader synchronizes followers' logs and resumes normal operation. The key correctness insight is this: any two majorities of nodes must overlap in at least one node. So between any two consecutive global state changes — whether two commits, two leader electio...