Chapter 14: Consensus Algorithms: Paxos, Raft & Beyond

The chapter examines broadcast primitives, particularly Atomic Broadcast protocols that guarantee both reliability and total ordering of messages across all participating nodes. Virtual Synchrony is presented as a solution for dynamic group membership scenarios where processes can join and leave the system. A detailed analysis of the Zookeeper Atomic Broadcast (ZAB) protocol reveals its epoch-based approach and three-phase methodology encompassing discovery, synchronization, and broadcast phases to maintain consistency in primary-backup architectures. The Paxos algorithm receives extensive coverage, detailing the distinct roles of Proposers who initiate proposals, Acceptors who vote on proposals, and Learners who execute agreed-upon decisions, along with the two-phase protocol involving prepare and accept phases that ensures safety through majority quorums. Multiple Paxos variants are explored, including Multi-Paxos for optimizing repeated consensus through stable leadership, Fast Paxos for reducing message latency, Egalitarian Paxos (EPaxos) which uses dependency tracking rather than predetermined ordering, and Flexible Paxos that relaxes traditional quorum intersection requirements. The Raft algorithm is presented as an alternative designed for enhanced understandability, utilizing Leader, Candidate, and Follower roles with randomized election timeouts to manage log replication and prevent split-vote scenarios. Finally, the chapter addresses Byzantine fault tolerance through the Practical Byzantine Fault Tolerance (PBFT) algorithm, which employs cryptographic authentication and a three-phase commit protocol to achieve consensus even when some nodes exhibit malicious behavior.