Paxos has a strange reputation for a foundational algorithm: it is correct, it is not even that long, and it is still one of the most notoriously difficult papers in distributed systems to read. Leslie Lamport wrote the original version, "The Part-Time Parliament," as an allegory about a fictional Greek legislature, partly as a joke. Almost nobody understood it. Years later, after watching people struggle, Lamport wrote "Paxos Made Simple," a much more direct explanation, opening with the memorable line that the algorithm "is trivially simple once explanations are stripped of unnecessary formalism."
What Paxos solves is consensus: getting a collection of machines, some of which may crash or have messages to them lost or delayed, to agree on a single value, safely, even though multiple machines might be proposing different values at the same time. It is the algorithm underneath Google's Chubby lock service, Spanner, and for years, most production consensus systems before Raft made the same guarantees easier to implement.
Paxos guarantees that once a value is chosen, it can never be un-chosen or replaced by a different value, no matter how many proposers, acceptors, or message losses show up afterward. It does this with two phases: proposers first ask a majority of acceptors for a promise not to accept anything older, then, if enough promise, propose an actual value for that majority to accept.
Three roles, one job each
Classic Paxos names three roles, though a single machine in a real system often plays more than one:
- Proposers suggest values that the group might agree on. Any proposer can propose at any time, including multiple proposers at once, which is exactly what makes the safety argument interesting.
- Acceptors are the ones who actually decide, collectively, by majority vote, which value is chosen. Each acceptor remembers what it has promised and accepted, and that memory is the entire mechanism that keeps the protocol safe.
- Learners find out what value was chosen, once a majority of acceptors has accepted it. In practice this is usually just a broadcast from an acceptor or the winning proposer.
Every proposal carries a proposal number, a value that is unique per proposer and strictly increasing, used purely to break ties and detect staleness. It says nothing about which value is better, only about which attempt is more recent.
Phase 1: ask before you propose
A proposer that wants a value chosen does not just broadcast it. It first picks a proposal number , higher than any it has used before, and sends a prepare(n) request to a majority of acceptors. This is a question, not a value yet: "will you promise to ignore any proposal older than from now on?"
An acceptor receiving prepare(n) checks it against the highest numbered prepare it has already responded to. If is higher, the acceptor promises, and replies with a promise(n), which includes the highest-numbered value it has already accepted, if any. If is not higher, the acceptor simply ignores the request; nothing unsafe happens by staying quiet.
Phase 2: propose, once a majority has promised
If the proposer hears back promise from a majority, it moves to Phase 2 and sends accept(n, v) to that same majority. The value is not free to pick arbitrarily: if any of the promises included a previously accepted value, the proposer must re-propose the value from the highest-numbered one it saw. Only if every promise came back empty is the proposer free to propose its own value.
An acceptor receiving accept(n, v) accepts it, unless it has since promised a higher numbered prepare in the meantime, in which case it refuses. Once a majority of acceptors has accepted the same pair, that value is chosen, and this cannot be undone.
Why re-proposing the highest value is the whole safety argument
The single rule that makes Paxos safe is the "must re-propose" constraint in Phase 2. Here is why it matters: suppose a value is chosen because a majority accepted (n, v). A later proposer, unaware this happened, runs Phase 1 with a higher number and gets promises from some majority .
Because and are both majorities of the same set of acceptors, they must overlap in at least one acceptor. That overlapping acceptor already accepted (n, v), so its promise back to the new proposer will report that fact. The rule forces the new proposer to re-propose rather than something else, so even a proposer that has no idea a value was already chosen ends up proposing the same one anyway.
This is the same overlapping-majority argument that makes Raft's election restriction safe, and it is not a coincidence, Raft is provably a specialization of the same underlying idea, with a stable leader added specifically to avoid running Phase 1 over and over. Once you see the majority-overlap trick here, Raft's safety proof reads as a special case of it.
The gap the paper is honest about: liveness is not guaranteed
Paxos guarantees safety unconditionally: a chosen value is never unchosen, no matter what. It does not guarantee liveness, that some value eventually gets chosen at all. If two proposers keep dueling, each running Phase 1 with a higher number just as the other reaches Phase 2, every accept can be pre-empted by a fresher prepare, and the algorithm can churn forever without ever choosing anything.
The practical fix, which the paper describes and every real implementation uses, is to elect a distinguished proposer, effectively a leader, so that under normal conditions only one proposer is active and there is no dueling to begin with. This is precisely the leader Raft makes a first-class, explicit part of the protocol instead of an optional optimization.
Why it still matters, even with Raft available
Paxos predates Raft by over a decade and remains in production in systems that were built before Raft existed or that need Paxos's exact guarantees, Google's Chubby and Spanner among them. More importantly, it is the reference point every later consensus algorithm gets compared against: when a paper claims a new protocol is correct, "equivalent to Paxos" is often the actual argument being made.
Reading it after Raft, rather than before, is a reasonable order for most engineers. Raft's explicit leader and log make the majority-overlap safety argument concrete and easy to visualize first; coming back to Paxos afterward, the same argument in its more abstract, leaderless form is much easier to follow.
Key takeaways: a proposer collects promises from a majority before proposing (Phase 1), then gets that majority to accept a value (Phase 2), and must re-propose the highest-numbered previously accepted value if one exists. Two overlapping majorities can never disagree, which is what makes a chosen value permanent. Safety is unconditional; liveness needs a single active proposer in practice, which is exactly the leader Raft makes explicit.