Distributed Consensus (Raft & Paxos)

1. What It Is & Why It Exists

The Core Problem: Agreement Across Unreliable Networks

In a distributed system, physical servers must coordinate state changes over an asynchronous, unreliable network subject to packet loss, arbitrary latency spikes, network partitions, and unannounced node crashes without Byzantine malice.

Coordinating state across such an environment without a single point of failure introduces the Distributed Consensus Problem: how can a cluster of independent machines agree on a single, deterministic sequence of values or state transitions?

The FLP Impossibility Theorem (Fischer, Lynch, Paterson, 1985)

The foundational theorem of distributed computing proves that in a purely asynchronous network, no deterministic consensus protocol can guarantee both Safety and Liveness in the presence of even a single unannounced fail-stop crash:

• Safety: Nothing bad happens (the cluster never commits two conflicting states or elects two active leaders).
• Liveness: Something good eventually happens (the cluster never deadlocks and always makes progress).

The Breakdown: Asynchronous Replication vs. 2PC vs. Quorum Consensus

Concrete Proof: The Split-Brain Blackout vs. Quorum Safety

Consider a 5-node cluster experiencing an asymmetric network partition dividing the cluster into two segments: a minority partition of 2 nodes ($S_1, S_2$) and a majority partition of 3 nodes ($S_3, S_4, S_5$):

---

The First-Principles Solution: Quorum-Based Replicated State Machines

Practical consensus protocols (Raft, Multi-Paxos, Zab) circumvent the FLP Impossibility Theorem by introducing partial synchrony (randomized timers and heartbeat timeouts):

1. Absolute Safety: Safety is mathematically guaranteed under all asynchronous conditions, regardless of network delays or packet reordering.
2. Conditional Liveness: Liveness is guaranteed as long as a strict mathematical majority quorum of nodes ($Q = \lfloor N/2 \rfloor + 1$) can communicate, with messages arriving well within the election timeout often enough for a leader to be elected and stay elected.
3. Replicated State Machine (RSM) Model: If identical deterministic state machines on multiple servers process an identical, ordered sequence of inputs from a consensus log, they will produce an identical, consistent state across all nodes.

Synthesizing vector architecture diagram...

Both panels start with a five-node cluster split by a network partition into groups of 2 and 3. In the "Broken Baseline" panel, there is no quorum rule, so each side elects its own leader, Node 1 accepts x=10 and Node 3 accepts x=20, and when the network heals the two histories conflict and one side's writes must be thrown away. In the "Production Standard" panel, Raft requires 3 of 5 votes: the 2-node minority's old leader cannot get a quorum, so it may keep appending writes to its log but can never commit them (its clients time out, and those entries are deleted when it rejoins), while the 3-node majority elects Node 3 as leader for term 2 and keeps committing. A cluster of 2F+1 nodes survives F failures, and a minority can never commit, so the two sides can never disagree.

---

2. Core Mechanics & Algorithmic Architecture

The Raft Algorithm: 3 Decomposed Sub-Mechanisms

Raft decomposes the consensus problem into three strictly formalized sub-problems: Leader Election, Log Replication, and Safety.

Synthesizing vector architecture diagram...

Every node boots as a Follower and waits for heartbeats. If none arrives within its randomized election timeout (150-300 ms in the Raft paper's example; etcd's default is 1,000 ms, randomized between 1x and 2x), it becomes a Candidate, increments its term, votes for itself, writes its term and vote to disk, and asks the others for votes. From Candidate there are three ways out: a majority of votes makes it Leader; learning of a valid leader with a current or higher term sends it back to Follower; and a split vote makes it time out and start again with a higher term. A Leader stays leader until it sees any message with a higher term, then immediately steps down to Follower. The term number is Raft's logical clock: a higher term always wins, which is what guarantees at most one leader per term.

1. Leader Election & Mathematical Quorum

