Chapter 10: Distributed consensus

Introduction

The introduction explains why distributed consensus matters: it lets redundant processes act as one and prevents disagreements that could make an application behave incorrectly.

• Agreement among redundant processes: Explain that distributed consensus lets a group of redundant processes advance in lockstep and act as one, so some can compensate when others fail.
  Why it matters: This is the purpose behind the consensus mechanisms developed in the chapter.
• Consequences of unresolved disagreement: Describe how disagreement over whether a transaction committed, the order of operations, or who acquired a lock can lead to incorrect application behavior.
  Why it matters: These examples show why failing to reach consensus can be catastrophic for an application.

Key terms: distributed consensus, redundant processes, lockstep, consensus problem, commit or abort, operation order, lock

10.1 The challenge of reaching agreement

This section defines distributed consensus, explains why realistic failures make agreement difficult, and clarifies what the FLP impossibility theorem does—and does not—rule out.

• Consensus problem and system conditions: Explain that distributed consensus asks concurrent processes communicating over a network to agree on one value, and contrast the ideal conditions that make it trivial with realistic component and message failures that make it difficult.
  Why it matters: The difficulty of consensus depends on what failures and network behavior the system model allows.
• Safety and liveness tradeoff: Distinguish the safety guarantee from the liveness goal of consensus algorithms, using Two-Phase Commit as the contrast: a failed transaction coordinator can block commitment while preserving safety, whereas consensus does not depend on any single component to keep making progress.
  Why it matters: A protocol can avoid an incorrect outcome yet still stop making progress.
• FLP theorem limits: State that FLP rules out guaranteeing consensus under all circumstances in an asynchronous distributed system without clocks, even with only one possible node failure. Explain that its limitation chiefly concerns guaranteed liveness and does not rule out consensus under more constrained models, such as the asynchronous model with clocks mentioned here.
  Why it matters: FLP limits unconditional progress guarantees, not every practical attempt at consensus.

Key terms: distributed consensus, processes, system model, atomic commitment, Two-Phase Commit, transaction coordinator, safety, liveness, FLP Impossibility Theorem, asynchronous distributed system

10.2 System model

Defines the process, failure, and proposal model for consensus, then states the safety and liveness properties a consensus algorithm must satisfy.

• Processes proposals and crashes: Describe a system of processes that may propose values, decide values, or fail by halting; identify this failure as a crash failure.
  Why it matters: These assumptions give the consensus guarantees a precise setting.
• Consensus safety guarantees: Explain validity, integrity, and agreement: a decided value must have been proposed by some process, a process cannot change its decided value, and correct processes cannot decide different values.
  Why it matters: These properties specify what consensus must never get wrong.
• Termination for nonfailed processes: Explain termination as the liveness requirement that every nonfailed process eventually decides on a value, and distinguish this progress guarantee from the safety requirements.
  Why it matters: Agreement alone is not enough if processes never reach a decision.

Key terms: Processes, Values, crash failure, Propose(p, v), Decide(p, v), safety properties, validity, integrity, agreement, liveness properties

10.3 State machine replication

This section explains how consensus lets identical processes execute the same ordered commands, turning a process into a fault-tolerant replicated group.

• Deterministic replica behavior: Explain why identical, deterministic processes that start in the same state and receive the same inputs in the same order produce the same outputs and end in the same state.
  Why it matters: This principle explains why replicas can stay in step rather than merely hold separate copies of data.
• Consensus over the input log: Describe how consensus on the log supplying each replica's inputs makes processes advance in lockstep, so a replicated group can compensate for a failed member; illustrate this with the replicated key-value store.
  Why it matters: It connects the agreement problem to the practical benefit of surviving a node crash.

Key terms: state machine replication, deterministic processes, same state, same inputs in the same order, distributed consensus, log, replicated key-value store, lockstep

10.4 The origin—and irony—of consensus

This section traces the origins of fault-tolerant consensus, explains why single-decision Paxos led to Multi-Paxos, and distinguishes Paxos’s fame from Viewstamped Replication’s earlier publication.

• Paxos and repeated decisions: Explain the irony that Lamport set out to prove fault-tolerant consensus impossible but instead devised Paxos. Describe how Paxos makes replicas agree on one value despite failures and unreliable communication, while Multi-Paxos extends that idea to a series of decisions suitable for state machine replication.
  Why it matters: The distinction between one agreed decision and a sequence of them explains why consensus can support a replicated state machine.
• Viewstamped Replication publication precedence: Distinguish Paxos’s greater recognition from Viewstamped Replication’s earlier publication: Oki and Liskov published Viewstamped Replication in 1988, and it addressed the same consensus problem without explicitly using the term consensus.
  Why it matters: Recognition and publication order give different answers to which algorithm came first.

Key terms: Paxos, Multi-Paxos, write-once registers, state machine replication, Viewstamped Replication, Brian Oki, Barbara Liskov

10.5 Implementing consensus

10.5.1 Leader-based consensus

