What is the Paxos Consensus Algorithm?
Understand the Paxos algorithm: prepare/promise and accept phases, safety guarantees, and how Multi-Paxos agrees on a log.
Expected Interview Answer
Paxos is a consensus algorithm that lets a group of nodes agree on a single value even with failures and message loss, using two phases (prepare/promise, then accept/accepted) where a proposer must win acknowledgement from a majority of acceptors at each phase before a value is chosen.
In the prepare phase, a proposer picks a globally increasing proposal number and asks acceptors to promise not to accept any earlier-numbered proposal; if a majority promise, the proposer moves to the accept phase, proposing a value (either its own, or the highest-numbered value already accepted by any acceptor in its promises, to preserve safety). If a majority of acceptors accept that proposal, the value is chosen and durable, since any future proposer running the algorithm is guaranteed to discover that value through the promise step. Paxos guarantees safety (only one value is ever chosen) at the cost of being notoriously difficult to reason about and implement correctly, which is why Raft was later designed as a more understandable alternative that achieves equivalent guarantees. Multi-Paxos extends the basic protocol to efficiently agree on a sequence of values (a log) by electing a stable leader/proposer, similar in spirit to Raft.
- Guarantees safety (no two different values are ever chosen) even under message loss and node failure
- Tolerates up to a minority of failed nodes while still making progress
- Forms the theoretical foundation many production consensus systems build on
- Multi-Paxos generalizes the protocol to efficiently agree on an ordered log of values
AI Mentor Explanation
Paxos is like a selection committee choosing the captain through two rounds instead of a simple show of hands. First, a nominator sends a numbered proposal asking committee members to promise not to consider any earlier-numbered nomination (prepare/promise); once a majority promise, the nominator proposes an actual name, favoring any name a majority already leaned toward, to avoid contradicting an earlier near-decision. Only when a majority formally accepts that name is the captaincy finalized, and any later nominator is guaranteed to discover that choice through the same promise step. This two-phase, majority-confirmed process is exactly what Paxos does to safely choose one value across unreliable committee members.
Step-by-Step Explanation
Step 1
Prepare phase
A proposer picks an increasing proposal number and sends a Prepare request to acceptors, asking them to promise to ignore earlier-numbered proposals.
Step 2
Promise responses
Acceptors reply with a promise plus any higher-numbered proposal they already accepted, if one exists.
Step 3
Accept phase
If a majority promised, the proposer sends an Accept request with a value — either its own, or the highest already-accepted value from the promises, to preserve safety.
Step 4
Value chosen
Once a majority of acceptors accept that proposal, the value is chosen and any future round is guaranteed to discover it.
What Interviewer Expects
- Explains the two-phase structure: prepare/promise then accept/accepted
- Explains why a proposer must adopt the highest already-accepted value in phase two (safety)
- Mentions the majority-quorum requirement at each phase
- Can contrast Paxos with Raft on understandability and mentions Multi-Paxos for log-based agreement
Common Mistakes
- Skipping the safety rule that forces a proposer to reuse an already-accepted value
- Confusing single-value (basic) Paxos with Multi-Paxos, which agrees on an ordered log
- Claiming Paxos guarantees liveness/progress without qualification (it can stall under contention — the FLP result)
- Describing Paxos as a single-phase majority vote
Best Answer (HR Friendly)
“Paxos is a way for a group of computers to agree on one value even if some of them are slow or fail. It works in two rounds: first a proposer checks that enough machines are willing to consider its idea, and then it asks them to formally accept a value, making sure it never contradicts something a majority may have already leaned toward, so the whole group ends up agreeing safely on exactly one answer.”
Code Example
class PaxosProposer:
def __init__(self, proposal_number, acceptors):
self.n = proposal_number
self.acceptors = acceptors
def propose(self, initial_value):
# Phase 1: Prepare
promises = [a.prepare(self.n) for a in self.acceptors]
promises = [p for p in promises if p is not None]
if len(promises) <= len(self.acceptors) / 2:
return None # no majority, retry with higher n
# Adopt the highest-numbered already-accepted value, if any
accepted = [p for p in promises if p.accepted_value is not None]
value = initial_value
if accepted:
highest = max(accepted, key=lambda p: p.accepted_n)
value = highest.accepted_value
# Phase 2: Accept
acks = [a.accept(self.n, value) for a in self.acceptors]
if sum(1 for ok in acks if ok) > len(self.acceptors) / 2:
return value # value is chosen
return NoneFollow-up Questions
- Why must a proposer reuse the highest-numbered already-accepted value instead of its own?
- How does Multi-Paxos avoid running two phases for every single value in a log?
- What real-world systems are known to use Paxos or a Paxos variant?
- How does Paxos handle the case where two proposers compete simultaneously (dueling proposers)?
MCQ Practice
1. What are the two phases of basic Paxos?
Basic Paxos consists of a prepare/promise phase followed by an accept/accepted phase, each requiring a majority.
2. In the accept phase, which value must a proposer use if acceptors already promised having accepted one?
Reusing the highest-numbered already-accepted value is the key safety rule that prevents two different values from being chosen.
3. Why was Raft designed after Paxos already existed?
Raft was explicitly designed for understandability, decomposing the problem into leader election, log replication, and safety, while matching Paxos guarantees.
Flash Cards
What are the two phases of Paxos? — Prepare/promise, then accept/accepted — each requiring a majority of acceptors.
What is the key safety rule in the accept phase? — The proposer must adopt the highest-numbered value already accepted by any acceptor in the promises, if one exists.
What is Multi-Paxos? — An extension that agrees on an ordered log of values efficiently, using a stable leader instead of running full Paxos per entry.
Why is Paxos considered hard? — Its safety proof and edge cases (dueling proposers, liveness) are notoriously difficult to reason about and implement correctly.