• Nodes start as Followers. If a follower receives no heartbeat within a randomized electionTimeout ($150\text{--}300\text{ ms}$ in the Raft paper's example; etcd defaults to $1,000\text{ ms}$, randomized up to twice that), it transitions to Candidate, increments its currentTerm, votes for itself, writes currentTerm and votedFor to disk (otherwise a restarted node could vote twice in one term), and broadcasts RequestVote RPCs.
• Election restriction: a voter refuses a candidate whose log is less up-to-date than its own (a later last term wins; with equal last terms, the longer log wins). A committed entry is on a majority and a winner needs a majority of votes, so the two share a node, and that node refuses any candidate missing the entry: every committed entry survives an election.
• A Candidate becomes Leader only after securing votes from a strict mathematical quorum:

$$Q = \left\lfloor \frac{N}{2} \right\rfloor + 1$$ $$\text{Fault Tolerance Bound } (F) = \left\lfloor \frac{N - 1}{2} \right\rfloor$$

• For $N = 3$, $Q = 2$ (tolerates $1$ node failure).
• For $N = 5$, $Q = 3$ (tolerates $2$ node failures).
• An even-numbered cluster ($N = 4$) requires $Q = 3$ votes, providing the exact same fault tolerance ($F = 1$) as $N = 3$ while increasing network overhead. Always deploy odd-numbered clusters ($N=3, 5, 7$).

2. Log Replication & The Log Matching Property

• The Leader receives commands from clients, appends them to its local Write-Ahead Log, and broadcasts AppendEntries RPCs.
• An entry from the leader's current term is Committed once it is safely written on a majority of nodes ($Q$). Raft never commits entries from earlier terms by counting replicas: a new leader first appends and commits a no-op entry in its own term, and every earlier entry becomes committed with it. Until that no-op commits, a new leader doesn't know the commit index and can't serve linearizable reads (the section The leader crashes: elections of Replication, Quorums & Read-Your-Writes).
• Log Matching Invariant: If two distinct logs contain an entry with the same index and term, they are guaranteed to store identical commands in all entries up through that index.

3. Linearizable Reads (Avoiding Stale Reads on Partitioned Leaders)

If a Leader is partitioned off, it might respond to read queries with stale data before discovering its isolation. Raft guarantees linearizable reads via two protocols:

1. ReadIndex Protocol: The Leader records its current commitIndex, broadcasts a heartbeat to confirm it still commands a majority quorum, and serves the read once ACKs arrive and it has applied up to the recorded index. A deposed leader cannot collect a majority, so its read fails instead of returning stale data.
2. LeaseRead Protocol: The Leader relies on a physical time-bounded lease, timed from the send time of the last heartbeat a majority acknowledged: as long as $t_{\text{now}} < t_{\text{heartbeat\_sent}} + T_{\text{lease}}$, it serves reads locally with zero network hops. $T_{\text{lease}}$ must be shorter than the minimum election timeout minus a margin for the difference in clock rates, so the lease ends before any other node can win an election. Unlike ReadIndex, this relies on clocks and bounded pauses for safety (the section A network partition and two leaders of Replication, Quorums & Read-Your-Writes; clock margins in the section Time: whose clock decides? of Leases, Fencing Tokens & Distributed Locks).

---

Step-by-Step Deterministic Write & Replication Pipeline

Synthesizing vector architecture diagram...

---

In-Memory & Distributed State Structures

Every Raft node maintains three distinct classes of state in memory and on disk:

---

Consensus Scenario & Quorum State Matrix

Under a 5-node cluster ($S_1, S_2, S_3, S_4, S_5$) with quorum requirement $Q = \lfloor 5/2 \rfloor + 1 = 3$, and initial Term 2 Leader $S_1$:

---

3. Data Migration, Anti-Entropy & Consistency Protocols

1. Log Compaction & Snapshotting

Because an append-only log grows indefinitely, servers would eventually run out of disk space and take hours to replay logs upon reboot. Raft handles this via Memory Snapshotting:

• An application periodically takes a point-in-time snapshot of its state machine (e.g., at Index 10,000).
• All log entries up through Index 10,000 are deleted from disk.
• The InstallSnapshot RPC: If a lagging follower or newly added node is so far behind that its missing entries have already been compacted, the Leader streams its latest snapshot file directly to the follower over the network.

Synthesizing vector architecture diagram...

---

2. Dynamic Cluster Membership Changes (Joint Consensus)

Adding or removing nodes cannot be done via static configuration changes on all machines, as two independent majorities could vote at the same time during the rollout window.

• Raft Joint Consensus: The cluster transitions through an intermediate phase ($C_{\text{old}, \text{new}}$) where decisions require independent majorities from both the old configuration and the new configuration: $\text{Quorum}_{\text{Joint}} = \text{Majority}(C_{\text{old}}) \land \text{Majority}(C_{\text{new}})$
• Once $C_{\text{old}, \text{new}}$ is committed, the leader commits the final configuration $C_{\text{new}}$.

3. Accelerated Log Conflict Resolution & Graceful Draining

• Accelerated Log Backtracking: In naive Raft, if a follower's log diverges across 1,000 entries, the leader decrements nextIndex by 1 per rejected AppendEntries RPC (costing 1,000 network round-trips). In the optimized protocol, the follower returns the conflicting entry's term (conflictTerm) and the earliest index of that term (conflictIndex). The leader skips nextIndex past the entire conflicting term in a single RPC, accelerating log synchronization after network partition healing.
• Graceful Leader Step-Down & Node Draining: When an active leader node is selected for host maintenance or rolling restarts:
  1. Operator triggers etcdctl move-leader <target_follower_id> (or issues Raft TimeoutNow RPC).
  2. The leader halts client writes, synchronizes uncommitted log entries to the target follower, and commands the follower to initiate an immediate election without waiting for election timeout.
  3. The target follower wins the election at once, so writes pause only briefly instead of for a full election timeout.
  4. The retiring node drains client gRPC connections and shuts down gracefully without triggering cluster-wide election storms.

---