10 - Distributed Consensus

distributedsystem/books/think-distributed-systems

Split Brain Condition

1. The Challenge of Agreement

Distributed consensus allows a group of redundant physical processes to advance in lockstep to act as a single logical component. This guarantees that some processes in the group can compensate for the failure of others.

• The Problem: A set of concurrent processes must agree on a single value over an unreliable network where components can crash, and messages can be lost, reordered, delayed, or duplicated.
• Two-Phase Commit (2PC) vs. Consensus:
  • 2PC blocks if the coordinator fails, sacrificing liveness to preserve safety.
  • Consensus algorithms guarantee safety and actively prioritize liveness, ensuring no single component failure can halt the entire system.

💡 Aha! Moment: The FLP Impossibility Theorem

Credited to Fischer, Lynch, and Paterson, this theorem proves that in a fully asynchronous distributed system without clocks, it is impossible to guarantee deterministic consensus if even a single node can crash.

To bypass this limit, real-world consensus protocols introduce weak synchrony assumptions (such as clocks or partial synchrony with timeouts) to ensure liveness.

2. Formal System Model & Properties

Let a distributed system be a collection of processes ($\text{Processes}$) and a set of values ($\text{Values}$).

• $\text{Propose}(p,v)$ represents process $p$ proposing value $v$.
• $\text{Decide}(p,v)$ represents process $p$ deciding on value $v$.

A valid consensus algorithm must satisfy three safety properties and one liveness property:

Safety Properties

• Validity: If a process decides on $v$, then $v$ must have been proposed by some process:
  $\forall p\in \text{Processes},\text{Decide}(p,v)\Rightarrow \exists q\in \text{Processes},\text{Propose}(q,v)$
• Integrity: If a process decides on $v$, that decision is permanent and cannot be changed:
  $\forall p\in \text{Processes},\forall v,v^{\prime }\in \text{Values}:\text{Decide}(p,v)\wedge \text{Decide}(p,v^{\prime })\Rightarrow v=v^{\prime }$
• Agreement: No two correct (non-failed) processes decide on different values:
  $\forall p,q\in \text{Processes},\forall v,v^{\prime }\in \text{Values}:\text{Decide}(p,v)\wedge \text{Decide}(q,v^{\prime })\Rightarrow v=v^{\prime }$

Liveness Property

• Termination: Every non-failed process eventually decides on some value $v$ (using temporal logic where $\diamond$ means eventually and $\square$ means always):
  $\forall p\in \{p^{\prime }\in \text{Processes}\mid \text{alive}(p^{\prime })\},\exists v\in \text{Values}:\diamond \square (\text{Decide}(p,v))$

3. State Machine Replication (SMR)

State Machine Replication is the primary engineering mechanism that transforms a collection of physical components into a single fault-tolerant logical component.

                    ┌─────────────────────────────────┐
                    │        Consensus Engine         │
                    │   (Guarantees Log Order)        │
                    └────────────────┬────────────────┘
                                     │ Committed Input Log
                                     ▼
                     ┌───────────────────────────────┐
                     │   Deterministic State Machine │
                     │   (State Transitions)         │
                     └───────────────────────────────┘

• Core Principle: If two identical, deterministic processes start in the same initial state and receive the exact same inputs in the exact same order, they will transition to the same state and produce the exact same output.
• Reduction: Enforcing SMR reduces the problem of distributed state replication to consensus on the ordered log of inputs.

Historical Foundations

• Paxos (Leslie Lamport, 1989): Groundbreaking protocol modeling consensus as a single decision on a write-once register. Multi-Paxos extends this to a series of decisions suitable for SMR logs.
• Viewstamped Replication (Oki & Liskov, 1988): Actually predates Paxos as the first published algorithm solving distributed consensus, though it did not explicitly brand itself under the name “consensus”.

4. Architectural Patterns: Leader + Quorum

Modern consensus protocols (Raft, Multi-Paxos, VR) combine a single Leader architecture with Quorum-based validation.

Leader-Based Consensus (The Dictator)

In a perfect network, a designated leader (Benevolent Dictator for Life or BDFL) receives all client requests, sequences them, and broadcasts them. However, in real systems:

• If the leader crashes, the system halts (loss of liveness).
• Network partitions can isolate the leader, leading to split-brain.

