# Paxos algorithm Paxos is a family of protocols, designed by [[Leslie Lamport]], that lets a group of unreliable processes agree on a single value. It assumes an asynchronous network (messages can be delayed, lost or reordered) and crash faults: processes may stop and restart, but they don't lie. Byzantine faults, where a process sends wrong or conflicting messages, need other protocols (see [[Fault Tolerance]]). Applied to every entry of a log, single-value agreement gives *state machine replication*: several servers apply the same commands in the same order, so they hold the same state and the group survives the loss of any minority. Replicated databases, lock services and configuration stores rely on this. ## How it works There are three roles; one process often plays all three: - **Proposers** suggest a value - **Acceptors** vote on proposals; any majority of them forms a quorum - **Learners** find out which value was chosen A round has two phases: 1. **Prepare / Promise.** A proposer picks a proposal number *n* higher than any it has used and sends *prepare(n)* to the acceptors. Each acceptor that hasn't promised a higher number promises to ignore anything below *n*, and reports the highest-numbered proposal it has already accepted, if any 2. **Accept / Accepted.** Once a majority has promised, the proposer sends *accept(n, v)*. The value *v* must be the one from the highest-numbered proposal the acceptors reported; only if none was reported can the proposer use its own value. Acceptors accept unless they have promised a higher number since, and a value is chosen once a majority accepts the same proposal Any two majorities share at least one acceptor. That overlap is what carries an already chosen value into every later round, so two different values can never both be chosen. ## Safety always, progress not guaranteed Paxos never lets the group decide two different values, whatever the delays or crashes. It doesn't promise to decide at all. That limit isn't specific to Paxos: Fischer, Lynch and Paterson proved in 1985 (the "FLP impossibility" result) that no deterministic consensus protocol can guarantee progress in an asynchronous system where even one process may crash. In Paxos, two proposers can keep pre-empting each other with ever-higher proposal numbers. Implementations avoid that duel by electing a single leader to propose, with timeouts and randomized retries to replace it when it fails. ## Multi-Paxos Running both phases for every log entry is expensive. Multi-Paxos keeps a stable leader that runs phase 1 once, then only phase 2 for each new entry, so each command costs one round trip to a majority while the leader stays healthy. This is the form used to replicate logs in practice. ## History Lamport found the algorithm in the late 1980s, while trying to prove that a fault-tolerant file system being built at DEC's Systems Research Center (Echo) was impossible. He wrote it up as "The Part-Time Parliament", the story of a parliament on the fictional Greek island of Paxos whose legislators keep wandering in and out of the chamber. He submitted it to ACM Transactions on Computer Systems in 1990; the referees asked him to remove the Greek parable, and the paper only appeared in 1998. Readers found it hard to follow, so in 2001 he published "Paxos Made Simple", a 13-page explanation without the parable. A similar protocol, Viewstamped Replication, had been published by Brian Oki and [[Barbara Liskov]] in 1988. ## Paxos and Raft Paxos earned a reputation for being hard to understand and harder to implement correctly. Lamport himself notes that one sentence of "Paxos Made Simple" is ambiguous, and that several implementations on GitHub got it wrong. Diego Ongaro and John Ousterhout designed Raft (2014) explicitly for understandability: it is equivalent to Paxos in fault tolerance and performance, but split into leader election, log replication and safety. ## In production - Google's Chubby lock service, Spanner and Megastore use Paxos - ZooKeeper uses its own atomic broadcast protocol (Zab), not Paxos - etcd, the store behind [[Kubernetes]], uses Raft ## References - Leslie Lamport, "The Part-Time Parliament", ACM Transactions on Computer Systems 16(2), May 1998, 133-169 - Leslie Lamport, "Paxos Made Simple", ACM SIGACT News 32(4), December 2001, 51-58 - Lamport's own notes on both papers: https://lamport.azurewebsites.net/pubs/pubs.html - Michael J. Fischer, Nancy Lynch and Michael Paterson, "Impossibility of Distributed Consensus with One Faulty Process", Journal of the ACM 32(2), 1985 - Brian Oki and Barbara Liskov, "Viewstamped Replication", PODC 1988 - Diego Ongaro and John Ousterhout, "In Search of an Understandable Consensus Algorithm", USENIX ATC 2014: https://raft.github.io/ - Mike Burrows, "The Chubby lock service for loosely-coupled distributed systems", OSDI 2006: https://research.google/pubs/the-chubby-lock-service-for-loosely-coupled-distributed-systems/ - Apache ZooKeeper internals (atomic broadcast): https://zookeeper.apache.org/doc/current/zookeeperInternals.html - etcd FAQ: https://etcd.io/docs/v3.5/faq/ - Wikipedia, Paxos (computer science): https://en.wikipedia.org/wiki/Paxos_(computer_science) ## Related - [[Leslie Lamport]] - [[Barbara Liskov]] - [[Fault Tolerance]] - [[Timeouts (software)]] - [[Kubernetes]] - [[Database]]