Raft Consensus with a Minority of Nodes
This post explores a mathematically elegant, albeit unconventional, modification to the Raft consensus protocol. By leveraging finite projective planes, a concept also central to the card game Spot It!, the author proposes enabling progress even when only a minority of nodes are active, provided they form a specific "bloc." However, this theoretical improvement comes with a significant trade-off: it sacrifices Raft's guarantee of progress when a simple majority of nodes is available.
The Lowdown
The article introduces a novel approach to the Raft consensus protocol, aiming to maintain functionality even when a traditional majority of nodes is unavailable. Inspired by the mathematical principles behind the popular card game Spot It! (Dobble), the author proposes integrating finite projective planes to redefine quorum requirements. This modification allows Raft to commit entries or elect leaders with a smaller, specific subset of nodes, rather than relying on a simple numerical majority.
- Raft Refresher: The author briefly explains Raft's core mechanics, emphasizing how its safety stems from the guarantee that any two majorities of nodes must overlap. This overlap ensures consistency by having at least one node participating in successive state changes.
- Spot It! Connection: The game Spot It! is highlighted for its unique property where any two cards share exactly one symbol. This seemingly simple game property is a direct application of finite projective planes, a combinatorial structure where "lines" (cards) intersect at "points" (symbols) in a specific, predictable way.
- Projective Plane Integration: The core idea is to treat the nodes in a Raft cluster as "points" and predefined subsets of nodes as "lines" or "blocs" from a finite projective plane. If any two such "blocs" are guaranteed to intersect in at least one node, they can serve as valid quorum sets for Raft.
- Modified Raft Operations: Under this new scheme, a log entry is committed or a leader is elected once an entire "bloc" of nodes (which is smaller than a traditional majority) acknowledges the operation. The intersection property of projective planes mathematically preserves Raft's crucial safety guarantees.
- Demonstration with Fano Plane: Using a 7-node cluster based on the Fano plane (the smallest projective plane), the article demonstrates scenarios where progress can be made with only 3 active nodes (a minority), showcasing the potential benefit. It also illustrates how consistency is maintained through the guaranteed overlap of "blocs."
- The Critical Trade-off: The primary drawback is revealed in scenarios where a traditional majority of nodes might be active, yet the system fails to make progress because the active nodes do not happen to form one of the designated "blocs." The probability of a random subset of active nodes containing a valid bloc can be surprisingly low, especially in larger clusters.
- Broader Implications & Alternatives: The author relates this work to the Erdős–Ko–Rado theorem, which provides theoretical bounds on intersecting set systems. While projective planes offer mathematical elegance, the article concludes by suggesting that designing quorum sets based on real-world failure patterns (e.g., availability zones) might be more practical and effective than relying on a purely mathematical construction for random failures.
In essence, this exploration offers a fascinating theoretical modification to Raft, demonstrating how advanced combinatorics can enable consensus with a minority of nodes. However, it candidly points out the practical limitations, particularly the reduced availability guarantee under random node failures, making it a thought-provoking exercise in distributed systems design rather than a direct recommendation for current implementations.