Quorum-Based Consensus (Majority Rule)

To prevent split-brain and tolerate crashes, consensus requires agreement from a quorum ($Q$) of processes:
$Q>\frac{N}{2}$

• Quorum Intersection Property: Any two quorums must overlap by at least one process:
  $Q_1\cap Q_2\ne \varnothing$
  This ensures that at least one node in a newly formed quorum possesses the history or decisions made by previous quorums, preventing conflicting split-brain decisions.
• Tolerating $f$ Failures: To compensate for $f$ concurrent failures, a system must contain at least $f+1$ operational nodes to form a quorum. Thus, the minimum cluster size $N$ is:
  $N=f+(f+1)=2f+1$

5. The Raft Consensus Protocol

Raft decomposes the distributed consensus and SMR problem into logical sub-problems: Leader Election, Log Replication, and State Machine Safety.

Logical Time: Terms

Raft divides time into monotonically increasing integer terms (acting as logical clocks).

• Each term begins with a Leader Election phase, followed by a Log Replication phase.
• Terms as Fencing Tokens: If a network partition causes a stale leader to remain active, its low term number acts as a fencing token. Followers reject any messages containing term numbers lower than their current term.

The Three Node States

1. Follower: Passive state. Resets an randomized election timer upon receiving heartbeats from the Leader. If the timer expires, transitions to Candidate.
2. Candidate: Increments current term, votes for itself, and broadcasts RequestVote RPCs.
   • Quorum Vote: Wins election if it receives votes from a majority.
   • Split Vote: No candidate wins. Initiates a new term election.
   • Demotion: Discovers a leader with a higher term and steps down to Follower.
3. Leader: Orchestrates client operations, manages log replication, and issues heartbeats.

Log Replication Flow

1. Accept: Leader accepts a command from a client.
2. Append: Leader writes the command to its local log.
3. Propagate: Leader sends AppendEntries RPCs to followers.
4. Commit: Once a quorum of followers acknowledges appending the entry, the leader advances its commit index and applies the entry to its local state machine.

State Machine Safety (The Leader Completeness Property)

Raft guarantees that if a log entry is applied to a state machine at a given index, no other node will ever apply a different entry for that index.

• Election Restriction: A follower will only vote for a candidate if the candidate’s log is at least as up-to-date as its own.
• Up-to-Date Comparison Rules:
  1. Compare the term of the last log entries: the log with the higher term is more up-to-date.
  2. If terms are equal, compare log lengths: the longer log is more up-to-date.

6. Raft Puzzles Breakdown

These puzzles assume a 3-node cluster operating in Term 3.

Puzzle 1: Identifying the Leader

• State: Node 1 has log entries up to index 8. Node 2 has entries up to index 9. Node 3 has entries up to index 7.
• Analysis: Only the leader can accept client requests directly and write them to its log before propagating them.
• Conclusion: Node 2 is the leader of Term 3 because its log is the most advanced (index 9).

Puzzle 2: Unpropagated Entry Loss

• State: Node 2 (leader) accepts request 9, appends it locally, but crashes before sending it to Node 1 or Node 3.
• Analysis: When Node 2 crashes, a new leader must be elected for Term 4. Because request 9 was only on Node 2, the newly elected leader will not have this entry.
• Conclusion: Yes, request 9 is lost. This does not violate state machine safety because the entry was never committed (it was not replicated to a quorum).

Puzzle 3: Propagated, Uncommitted Crash (The Wizard’s Puzzle)

• State: Node 2 (leader) appends request 9, propagates it to Node 1, and gets an acknowledgment. Node 2 crashes before it can write a commit index update or reply to the client.
• Analysis:
  • Request 9 is present on a quorum of nodes ($\{\text{Node 1},\text{Node 2}\}$).
  • Node 1 cannot determine whether the leader crashed before or after committing. To guarantee state machine safety, the system must treat this entry as committed.
  • Node 3 (log length 8) and Node 1 (log length 9) are active. Node 3 cannot become leader because Node 1’s log is longer and more up-to-date; Node 1 will deny Node 3’s vote request.
  • Node 1 is elected leader for Term 4.
• Conclusion: No, request 9 is not lost. Upon election, Node 1 will propagate entry 9 to Node 3, advance its commit index, and formally commit it to the state machine.