Raft Consensus with a Minority of Nodes
a day ago
- #Finite Projective Planes
- #Consensus Protocols
- #Distributed Systems
- Raft is a consensus protocol designed for managing a replicated log across nodes, focusing on consistency, fault tolerance, and a single leader.
- It operates through leader election, log replication, and safety mechanisms, requiring majority acknowledgment for commits, with fault tolerance up to minority node failures.
- Key correctness relies on overlapping majorities ensuring at least one node participates in consecutive state changes, preventing conflicts.
- Spot It! (Dobble) is a card game where any two cards share exactly one symbol, enabled by finite projective planes, specifically of order 7 with 57 symbols and 55 cards.
- Finite projective planes, like the Fano plane (order 2), have properties where any two points lie on one line and any two lines intersect at one point, with total points/lines = n² + n + 1.
- They exist for prime power orders; Spot It! uses order 7, but orders like 6 and 10 are proven not to exist.
- A modified Raft protocol uses projective planes to define blocs (quorum sets) of p+1 nodes, reducing quorum size but requiring specific node combinations for progress.
- Trade-offs include lower probability of progress with random active nodes compared to classic Raft, as seen in examples with 7 and 57-node clusters.
- The Erdős–Ko–Rado theorem provides bounds on intersecting families, offering a framework to optimize bloc designs for real-world failure patterns, like availability zones.
- Practical implementations may prioritize tailored bloc designs over symmetric structures to handle correlated failures more effectively.