Raft Consensus with a Minority of Nodes

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 elections, or one of each — at least one node participated in both. This single overlapping node carries forward the knowledge of what was previously committed, preventing conflicts and ensuring consistency. In a 5-node cluster, any two sets of 3 nodes must share at least one member. This overlap is what makes Raft safe.

Spot It!

Spot It! (also known as Dobble) — the author's favorite family card game.

Spot It! (known as Dobble outside North America) is a card game whose rules are relatively straightforward: flip a card from the deck to the center, and race to find the one symbol your card has in common with the center card. Call it out, discard your card, and repeat. It's fast, fun, and requires no reading or arithmetic. It's simple enough for a 5-year old to learn quickly, yet the game design is surprisingly complex.

Here's the remarkable property that makes the game work: the deck has 55 cards, each with 8 distinct symbols drawn from a pool of 57 unique symbols, and any two cards share exactly one symbol in common. This isn't trivial to engineer. Try designing even 10 cards with this property and you'll find it surprisingly difficult. The game's designers didn't just get lucky — they used a beautiful piece of mathematics: finite projective planes .

Finite Projective Planes

A finite projective plane of order $n$ is a combinatorial structure consisting of points and lines with three key properties: (1) any two distinct points lie on exactly one common line, (2) any two distinct lines intersect in exactly one common point, and (3) every line contains exactly $n + 1$ points and every point lies on exactly $n + 1$ lines. The total number of points equals the total number of lines, and both equal $n^2 + n + 1$.

The Fano plane — the smallest finite projective plane (order 2). It has 7 points and 7 lines (including the inscribed circle), with 3 points per line and 3 lines per point. Any two lines intersect in exactly one point.

The smallest example is the Fano plane (order $n = 2$): 7 points, 7 lines, with 3 points on each line and 3 lines through each point. In the diagram above, the seven "lines" are the three sides of the triangle, the three altitudes, and the inscribed circle — each passing through exactly 3 of the 7 points. You can verify that any two of these lines share exactly one point.

Spot It! uses a finite projective plane of order $n = 7$. This gives $7^2 + 7 + 1 = 57$ points (symbols) and 57 lines (cards), with $7 + 1 = 8$ points per line (symbols per card). The intersection property guarantees any two cards share exactly one symbol — exactly what the game needs.

Finite projective planes are known to exist when the order $n$ is a prime power. Here are some small examples:

Order ($n$)<br>Points = Lines ($n^2 + n + 1$)<br>Points per line ($n + 1$)<br>Notes

273Fano plane<br>3134<br>4215<br>5316<br>7578Spot It!<br>8739<br>99110<br>1113312

(Order 6 is notably absent — it was proven not to exist. Order 10 was shown...