Chapter 9: Consistency Models & Consensus Algorithms

The ninth chapter, "Consistency and Consensus," addresses the crucial task of developing fault-tolerant distributed systems by establishing foundational abstractions that tolerate issues such as unreliable networks, node failures, and approximate clock timing. One central abstraction explored is consensus, which requires all nodes to agree on a specific decision despite internal system faults. The discussion differentiates between consistency models: eventual consistency, a weak guarantee that means replicas will eventually converge to the same value if writes cease, and linearizability (or atomic consistency), a much stronger recency guarantee that maintains the illusion of a single, atomic copy of the data, thereby imposing a total order on all operations. Linearizability is essential for coordination tasks, such as leader election (avoiding split brain), implementing distributed locks, and enforcing hard uniqueness constraints (like usernames). However, this strong guarantee comes at a cost, leading to the CAP theorem insight: a system requiring linearizability must sacrifice availability during a network partition. The chapter contrasts linearizability's total order with causal consistency, which preserves only the partial order defined by cause-and-effect dependencies. Causal consistency avoids the performance penalty associated with linearizability and is the strongest model that remains available in the face of network failures. The mechanisms for ordering events are examined, including Lamport timestamps, which generate a total order consistent with causality but are insufficient for immediate decision-making regarding uniqueness constraints. This limitation highlights the necessity of total order broadcast (or atomic broadcast), which guarantees that all nodes receive the exact same sequence of messages in the identical fixed order. The text reveals the profound equivalence between total order broadcast, linearizable atomic operations (like compare-and-set), and the consensus problem itself. The chapter then details the atomic commit problem for distributed transactions, typically handled by the Two-Phase Commit (2PC) protocol. 2PC employs a coordinator; participants first vote "yes" during the prepare phase (promising irrevocably to commit) before the coordinator makes the definitive commit or abort decision. Crucially, 2PC is a blocking protocol: if the coordinator fails after participants have prepared, the participants become stuck "in doubt," holding locks indefinitely until the coordinator recovers, thus failing the consensus requirement for termination. In contrast, superior fault-tolerant consensus algorithms (such as Paxos, Raft, and Zab) implement total order broadcast by utilizing epoch numbering and strict majority quorums to safely ensure agreement, integrity, validity, and termination, preventing indefinite blocks during node failures. These robust consensus mechanisms are the foundation of coordination services like ZooKeeper and etcd.