How it works
Basic Paxos chooses one value for one decision, such as the command at log position 42. Nodes act as proposers, acceptors, and learners; one server can fill all three roles. In the standard majority-based setup, three acceptors require two votes, and five require three.
Phase 1 is prepare and promise. A proposer selects a unique, ordered ballot number and sends a prepare request. Acceptors that have not promised a higher ballot persist a promise not to accept lower ballots, then report any value they previously accepted and its ballot.
After receiving promises from a majority, the proposer must use the value with the highest accepted ballot among those responses. If none reports an accepted value, it may propose a new value. This rule, together with intersecting majorities, prevents a later proposal from replacing a value that was already chosen.
Phase 2 is accept. The proposer sends the selected value and ballot to acceptors, which accept unless they have promised a higher ballot. Once a majority has accepted that proposal, its value is chosen, even if the proposer crashes before announcing the result. Acceptors persist promises and accepted proposals before replying so crashes do not erase the safety rules.
Multi-Paxos applies these rules across log positions. A stable leader can complete phase 1 for its ballot across the log, recover prior accepted entries, and then use phase 2 for new entries without repeating prepare each time. Replicas learn chosen entries and apply commands in log order to a deterministic state machine.
Paxos preserves agreement under arbitrary message delays, but progress is not guaranteed under perpetual contention or an indefinitely delayed network. Practical systems use timeouts, retries, and an eventual stable leader with a reachable majority. Linearizable reads need an additional safe read protocol; reading any replica is not automatically safe.
A worked example
Recovering a chosen entry after a leader crash
A replicated key-value shard has three acceptors: A, B, and C. At log position 42, leader A proposes `set balance=90` in ballot 7. A and B durably accept it, so the value is chosen, but A crashes before replying to the client. C starts ballot 8 and receives promises from B and C. B reports the accepted value from ballot 7. C must propose that value for position 42, not a different write, and can finish the decision with B. The client may still see a timeout, so its retry needs a request ID recorded with the replicated command. If B also becomes unreachable, C alone cannot choose further entries.
Trade-offs to say out loud
- Safety over write availability during partitions
- Only a partition with a majority can choose new values; a minority must reject or delay writes rather than decide independently.
- Replication adds latency
- A stable Multi-Paxos leader waits for durable acceptance from a majority, so quorum network latency and storage latency affect writes.
- Leader stability improves throughput
- A stable leader amortizes prepare work, while competing proposers can repeatedly preempt one another and stall progress.
- Implementation is more than two phases
- Recovery, log gaps, snapshots, membership changes, and client retries require careful protocols beyond basic Paxos.
- Fault tolerance has a defined scope
- Standard Paxos handles crash and recovery failures, not malicious nodes or nodes that violate the protocol.
- Consensus does not cover external effects
- Choosing a command once does not make a payment or email execute exactly once, so external actions still need idempotency and reconciliation.
When to reach for it
- Replicas must agree on an authoritative write order, and acknowledged writes must survive leader failover.
- A control plane needs one agreed ownership or configuration history rather than conflicting decisions during a partition.
- The design explicitly favors consistent decisions over accepting writes in every network partition.
- An interviewer asks how a new leader recovers unfinished proposals without overwriting a decision already made.
How to bring it up in the interview
- Start with the invariant: two different values must never be chosen for the same log position. Then explain majority intersection and the highest-accepted-ballot rule together.
- Distinguish basic Paxos from Multi-Paxos: one chooses a single value; the other builds an ordered log with a stable leader. Expect questions about recovery and gaps in that log.
- Define the acknowledgment boundary: durable majority acceptance, followed by whatever application step the API promises. Explain what happens if the response is lost and the client retries.
- Describe the partition policy explicitly. A minority cannot keep choosing writes, and timeouts indicate suspicion rather than proof that another node is dead.
- Prefer an established consensus-backed storage or coordination system over proposing a custom implementation. Expect follow-ups on linearizable reads, safe membership changes, and fencing stale owners.
Common mistakes
- Explaining Paxos as majority voting without the prepare promises and value-adoption rule that preserve earlier decisions.
- Treating acceptance by one node as a chosen value, or assuming a chosen value must already be known by every learner.
- Claiming Paxos always makes progress as long as a majority is alive; communication delays and competing proposers can still prevent progress.
- Assuming consensus automatically provides linearizable replica reads, multi-key transactions, or exactly-once external side effects.
- Assuming an agreed leader record stops an old leader from acting; downstream resources still need fencing or an equivalent enforcement mechanism.
Where it comes up
Interview questions where paxos is part of a strong answer, and why.
- Design a distributed message log like KafkaMulti-Paxos provides a model for choosing partition log entries and preserving acknowledged appends through leader failover.
- Design a distributed key-value storeA strongly consistent design can use Multi-Paxos per shard to order writes and recover safely after replica failures.
- Design a control plane for a distributed databaseConsensus-backed authority records make failover and ownership changes agree across control-plane replicas, with fencing needed to constrain stale actors.
Questions people ask
What is the Paxos algorithm used for?
Paxos lets distributed nodes agree on a value despite crashes and unreliable communication. Multi-Paxos uses repeated decisions to build a replicated log, which can underpin consistent storage and coordination services.
What is the difference between Paxos and Raft?
Both can support replicated state machines using intersecting majorities under crash failures. Raft presents leader election, log replication, and safety as an integrated protocol; basic Paxos describes agreement on one value, with Multi-Paxos extending it to a log. In interviews, defend the failure and consistency guarantees rather than treating either name as a complete design.
Is Paxos the same as two-phase commit?
No. Paxos reaches agreement among replicas, while two-phase commit coordinates whether transaction participants commit or abort. Their phases serve different purposes, and classic two-phase commit can block after coordinator failure; a reachable Paxos majority can make progress once leadership and communication stabilize.