System Design AI

Paxos in System Design Interviews: When to Use It and What to Say

Paxos is a distributed consensus protocol that lets a set of machines agree on one value even when some of them crash or messages are delayed.

The problem Paxos solves

When you replicate data across several servers, you need a single source of truth for the order of writes. Without a consensus algorithm, two nodes could accept different writes for the same logical slot, leading to divergent state and data loss. A concrete example is a write-ahead log for a distributed database. Each log entry must be placed at the same index on every replica, otherwise recovery becomes impossible.

How Paxos works – step by step

Paxos has three roles that any node can assume: Proposer, Acceptor, and Learner. The protocol proceeds in two phases.

Phase 1 – Prepare

  1. A proposer picks a monotonically increasing proposal number n and sends a Prepare(n) to a majority of acceptors.
  2. Each acceptor replies with Promise(n, nₚ, vₚ), promising not to accept any proposal with a number lower than n. It also includes the highest-numbered proposal it has already accepted ( nₚ ) and its value ( vₚ ), if any.

Phase 2 – Accept

  1. After receiving promises from a majority, the proposer selects the value v from the highest nₚ it learned, or chooses its own value if none were reported.
  2. It sends Accept(n, v) to the same majority.
  3. Acceptors that have not promised a higher number respond with Accepted(n, v), recording the value.
  4. Learners (often the same nodes) are notified once a majority has accepted the same (n, v) pair, and they consider the value chosen.

Small worked example

  • Three nodes: A, B, C. Majority = 2.
  • Proposer on A picks n = 1 and sends Prepare(1) to B and C.
  • B replies Promise(1, null, null). C replies Promise(1, null, null).
  • A now sends Accept(1, "X") to B and C.
  • B and C store "X" and reply Accepted(1, "X").
  • Learners see two Accepted messages, declare "X" chosen.

If B later crashes and a new proposer on C picks n = 2, it will learn that proposal 1 was already accepted and must propose the same value "X" to preserve consistency.

Where Paxos shows up in classic interview questions

Interview QuestionWhere Paxos Appears
Design a highly-available lock service (e.g., Chubby)In the lock-grant path to decide which client holds the lock at a given time.
Build a replicated log for a distributed database (e.g., write-ahead log)To order log entries across replicas before they are applied.
Design a leader election system for a clusterThe election itself can be modeled as a single-value consensus where the value is the elected node’s ID.

Trade-offs and the alternative interviewer will ask about

AspectPaxosTypical Alternative (Raft)
UnderstandabilityComplex; many papers describe separate roles and phases.Simpler; combines leader election and log replication in one flow.
LatencyTwo round-trips in basic Paxos (prepare + accept); Multi-Paxos with a stable leader skips prepare and needs one.Often one round-trip once a stable leader exists.
Failure handlingWorks with any majority of nodes; no single leader required.Relies on a stable leader; leader failure triggers a new election.
Implementation effortHigh; need to manage proposal numbers, persistent promises, and learner notifications.Moderate; leader handles most coordination, reducing code paths.

Interviewers typically follow up with “What if we need lower latency?” or “Can we simplify the protocol?” Expect them to steer toward Raft or quorum-based writes as a more interview-friendly alternative.

30-second spoken version

"Paxos is a consensus algorithm that lets a group of servers agree on a single value despite crashes. It works in two phases: a proposer asks a majority of acceptors to promise not to accept lower-numbered proposals, then it proposes a value that the majority accepts. The chosen value is the one that a majority has accepted. It’s used wherever you need a consistent order of writes, like a replicated log or a distributed lock service. The downside is extra latency and complexity; many interviewers prefer Raft, which is easier to explain, though with a stable leader Raft and Multi-Paxos both commit in one round trip."

Common mistakes candidates make

  • Skipping the prepare phase: Claiming that a proposer can just broadcast a value ignores the safety guarantees that promises provide.
  • Confusing majority with all nodes: Saying Paxos needs all nodes to agree leads to unnecessary pessimism; a majority is sufficient.
  • Omitting failure scenarios: Not describing what happens when an acceptor crashes after promising but before accepting leaves the protocol incomplete.
  • Mixing up roles: Treating proposer, acceptor, and learner as separate services when the interview expects a single node to play all three.
  • Forgetting to mention persistent state: Paxos requires acceptors to store the highest promised number and accepted value on durable storage; overlooking this makes the design unrealistic.

How to practice this

  1. Study the worked design for a consensus module with Raft in the System Design AI library, and note which parts of it do the jobs Paxos gives to proposers, acceptors and learners.
  2. On the canvas, redraw the diagram from memory, labeling the two phases and the flow of messages.
  3. Use the AI coach to review your canvas. Ask it to point out missing steps or unclear explanations, then iterate until you can walk through the protocol in 30 seconds without notes.

Questions people ask

When should I bring up Paxos in a system design interview?

Mention Paxos when the problem involves agreeing on a single value across replicas, such as a distributed lock service, a replicated log, or leader election. It signals you understand consistency under failure.

How does Paxos differ from Raft?

Paxos is more generic and splits responsibilities into proposer, acceptor, and learner, leading to higher conceptual complexity. Raft combines these into a leader-driven model, making it easier to explain; with a stable leader its latency matches Multi-Paxos, which also skips the prepare phase.

What is the minimum number of nodes needed for Paxos to make progress?

Progress requires a majority of nodes. With *n* replicas, you need floor(n/2)+1 nodes to form a quorum and choose a value.

Can Paxos handle network partitions?

Yes, as long as a majority of nodes remain connected. The partition without a majority cannot make progress, preserving safety while the majority continues to operate.