What are Raft and Paxos? Consensus Algorithms Explained
Learn how Raft and Paxos achieve distributed consensus via majority quorums, and how Raft simplifies leader election and log replication.
Expected Interview Answer
Raft and Paxos are consensus algorithms that let a group of distributed nodes agree on a single value or an ordered sequence of operations even when some nodes fail or messages are delayed, by requiring any accepted decision to be approved by a majority (quorum) of nodes.
Paxos, the original formalized solution, uses proposers, acceptors, and learners in a two-phase (prepare/promise, then accept/accepted) protocol that is provably correct but notoriously difficult to understand and implement safely, especially for its multi-decree (Multi-Paxos) form used to agree on a log of operations. Raft was designed later specifically to be more understandable while providing the same safety guarantees, by explicitly electing a single leader (via randomized election timeouts and terms) who is solely responsible for accepting client writes and replicating a log to followers, committing an entry once it is stored on a majority. Both algorithms tolerate up to floor((N-1)/2) node failures out of N nodes and are the foundation for keeping distributed databases and coordination services (etcd, ZooKeeper's ZAB, CockroachDB, Consul) consistent despite crashes and network partitions.
- Tolerates node failures while still reaching agreement
- Guarantees a consistent, ordered log across replicas (state machine replication)
- Raft trades some flexibility for a simpler, leader-based mental model
- Foundation for reliable distributed databases and coordination services
AI Mentor Explanation
Think of a five-member cricket selection committee that must agree on the final playing XI even if one or two members are unreachable; rather than needing all five to sign off, a majority of three is enough to finalize the decision, and everyone else accepts whatever the majority agreed on. Raft formalizes this by first electing a chairperson (the leader) who proposes the XI and only needs a majority to confirm it; Paxos achieves the same majority-agreement outcome without a fixed chairperson, using a more general propose-and-accept negotiation. Both guarantee the committee reaches one consistent decision even if some members are absent.
Step-by-Step Explanation
Step 1
Elect or nominate a proposer/leader
Raft elects a single leader per term via randomized timeouts; Paxos allows any node to act as a proposer for a given round.
Step 2
Propose a value or log entry
The leader (Raft) or proposer (Paxos) sends the proposed value/entry to the other nodes for approval.
Step 3
Collect a majority acknowledgment
The proposal is accepted once a majority (quorum) of nodes acknowledge it, tolerating up to floor((N-1)/2) failures.
Step 4
Commit and replicate
Once a majority accepts, the value/entry is committed and applied to each node's state machine in the same order.
What Interviewer Expects
- Understanding of the majority-quorum requirement for both algorithms
- Ability to explain Raft's leader-election and log-replication model clearly
- Awareness that Paxos is more general but harder to implement correctly than Raft
- Knowledge of real systems built on these algorithms (etcd, ZooKeeper, CockroachDB)
Common Mistakes
- Claiming these algorithms require unanimous agreement instead of a majority
- Not knowing the difference between single-decree Paxos and Multi-Paxos
- Describing Raft without mentioning leader election or terms
- Confusing consensus algorithms with simple primary-replica replication (which lacks automatic failover consensus)
Best Answer (HR Friendly)
“Raft and Paxos are algorithms that let a group of servers agree on the same decision even if some of them crash or lose connection, as long as more than half are still working. Raft does this by electing one clear leader who proposes changes, which makes it easier to understand, while Paxos achieves the same guarantee with a more flexible but harder-to-follow negotiation process.”
Code Example
-- Leader appends a new entry to its local log
log.append({ term: 5, index: 101, command: "UPDATE Orders SET status='SHIPPED' WHERE order_id=42" });
-- Leader sends AppendEntries RPC to all followers
for follower in followers:
send_append_entries(follower, term=5, entries=[log[101]]);
-- Entry is committed once a MAJORITY of nodes (including the leader) have it
if acknowledged_count >= (total_nodes / 2) + 1:
commit_index = 101;
apply_to_state_machine(log[101]); -- e.g. actually run the SQL update
-- Followers apply the same entry once they learn commit_index has advancedFollow-up Questions
- How does Raft's leader election prevent two leaders from being active in the same term?
- What is the difference between single-decree Paxos and Multi-Paxos?
- How do these consensus algorithms relate to the CAP theorem?
- Name a real distributed system that uses Raft or Paxos for coordination.
MCQ Practice
1. What is required for a value or log entry to be committed in Raft or Paxos?
Both algorithms only require a majority of nodes to acknowledge a proposal before it is considered committed.
2. What is the key design goal that distinguishes Raft from Paxos?
Raft introduces a clear leader-election and log-replication model specifically to be more understandable than Paxos.
3. With 5 nodes, how many node failures can a majority-quorum consensus algorithm like Raft typically tolerate and still make progress?
With N=5, floor((N-1)/2) = 2 failures can be tolerated while a majority of 3 nodes remains available.
Flash Cards
What problem do Raft and Paxos solve? — Getting distributed nodes to agree on a value or ordered log despite node failures and network delays.
How many nodes must agree to commit a value? — A majority (quorum) of nodes, not all of them.
Main difference between Raft and Paxos? — Raft uses explicit leader election for a simpler mental model; Paxos is more general but harder to implement correctly.
Name systems built on these algorithms. — etcd and CockroachDB use Raft; ZooKeeper uses a Paxos-like protocol called ZAB.