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.
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.

Interactive Architecture Diagram
100%Fit100%
Synthesizing vector architecture diagram...

---

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.

Interactive Architecture Diagram
100%Fit100%
Synthesizing vector architecture diagram...

1. Leader Election & Mathematical Quorum

• Nodes start as Followers. If a follower receives no heartbeat within a randomized electionTimeout ($150\text{--}300\text{ ms}$), it transitions to Candidate, increments its currentTerm, votes for itself, and broadcasts RequestVote RPCs.
• 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 is Committed once it is safely written on a majority of nodes ($Q$).
• 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.
2. LeaseRead Protocol: The Leader relies on a physical time-bounded lease. As long as $t_{\text{now}} < t_{\text{last\_majority\_ack}} + T_{\text{lease}}$, it serves reads locally with zero network hops.

---

Step-by-Step Deterministic Write & Replication Pipeline

Interactive Architecture Diagram
100%Fit100%
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.

Interactive Architecture Diagram
100%Fit100%
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 immediately with zero downtime.
  4. The retiring node drains client gRPC connections and shuts down gracefully without triggering cluster-wide election storms.

---