Paxos (Computer Science)

Paxos (Computer Science) is a family of asynchronous fault-tolerant consensus protocols in distributed computing and computation and algorithms that enables a network of unreliable processors to agree deterministically on a single value or an ordered sequence of state-machine transitions despite arbitrary message delays, packet duplication, reordering, and crash-recovery node failures. Devised by American computer scientist Leslie Lamport in 1989 (initially circulated as a technical report framing the protocol as the parliamentary legislative system of the fictional ancient Greek island of Paxos, and formally published in ACM Transactions on Computer Systems in 1998), Paxos established the theoretical and practical foundation for replicated state machines across modern cloud infrastructure.

Because the Fischer–Lynch–Paterson (FLP) impossibility theorem (1985) proves that no deterministic consensus protocol can simultaneously ensure both safety (never returning conflicting values) and liveness (eventual termination) in a fully asynchronous network if even a single processor can crash, Paxos is engineered to be unconditionally safe under all asynchronous timing and crash-recovery schedules, while achieving liveness whenever a majority quorum of N = 2f + 1 acceptors can communicate with an uncontested leader for two message round-trips. Together with its understandable state-machine counterpart the Raft algorithm and causal ordering primitives such as the Lamport timestamp and vector clock, Paxos powers globally distributed coordination services and transactional databases including Google Chubby, Spanner, Apache Cassandra lightweight transactions, and Microsoft Azure storage.

Asynchronous Crash-Recovery Model and the Three Agent Roles

Basic Paxos (also called Single-Decree Paxos) solves consensus on a single immutable value v under the non-Byzantine crash-recovery failure model (as distinct from arbitrary Byzantine fault models): processors may stop executing at any instant, lose volatile memory, and later restart from persistent disk storage, while network links may delay, drop, duplicate, or reorder messages without corrupting message contents. Paxos partitions system participants into three logical roles (where a single physical server typically executes all three roles simultaneously in a symmetric configuration):

1. Proposers: Advocate client-submitted values v and coordinate consensus rounds using globally unique, totally ordered proposal ballot numbers n.
2. Acceptors: Act as the fault-tolerant replicated memory of the protocol, voting on proposals in majority quorums Q (any subset of at least ⌊N/2⌋ + 1 out of N = 2f + 1 acceptors).
3. Learners: Observe accepted quorum votes and execute or return the chosen consensus value once a majority of acceptors accept a common proposal (n, v).

Quorum Intersection Invariant (P2c)

Safety in Paxos rests on the pigeonhole quorum intersection property: any two majority quorums Q₁, Q₂ ⊆ {1, ..., N} with |Q₁| ≥ f + 1 and |Q₂| ≥ f + 1 share at least one common acceptor a ∈ Q₁ ∩ Q₂. To ensure that once a value v is chosen at ballot n₀, no later ballot n > n₀ can ever choose a different value v′ ≠ v, Lamport derived the central Paxos invariant P2c:

For any proposal (n, v) issued by a proposer, if any proposal with number less than n has been accepted by a majority quorum Q₁, then v must equal the value of the highest-numbered proposal among all proposals numbered less than n accepted by any member of the proposer's Prepare quorum Q₂.

Because Q₁ ∩ Q₂ ≠ ∅, querying Q₂ in Phase 1 reveals the latest value accepted by Q₁ and locks out any older ballots n′ < n.

Phase 1: Prepare and Promise (Reading and Locking Prior State)

Every ballot number n is made unique across proposers by pairing a local monotonic counter r with the proposer's unique node identifier i (ordered lexicographically as n = (r, i), analogous to a Lamport timestamp).

• Phase 1a (Prepare): A proposer selects a new ballot number n and broadcasts a Prepare(n) message to a majority quorum Q of acceptors.
• Phase 1b (Promise): Upon receiving Prepare(n), an acceptor compares n against the highest ballot number n_min it has ever promised:
  • If n > n_min, the acceptor persists n_min ← n to stable storage (promising never to accept any future proposal numbered less than n) and replies with Promise(n, n_a, v_a), where (n_a, v_a) is the highest-numbered proposal this acceptor has previously accepted (or (⊥, ⊥) if none).
  • If n ≤ n_min, the acceptor ignores the Prepare message or replies with a negative acknowledgment NACK(n_min).

Phase 2: Accept and Accepted (Voting and Choosing a Value)

