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

4. How Paxos Differs from Raft (Basic Paxos and Multi-Paxos)

Raft and Paxos solve the same problem with the same safety rule: a value is chosen only when a majority of nodes has stored it. The difference is how the two protocols are described and how much work they do per value. Raft describes one leader and one log. Paxos describes a two-phase vote on a single value, and builds the leader and the log on top of it.

Basic Paxos: one two-phase vote for one value

Basic Paxos chooses exactly one value for one slot. It has three roles. A proposer suggests a value. An acceptor votes on proposals. A learner finds out which value was chosen. In practice every node plays all three roles. Each proposal carries a proposal number $n$ (also called a ballot number). Every proposer uses numbers that are unique to it and larger than any number it used before, for example $n = \text{round} \times \text{number of nodes} + \text{node id}$.

1. Phase 1, Prepare and Promise. The proposer sends Prepare(n) to the acceptors. An acceptor compares $n$ with the highest proposal number it has already promised. If $n$ is higher, the acceptor replies Promise(n) and records a promise to ignore every proposal numbered lower than $n$. The reply also includes the proposal the acceptor last accepted, if there is one: its number and its value. If $n$ is not higher, the acceptor ignores the request.
2. Phase 2, Accept and Accepted. The proposer waits for promises from a majority of acceptors. It then chooses the value $v$ to propose. If any promise carried an already accepted proposal, $v$ must be the value from the accepted proposal with the highest number. Only when no promise carried any accepted proposal may the proposer use its own value. It sends Accept(n, v). An acceptor accepts unless it has since promised a higher number. It replies Accepted(n, v). The value $v$ is chosen once a majority of acceptors has accepted the same proposal, and learners are told.

The rule in step 2 is the whole safety argument. Once a majority has accepted $v$, every later majority of promises overlaps that majority in at least one acceptor, and that acceptor reports $v$. A later proposer is therefore forced to re-propose $v$ instead of its own value, so a chosen value can never be replaced.

A concrete run with five acceptors ($S_1$ to $S_5$). Proposer $S_1$ sends Prepare(7). $S_1$, $S_2$ and $S_3$ reply Promise(7) with no accepted proposal. $S_1$ sends Accept(7, x=10). $S_1$, $S_2$ and $S_3$ reply Accepted(7, x=10), so $x=10$ is chosen. Now $S_5$ sends Prepare(9). $S_3$, $S_4$ and $S_5$ reply Promise(9), and $S_3$ reports that it accepted $(7, x=10)$. $S_5$ wanted to propose $x=20$, but the rule forces it to send Accept(9, x=10). The chosen value survives.

Basic Paxos has two costs. Every value needs two round trips, Prepare then Accept. And two proposers can block each other forever: each one's Prepare cancels the other's promises before its Accept arrives. This is a livelock, which means every node keeps working but no value is ever chosen. Basic Paxos does not define a leader, so nothing in the protocol stops this. Real systems add a leader or a random back-off, exactly as Raft adds randomized election timeouts.

Multi-Paxos: one leader, Phase 1 once, Phase 2 per value

A replicated log needs one chosen value per log slot. Running Basic Paxos separately for every slot would cost two round trips per write. Multi-Paxos removes that cost. One node is elected as the distinguished proposer, which is the leader. It runs Phase 1 once with a single proposal number that covers every future slot. From then on it runs only Phase 2 for each new value: one Accept round, acknowledged by a majority. That is one round trip per write, the same cost as a Raft AppendEntries round. The leader stays leader until another node suspects it has failed and runs its own Phase 1 with a higher number.

The mapping between the two protocols

Two differences matter in practice.

1. Who may become leader. In Raft, a voter refuses a candidate whose log is less up-to-date than its own. The winner already holds every committed entry, so it never needs to ask for missing values. In Multi-Paxos, any node may become leader. It learns the accepted values it must keep from the Promise replies, then re-runs Phase 2 for every slot that was accepted but not yet chosen before it can serve new writes.
2. Holes in the log. A Raft log is contiguous: the leader appends entries in index order, and a follower accepts entry $i$ only after it holds entry $i-1$. Multi-Paxos decides each slot independently, so slot 12 can be chosen before slot 11. A new leader must fill every such gap, usually with a no-op value, before the state machine can apply the entries after it. Raft avoids this bookkeeping. This is the reason the Raft paper calls its design "understandable", and the reason etcd, Consul and CockroachDB chose it.

Where each one runs today is in the section Real-World Distributed Engine Comparison: Google Chubby and Google Spanner run Multi-Paxos, Amazon DynamoDB replicates each partition with a leader-driven Multi-Paxos group, and Apache Cassandra lightweight transactions run one Basic Paxos round per operation.

---

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.

---