System Design AI

Paxos: The Follow-Up Questions Interviewers Ask, With Answers

Interviewers bring up Paxos because it is a classic consensus algorithm that sits at the heart of many distributed services. Mentioning it signals that you understand consistency, fault tolerance, and the need for a single source of truth.

From there they probe how deep your knowledge goes. They want to see whether you can move past the textbook definition and discuss real-world constraints, performance trade-offs, and how you would actually run Paxos in production.

Why Paxos Gets Follow-Up Questions

Paxos is conceptually simple but implementation-heavy. A candidate who can name the roles—proposer, acceptor, learner—has shown basic awareness. The next step is to verify that they can reason about quorum sizing, network partitions, and latency under load. Interviewers also check whether you can relate Paxos to other consistency models and to the services that use it, such as a distributed lock manager or a replicated state machine.

Core Follow-Up Questions

1. How do you choose the size of the quorum, and why does it matter?

I choose a majority quorum, so with N acceptors I need ⌊N/2⌋+1 votes to commit. For example, with five acceptors I need three. This ensures that any two quorums intersect, guaranteeing that at most one value can be chosen. If I used a smaller quorum, two disjoint groups could each decide a different value, breaking safety.

2. What happens if the leader (proposer) crashes mid-round?

If the leader crashes after sending prepare messages but before receiving a majority of promises, the round aborts. Other proposers can start a new round with a higher proposal number. The lost work is harmless because no value is chosen until a majority of acceptors have promised not to accept lower numbers. In practice, we detect the crash via heartbeat timeouts and trigger a leader election.

3. How does Paxos handle network partitions?

Paxos guarantees safety but not liveness during a partition. If a majority partition can still form, it can continue to make progress; the minority partition cannot commit any new values. Once the partition heals, the minority learns the committed value through the learner role. This is why we often pair Paxos with a timeout-based retry strategy to avoid indefinite stalls.

4. What is the latency impact of a single Paxos round-trip?

A single round-trip involves a prepare phase and an accept phase, each requiring a network round-trip to a majority of acceptors. Assuming a 30 ms round-trip latency between datacenters, a commit takes roughly 60 ms plus processing overhead. In a tightly coupled cluster with 5 ms latency, the commit time drops to about 10 ms. This latency scales with the number of hops and the size of the quorum.

5. How do you persist the Paxos log, and what durability guarantees do you get?

Each acceptor writes the promise and any accepted value to stable storage before responding. I typically use an append-only log on SSDs with fsync on each write. This gives durable safety: once a value is committed, a power loss cannot cause loss of the chosen value. To improve throughput, I batch multiple log entries and use group-commit, but I still ensure the commit point is flushed before acknowledging the client.

6. Can you explain the difference between Basic Paxos and Multi-Paxos?

Basic Paxos decides a single value per instance. Multi-Paxos optimizes for a sequence of decisions by electing a stable leader that skips the prepare phase for subsequent values, reducing each commit to a single accept round-trip. The leader still needs to re-establish its authority after a failure, but under normal operation the latency drops from two round-trips to one.

7. How would you scale Paxos to handle thousands of requests per second?

I would shard the state machine, running independent Paxos groups for each shard. Each group would have its own acceptor set, typically five nodes, to keep quorum size modest. Load balancers route client requests to the appropriate shard based on a hash of the key. This parallelism lets the system linearly scale with the number of shards while preserving the safety guarantees per shard.

8. What are the trade-offs of using Paxos versus Raft in a modern service?

Both provide consensus, but Raft adds a more explicit leader election and log replication model, which many find easier to reason about. Paxos is more flexible; you can implement leaderless variants like EPaxos for lower latency in geographically distributed settings. However, Raft’s stronger emphasis on understandability often reduces operational bugs. Choosing between them depends on team expertise and latency requirements.

9. How do you monitor and debug a live Paxos deployment?

I instrument each acceptor with metrics: number of promises, number of accepted values, and latency of each phase. I also track leader election frequency and the size of the uncommitted log tail. Alerts fire on sudden spikes in failed prepares or prolonged leader absence. For debugging, I capture the full sequence of messages for a given instance and replay them offline to verify quorum intersections.

Senior vs. Staff Answers

A senior-level answer covers the algorithmic basics, correctness guarantees, and common operational concerns. It demonstrates that the candidate can implement Paxos safely and reason about its performance in a single cluster.

A staff-level answer goes further. It ties Paxos to system-wide architecture, discusses sharding strategies, cross-region latency mitigation, and alternative consensus protocols. It also shows a proactive mindset: monitoring, automated recovery, and cost-benefit analysis of different designs. The staff response reflects experience in scaling Paxos from a prototype to a production service that handles millions of requests daily.

How to practice this

  1. Review the worked consensus design in the System Design AI library; it is built on Raft rather than Paxos, but the quorum, leader and log ideas carry over. Study the diagram, notes, and the practice brief.
  2. On the canvas, sketch your own Paxos-based service, labeling each component and noting the quorum size you would pick.
  3. Use the AI coach to get feedback on your diagram and iterate until you can explain each follow-up question confidently.

Questions people ask

What is the minimum number of nodes needed for Paxos?

Paxos needs at least three nodes to tolerate the failure of one. With three nodes, two must agree, ensuring any two quorums intersect.

Why does Paxos need a majority quorum?

A majority quorum guarantees that any two decision rounds share at least one common node, preventing contradictory values from being chosen.

Can Paxos be used across multiple data centers?

Yes, but network latency will dominate commit time. You must tolerate partitions and may need to combine Paxos with a higher-level retry strategy.

How does Multi-Paxos improve performance?

Multi-Paxos elects a stable leader, allowing subsequent proposals to skip the prepare phase, reducing each commit to one round-trip instead of two.