5.2. Consensus Algorithms
Consensus is the problem of getting a group of nodes to agree on a single value despite failures — and the FLP result proves it is impossible to guarantee in a fully asynchronous network. Every practical consensus algorithm is a way of living with that impossibility: guaranteeing safety always, and liveness only when the network behaves. This chapter covers why consensus is hard, then Paxos and Raft as the two answers the industry actually ships, plus their derivatives (Zab, etcd) and the Byzantine variants that tolerate lying nodes.
Topics Covered
Section titled “Topics Covered”- 5.2.1. The Split-Brain Problem and Fencing Tokens: Introduces the split-brain problem and fencing tokens as the mechanism that prevents a stale leader from acting.
- 5.2.2. The FLP Impossibility Result: Why Consensus Is Hard: Explains the FLP result: why guaranteed consensus is impossible in a fully asynchronous network, and the escape hatches.
- 5.2.3. Paxos: Core Logic, Prepare and Accept Phases: Covers Paxos’s prepare and accept phases and the core logic that made fault-tolerant agreement provable.
- 5.2.4. Raft: Leader Election, Log Replication, Membership Changes: Explains Raft’s leader election, log replication, and membership changes, designed for understandability.
- 5.2.5. Zab (ZooKeeper Atomic Broadcast): Epochs and Zxid: Covers ZooKeeper Atomic Broadcast, its epoch and zxid mechanics, and how it powers ZooKeeper.
- 5.2.6. etcd: Distributed K-V Storage on top of Raft: Explains etcd as a distributed key-value store built on Raft, the backbone of Kubernetes cluster state.
- 5.2.7. Byzantine Fault Tolerance: PBFT, Proof of Work / Proof of Stake: Covers PBFT and blockchain consensus (Proof of Work, Proof of Stake) that tolerate malicious nodes.