• Phase 2a (Accept / Propose): Once the proposer receives Promise responses for ballot n from a majority quorum Q of acceptors, it selects value v according to invariant P2c:
  • If any acceptor in Q returned a non-null previously accepted proposal (n_a, v_a), the proposer must set v to the value v_a associated with the maximum ballot number max_a∈Q n_a among all responses in Q.
  • Only if every acceptor in Q reported no prior accepted proposal (n_a = ⊥ for all a ∈ Q) is the proposer free to choose its own client value v.

The proposer then sends Accept(n, v) to the acceptors.

• Phase 2b (Accepted): Upon receiving Accept(n, v), an acceptor accepts the proposal if and only if n ≥ n_min (it has not promised a higher ballot in the interim). It persists (n_a ← n, v_a ← v) to disk and broadcasts Accepted(n, v) to the proposer and all learners. Once a learner receives Accepted(n, v) from a majority of acceptors, value v is chosen and irrevocable.

In production replicated state machines, agreeing on a single value is insufficient; nodes must agree on an infinite sequence of log entries indexed by slot s = 1, 2, 3, .... Multi-Paxos elects a distinguished leader that executes Phase 1 (Prepare(n)) once across all uncommitted and future log slots s ≥ s₀ simultaneously. Once the leader holds a valid Phase 1 promise for ballot n, subsequent client commands bypass Phase 1 and execute only Phase 2 (Accept / Accepted) in a single network round-trip (2 message delays)—matching the normal-case latency of the Raft algorithm.

If two proposers simultaneously issue competing Prepare messages with interleaved ballot numbers (n₁ < n₂ < n₃ < n₄), each proposer can invalidate the other's Phase 1 promise before either completes Phase 2—a livelock scenario known as dueling proposers. Multi-Paxos eliminates dueling proposers by maintaining a single distinguished leader via periodic heartbeats, leases, or randomized binary backoff (with delay distribution scaling as 2^k) on rejected ballots.

How does Multi-Paxos differ from the Raft consensus algorithm?

Both Multi-Paxos and the Raft algorithm solve crash-fault-tolerant state-machine replication using N = 2f + 1 nodes and require 1 network round-trip per log entry under a stable leader. However, Multi-Paxos allows log entries to be committed out of order (creating temporary gaps in the log that must be filled by no-op entries during leader recovery) and permits any node to become leader by reading missing entries during Phase 1, whereas Raft enforces sequential log continuity and restricts leadership to candidates whose logs already contain all committed entries.

Why does Paxos require 2f + 1 acceptors instead of 2f to tolerate f crash failures?

To remain live when f acceptors have crashed, a quorum can require responses from at most N − f acceptors. Simultaneously, to prevent a split-brain partition where two disjoint quorums choose conflicting values, any two quorums of size N − f must overlap in at least one non-faulty acceptor: 2(N − f) − N ≥ 1, which simplifies to N ≥ 2f + 1.

What is Flexible Paxos (Howard et al., 2016)?

Heidi Howard, Dahlia Malkhi, and Alexander Spiegelman proved in Flexible Paxos that Paxos never actually requires Phase 1 quorums (Q₁) to intersect with other Phase 1 quorums, nor Phase 2 quorums (Q₂) to intersect with other Phase 2 quorums; safety requires only that every Phase 1 quorum intersects with every Phase 2 quorum (|Q₁| + |Q₂| > N). Because Phase 2 runs on every client write while Phase 1 runs only during rare leader elections, systems can shrink Phase 2 quorums (reducing write latency across wide-area data centers) at the cost of larger Phase 1 election quorums.

1. Lamport, L. (1998). "The part-time parliament." ACM Transactions on Computer Systems, 16(2), 133–169. https://doi.org/10.1145/279227.279229
2. Lamport, L. (2001). "Paxos made simple." ACM SIGACT News, 32(4), 51–58. https://lamport.azurewebsites.net/pubs/paxos-simple.pdf
3. Lamport, L. (2006). "Fast Paxos." Distributed Computing, 19(2), 79–103. https://doi.org/10.1007/s00446-006-0005-x
4. Chandra, T. D., Griesemer, R., & Redstone, J. (2007). "Paxos made live: An engineering perspective." Proceedings of the 26th Annual ACM Symposium on Principles of Distributed Computing (PODC), 398–407. https://doi.org/10.1145/1281100.1281103
5. Howard, H., Malkhi, D., & Spiegelman, A. (2016). "Flexible Paxos: Quorum intersection revisited." 20th International Conference on Principles of Distributed Systems (OPODIS 2016), LIPIcs Vol. 70, 25:1–25:14. https://doi.org/10.4230/LIPIcs.OPODIS.2016.25