The section shows why a single decision-making leader guarantees consensus only in an ideal system model and is insufficient when processes or messages can fail.

• Ideal leader decision process: Describe how a Benevolent Dictator for Life (BDFL) handles requests, makes decisions, and broadcasts them to other processes, and explain why this guarantees consensus in the stated theoretical system model.
  Why it matters: The ideal case makes the assumptions behind simple leader-based consensus explicit.
• Realistic single leader limitations: Explain why merely appointing a BDFL is insufficient in a realistic system model: its failure stops decisions, and lost or otherwise unreliable messages can keep decisions from reaching every process.
  Why it matters: These failure cases explain why consensus needs a more robust approach than simply naming one decision-maker.

Key terms: Benevolent Dictator for Life, BDFL, theoretical system model, realistic system model, system inconsistencies

10.5.2 Quorum-based consensus

This section explains how majority quorums enable agreement, why their overlap prevents split-brain decisions, and how many processes are needed to tolerate failures.

• Majority quorums and overlap: Explain that quorum-based consensus requires a majority of processes to acknowledge a decision, and that any two such majorities overlap, helping prevent independent groups from making inconsistent decisions.
  Why it matters: Quorum overlap is the reason separate groups cannot each form an independent majority.
• Minimum failure tolerant group size: Explain why tolerating f failed processes while retaining a quorum requires at least f+1 nonfailed processes, for a minimum total of N = 2f+1.
  Why it matters: This calculation connects the number of failures a system must tolerate to the number of processes it needs.

Key terms: quorum, Q > N/2, quorum intersection, splitbrain, f failed processes, f+1 nonfailed processes, N = 2*f+1

10.5.3 Combining leader and quorum

This section explains how consensus algorithms combine a quorum-elected leader with quorum acknowledgments before committing a proposed value.

• Leader and quorum combination: Trace how a quorum elects a leader, the leader proposes a value, and the leader waits for acknowledgments from a quorum before committing it. Explain that this combines decisive leadership with quorum reliability despite unreliable processes and networks.
  Why it matters: This pattern explains why a leader cannot commit a proposal on its own.

Key terms: leader, quorum, proposes values, acknowledgments, committing a value

10.6 Raft

Introduces Raft as a leader-and-quorum consensus protocol for replicated logs, while noting its complexity and the scope of the version discussed.

• Raft coordination of replicated logs: Explain that Raft manages replicated logs across a cluster as a foundation for state machine replication: a leader determines the order of log entries, while a quorum determines which entries are committed.
  Why it matters: This division of responsibilities frames the Raft mechanisms that follow.
• Raft complexity and version scope: Describe Raft's emphasis on understandability without calling it simple, and state that the discussion and later puzzles follow the original paper rather than necessarily applying to every Raft variant.
  Why it matters: Keeping the protocol version in mind helps avoid treating every puzzle as a claim about all Raft implementations.

Key terms: Raft, replicated logs, leader, quorum, message sequencing, message commitment, understandability, Raft consensus algorithm, original paper, variants

10.6.1 The log

This section explains how Raft uses consistent logs and leader eligibility to keep committed entries safe, then passes those entries to application state machines.

• Log consistency and commitment: Explain when Raft considers two nodes’ logs consistent, what the commit index marks, and why committed entries can safely be applied to a state machine.
  Why it matters: The distinction between a log entry and a committed entry is central to Raft’s safety guarantee.
• Up-to-date leader eligibility: Explain how Raft uses candidates’ logs during leader election to protect log consistency: only candidates with the most up-to-date logs are eligible to become leader.
  Why it matters: A new leader must not undermine the safety of entries already committed.
• Platform and application handoff: Distinguish Raft’s platform-level work—leader election, log replication, and commitment—from the application-level state machine that applies committed entries to application state.
  Why it matters: Consensus on a log matters because committed entries ultimately produce consistent application behavior.

Key terms: log consistency, commit index, quorum, committed, state machine safety, leader election, most up-to-date logs, candidate, platform level, application level

10.6.2 Terms

This section explains how Raft uses increasing terms to organize leader election and log replication, and to prevent an outdated leader from acting.

• Term phases and leader authority: Describe how Raft’s monotonically increasing terms act as a logical clock: each term begins with leader election, followed by log replication under the elected leader. Explain that the leader accepts client entries, replicates them to other nodes, and determines when nodes may apply entries to their state machines.
  Why it matters: Terms provide the structure for understanding how Raft elects a leader and manages its replicated log.
• Term numbers as fencing tokens: Explain why two nodes can both believe they are leader without both being able to act as leader. Describe how nodes reject incoming messages with term numbers lower than their current term, fencing off an earlier leader.
  Why it matters: The distinction between believing and being allowed to act is central to Raft’s correctness guarantee.

Key terms: terms, logical clock, leader election, Request Vote protocol, log replication, Append Entries protocol, term number, fencing token, previous leader, current leader

10.6.3 Leader Election protocol

This section traces how a Raft node moves among Follower, Candidate, and Leader states to elect a leader and respond to a newer term.

