Skip to content

Paxos-Style Quorum Protocol

Single-decree quorum protocol — instantiates Assumption-Bounded Distributed Agreement

Guarantees that competing proposers choose exactly one value and never un-choose it — by ordering proposals with monotonic ballot numbers and forcing each new ballot to re-adopt any value that might already have been chosen.

Paxos-Style Quorum Protocol is the classic two-phase, single-decree engine for choosing one value safely when several proposers compete and the network is asynchronous. Its defining idea is a pair of moves that together make the choice permanent. First, every proposal carries a monotonically increasing ballot number, and a majority of acceptors promise not to accept anything older — this totally orders competing attempts in logical time. Second, before proposing its own value in a new ballot, a proposer must adopt the highest-numbered value any acceptor in its majority has already accepted. Together these guarantee that once a value might have been chosen, every later ballot proposes that same value — so the choice, once possible, is stable forever. Safety holds unconditionally; liveness — that some ballot eventually succeeds — needs a period of synchrony with a single distinguished proposer, which is precisely how Paxos coexists with the impossibility of guaranteed asynchronous consensus.

Example

A coordination service must choose a single authoritative value — which replica holds the write lease for a shard — among five acceptors, at a moment when two candidate replicas nominate themselves almost simultaneously. Candidate A runs phase one with ballot 11 and collects promises from three acceptors. Candidate B runs phase one with ballot 12 and also collects three promises, overlapping A's majority in at least one acceptor. Because B's ballot is higher, any acceptor in B's quorum that had already accepted A's value under ballot 11 reports it back — and the rule forces B to drop its own nomination and propose A's value instead. Only one lease-holder is ever chosen; a late, stale retry from A under ballot 11 is simply rejected by acceptors that have since promised ballot 12. The dueling proposers race, but the shard never ends up with two lease-holders.[1]

How it works

  • Two phases. Prepare/promise claims a ballot number and learns what may already have been chosen; accept/accepted proposes a value and gathers a majority to choose it.
  • Ballot numbers as the order. Monotonic, per-proposer-unique ballots impose a total order on attempts, so a stale proposer can never overwrite a fresher decision.
  • Adopt before you propose. The safety invariant: a proposer must carry forward the highest already-accepted value in its quorum, which is what makes a possibly-chosen value un-losable.
  • Majority quorums. Any two ballots' quorums intersect, so the acceptor in the overlap enforces the adopt rule across competing ballots.

It deliberately keeps to a single decree; building an ordered log of many decisions on top is a different mechanism's job.

Tuning parameters

  • Single-decree vs. Multi-Paxos — run the full two phases per value, or elect a stable leader once and amortize phase one across many decisions. Multi-Paxos is far faster in steady state but reintroduces a leader to keep healthy.
  • Leader stability — how aggressively a single distinguished proposer is maintained. A stable leader avoids dueling-proposer livelock; frequent leader churn courts it.
  • Ballot-number scheme — how ballots are made unique-per-proposer and monotone (e.g. round number paired with a proposer id). Getting this subtly wrong silently breaks the single-value guarantee.
  • Quorum shape — simple majorities, or flexible/weighted quorums where the phase-one and phase-two quorums need only intersect each other rather than both be majorities — trading write-quorum size against read-quorum size.

When it helps, and when it misleads

Its strength is that it is the canonical, rigorously-proven-safe core for crash-fault agreement: it never chooses two values, under any pattern of message loss, reordering, duplication, or delay, and no matter how many proposers compete. Decades of systems have been built on that guarantee.

Its dangers are real but specific. Bare single-decree Paxos is subtle and slow — two round-trips per value — and famously easy to implement incorrectly from the paper. Dueling proposers can livelock, making no progress until a leader stabilizes — but note this is a liveness failure, never a safety one; the protocol simply chooses nothing for a while, not two things. And it assumes crash faults only: a single lying acceptor breaks it, which is the boundary where a Byzantine-tolerant protocol takes over. The classic misuse is hand-rolling it from the paper and getting the ballot ordering or the adopt rule slightly wrong, quietly forfeiting the single-value guarantee. The discipline is to elect a stable distinguished proposer for liveness, keep ballot numbers unique and monotone, and lean on a verified implementation rather than a fresh one.

How it implements the components

  • round_epoch_and_leadership_state — the monotonic ballot/round numbers and the acceptor promises that order competing proposals in logical time.
  • state_consistency_guard — the "adopt the highest already-accepted value" rule that preserves the monotone safety invariant: a possibly-chosen value is never contradicted by a later round.
  • safety_liveness_contract — the explicit deal it lives by: safety unconditionally, liveness only during synchrony with a stable proposer — its principled answer to the asynchronous impossibility.

It does not perform the base quorum commit or define durability (Quorum or Consensus Commit), maintain the multi-entry replicated log (Raft-Style Replicated-Log Protocol), tolerate lying acceptors (Byzantine Fault-Tolerant Quorum Protocol), or change the participant set (Joint-Consensus Membership Change).

Notes

The placement of dueling proposers on the liveness side, never the safety side, is the single most important thing to internalize: Paxos under contention chooses nothing until a leader stabilizes — it never chooses two things. Teams that misread livelock as a safety bug add "just commit anyway" shortcuts that forfeit the one guarantee the protocol exists to provide.

References

[1] Lamport's single-decree Synod (the heart of Paxos) rests on the invariant that if a value may have been chosen by a majority, every higher-numbered proposal must also propose that value — which is what makes the chosen value permanent. Safety is unconditional; the FLP impossibility means liveness cannot be, hence the reliance on an eventual stable leader. ↩