Distributed Consensus Protocols: Paxos vs Raft Leader Election & Log Replication

Why You Need This in Real Life

A 5-node distributed configuration store (like etcd or Consul) manages dynamic IP addresses for 200 microservices.

Node 1 gets isolated by a brief network hiccup and believes it is still the leader. Simultaneously, Node 2 is elected as the new leader by the remaining majority. Node 1 accepts an IP update (auth-service = 10.0.1.5), while Node 2 accepts a different IP update (auth-service = 10.0.9.99).

Without a formal consensus protocol, both nodes execute writes locally, splitting the cluster into two conflicting realities (Split-Brain Syndrome). Half your microservices send user passwords to the wrong server IP.

Distributed Consensus Protocols guarantee that a cluster of nodes agrees on a sequence of state machine operations—even if network packets are delayed, dropped, or individual nodes crash.

To design resilient distributed coordination engines, you must master Leslie Lamport’s Paxos and Diego Ongaro / John Ousterhout’s Raft.

Part 1: Quorum Math ( $\lfloor N/2 \rfloor + 1$ )

All consensus protocols rely on Quorum Intersection Math to guarantee safety without requiring all nodes to be online.

For a cluster of $N$ nodes, a Majority Quorum $Q$ is defined as:

$Q = \lfloor N/2 \rfloor + 1$

In a 3-node cluster, Quorum = $2$ nodes. (Tolerates $1$ node failure).
In a 5-node cluster, Quorum = $3$ nodes. (Tolerates $2$ node failures).

          5-Node Cluster (Quorum = 3)

     [Node 1]     [Node 2]     [Node 3]   |   [Node 4]     [Node 5]
     <-------- Active Quorum (3) -------> |   <-- Partitioned Off (2) -->
     Can achieve consensus & accept writes! |   REJECTS WRITES! (No Quorum)

Because any two majority quorums in an $N$ -node cluster must overlap by at least one node, the overlapping node ensures that new leaders always possess the complete committed history of previous leaders.

Part 2: Paxos Protocol Mechanics

Proposed by Leslie Lamport in 1989, Basic Paxos achieves consensus on a single value through three roles (Proposers, Acceptors, Learners) across two phases:

Phase 1 (Prepare):
Proposer                    Acceptor 1      Acceptor 2      Acceptor 3
   |                            |               |               |
   |-- Prepare(n=101) --------->|               |               |
   |-- Prepare(n=101) ------------------------->|               |
   |                            |               |               |
   |<-- Promise(101, null) -----|               |               |
   |<-- Promise(101, null) ---------------------|               |

Phase 2 (Accept):
   |-- Accept(n=101, v="A") --->|               |               |
   |-- Accept(n=101, v="A") ------------------->|               |
   |                            |               |               |
   |<-- Accepted(101, v="A") ---|               |               |
   |<-- Accepted(101, v="A") -------------------|               |
   |
(Value "A" is officially COMMITTED!)

Paxos Weakness: Livelock (Dueling Proposers)

If Proposer 1 issues Prepare(n=101), and before Phase 2 completes, Proposer 2 issues Prepare(n=102), Acceptors will reject Proposer 1’s Accept(n=101) phase. Proposer 1 then retries with Prepare(n=103), aborting Proposer 2! This dueling loop can execute indefinitely without committing a value (Livelock).

Part 3: Raft Protocol Mechanics

Raft was designed in 2014 at Stanford specifically to address the extreme complexity and livelock vulnerabilities of Paxos. Raft decomposes consensus into three independent sub-problems:

Leader Election
Log Replication
Safety Guarantee

+-----------------------------------------------------------------------------+
|                         Raft Node State Transitions                         |
|                                                                             |
|            Times out,               Receives votes from                     |
|         starts election              majority of cluster                    |
|      +--------------------+       +----------------------+                  |
|      |                    |       |                      |                  |
|      v                    |       v                      |                  |
|  +-------+             +------------+             +--------+                |
|  |Follower| ---------> | Candidate  | --------->  | Leader |                |
|  +-------+             +------------+             +--------+                |
|      ^                                                   |                  |
|      |                                                   |                  |
|      +---------------------------------------------------+                  |
|                   Discovers higher Term number                              |
+-----------------------------------------------------------------------------+

1. Leader Election via Terms & Randomized Timers

Raft divides time into numbered Terms (monotonically increasing integer counters).
Each node maintains an Election Timer randomized between 150ms and 300ms.
If a Follower hears no heartbeat from the Leader before its randomized timer expires, it increments its Term number, transitions to Candidate, votes for itself, and broadcasts RequestVote(term, candidateId).
Randomized election timers prevent split votes, ensuring one Candidate receives majority votes before others time out.

2. Log Replication

When the Leader receives a client command:

It appends the command to its local log file.
It sends an AppendEntries RPC to all Followers.
Once a majority of Followers acknowledge writing the log entry, the Leader commits the entry and returns success to the client.
On subsequent heartbeats, the Leader notifies Followers of the commit index, and Followers apply the entry to their local state machines.

Leader Log:    [Term 1: Set X=1] [Term 1: Set Y=2] [Term 2: Set Z=3 (Committed)]
Follower 1 Log: [Term 1: Set X=1] [Term 1: Set Y=2] [Term 2: Set Z=3 (Committed)]
Follower 2 Log: [Term 1: Set X=1] [Term 1: Set Y=2] [Term 2: Set Z=3 (Committed)]

Part 4: Comparative Summary

Feature	Basic Paxos	Raft Protocol
Understandability	High mathematical abstraction; difficult to implement.	Designed specifically for clarity and ease of implementation.
Leadership	Symmetric (No strong leader required; any node can propose).	Strong Leader (All client writes and log entry flows pass through Leader).
Livelock Prevention	Requires Multi-Paxos or randomized backoff delays.	Guaranteed via randomized election timers (150ms–300ms).
State Machine	Consensus per value index.	Replicated sequential log array.
Real-World Uses	Google Chubby, Spanner (Multi-Paxos variant).	etcd, Consul, CockroachDB, Apache Kafka (KRaft).

Next Steps

Now that we understand Paxos and Raft consensus protocols, we will examine Distributed Locking in Part 9: dissecting lease expirations, Redlock, and ZooKeeper fencing tokens.

References & Further Reading

IETF. RFC 6585 — Additional HTTP Status Codes (429 Too Many Requests). Internet Engineering Task Force.
Nygard, M. T. (2018). Release It! Design and Deploy Production-Ready Software (2nd Edition). Pragmatic Bookshelf.
Netflix Engineering. Hystrix: Latency and Fault Tolerance for Distributed Systems. GitHub.