• Follower timeout and candidacy: Trace how a node starts or restarts as a Follower, listens for Leader messages, and uses a randomly set election timer that resets when it receives a message. Explain that when the timer expires, the Follower suspects Leader failure, increments its term, becomes a Candidate, votes for itself, and sends RequestVote requests to the other nodes.
  Why it matters: This is how a node decides to start an election when it has stopped hearing from a Leader.
• Quorum votes and retries: Explain that a Candidate becomes Leader for its term if it receives votes from a quorum, counting its own vote. Describe how a Candidate without a quorum starts another election and repeats until it wins or learns about a new term and Leader.
  Why it matters: The vote outcome determines whether the node can lead or must continue trying.
• Newer-term follower transitions: Describe how a Candidate or a node that believes it is Leader returns to the Follower state when it learns about a new term and Leader.
  Why it matters: Stepping back prevents a node from continuing to act as Candidate or Leader after it learns of a newer leadership term.

Key terms: Follower, election timer, Candidate, term, RequestVote, quorum vote, split vote, Leader, demotion

10.6.4 Log Replication protocol

This section traces how a leader replicates a client’s log entry and advances the commit index after quorum acknowledgment.

• Log replication message flow: Trace how the leader accepts a client log entry, appends it locally, and sends Append Entries requests to followers; explain how follower acknowledgments lead the leader to advance the commit index.
  Why it matters: This sequence connects replication of an entry to the quorum acknowledgment required before the leader advances the commit index.

Key terms: Log Replication protocol, Append Entries requests, quorum, commit index

10.6.5 State machine safety

This section defines Raft’s state machine safety property and explains how log-based leader election preserves committed entries.

• State machine safety invariant: State that once a process applies a log entry at an index, no other process will ever apply a different entry at that index.
  Why it matters: This is the safety guarantee Raft’s election rules are designed to protect.
• Leader candidate log freshness: Explain that Raft elects only a candidate with the most up-to-date log, comparing the last entries’ terms first and, when those terms match, their indexes or log lengths.
  Why it matters: Restricting who can become leader prevents an out-of-date log from displacing entries needed for safety.
• Quorum preservation of committed entries: Trace how an entry held by a quorum excludes candidates lacking it from leadership, so future leaders retain an entry once it is committed and cannot lose or overwrite it.
  Why it matters: This connects the leader-election restriction to the lasting safety of committed entries.

Key terms: state machine safety, log entry, index, most up-to-date log, last entries, term, leader, quorum, future leaders, committed

10.7 Raft puzzles

This introduction sets up three Raft puzzles and encourages readers to use them to connect protocol details with system-wide behavior.

• Raft puzzle setup: Describe the setup shared by the three puzzles: each has a three-node Raft cluster in its third term.
  Why it matters: The shared setup lets you focus on what changes from one puzzle to the next.
• Algorithms and system behavior: Explain why studying Raft’s algorithm alone may not reveal its full behavior: some system-wide consequences emerge from the algorithm’s interaction with the broader system. Describe the third puzzle as an example meant to bring this distinction into focus.
  Why it matters: Looking beyond individual protocol steps helps you notice behavior that is easy to miss when studying an algorithm in isolation.

Key terms: Raft cluster, three nodes, third term, thinking in algorithms, thinking in distributed systems, systemic behaviors, implicit consequences

10.7.1 Puzzle 1

This puzzle identifies the leader for term 3 from the cluster’s logs and connects that evidence to the leader’s role in handling client requests.

• Term 3 leader identification: Identify node 2 as the leader for term 3 and explain that its more advanced log is the clue: the leader accepts client requests, adds them to its log, and propagates them to followers.
  Why it matters: The puzzle connects a visible log difference to the leader’s role in replication.

Key terms: leader, term 3, log, client requests, followers

10.7.2 Puzzle 2

A Raft puzzle shows how a request present only in a leader’s log can be lost without violating state machine safety.

• Uncommitted request loss: Explain why request 9 can be lost when node 2 loses leadership and why that loss does not violate state machine safety.
  Why it matters: A leader accepting a request is not the same as the request being committed.

Key terms: leader, term, follower, log, committed, state machine safety

10.7.3 Puzzle 3

Puzzle 3 shows why Raft preserves a replicated but apparently uncommitted request when its leader crashes.

• Uncertain commit status: Explain why node 1 must treat request 9 as potentially committed even though node 2 has not received its acknowledgment or advanced its commit index in the illustrated state.
  Why it matters: A follower cannot base safety on a leader state it cannot observe.
• Request preservation after election: Trace why request 9 is not lost after node 2 crashes: node 1 has the most up-to-date log, is the only eligible new leader, and propagates the missing entry to node 3 before advancing its commit index.
  Why it matters: Leader election and subsequent replication preserve the request despite the old leader's crash.

Key terms: acknowledgment, commit index, state machine safety, most up-to-date log, leader

10.8 Summary

The chapter summary recaps how state machine replication enables distributed consensus, why failures make consensus difficult, and how Raft divides the task.