Paxos is a family of protocols for reaching consensus in a network of unreliable processes, introduced by Leslie Lamport in “The Part-Time Parliament.” Lamport framed the algorithm through an allegory of legislators on the fictional island of Paxos who must agree on decrees even though they wander in and out of the parliament chamber and messengers can be lost or delayed.
In its single-decree form, the protocol assigns roles to processes acting as proposers, acceptors, and learners. A proposer asks a majority of acceptors to promise to consider its proposal, then asks that majority to accept a chosen value. Because any two majorities of acceptors overlap in at least one process, the protocol guarantees that once a value is chosen it cannot be contradicted, which is what keeps consensus safe despite failures.
The allegorical presentation was widely found difficult to follow, so Lamport wrote a second, plainer account titled “Paxos Made Simple.” It restates the same algorithm in direct language and then extends it to multi-Paxos, in which a sequence of consensus instances agrees on an ordered log of commands rather than a single value.
Paxos is both celebrated and notorious: correct and deeply influential, yet famously hard to understand and to implement faithfully. That difficulty was the explicit motivation behind Raft, which was designed to provide equivalent guarantees in a form that engineers could more easily reason about.