Source-linked AI summary
Flexible Paxos: Quorum intersection revisited
Heidi Howard, Dahlia Malkhi, Alexander Spiegelman
TL;DR
Intersecting Paxos quorums constrain the trade-off between resilience and throughput. Flexible Paxos requires intersection only across phases, allowing smaller replication quorums; in a 10-node example, 3 acceptors can replicate when 8 are required after leader failure.
Problem
With intersecting quorums, Paxos can increase throughput only by reducing resilience, or vice versa.
Source: §2 · p. 4Method
Flexible Paxos permits disjoint quorums within each phase, requiring only that quorums from different phases intersect.
Source: §1 · p. 2Results
In a 10-node system, 3 nodes can participate in replication if 8 participate when recovering from leader failure.
Source: §1 · p. 2Takeaways & Limitations
Smaller phase-2 quorums reduce common-case latency, tolerate slow acceptors, and allow disjoint acceptor sets for higher throughput, but progress can stop until acceptors recover if no phase-1 quorum forms.
Source: §3 · p. 5With simple quorums, reducing Q2 requires a corresponding increase in Q1 to preserve intersection.
Source: §4.3 · p. 8
Abstract
from arXiv · showhide
Distributed consensus is integral to modern distributed systems. The widely adopted Paxos algorithm uses two phases, each requiring majority agreement, to reliably reach consensus. In this paper, we demonstrate that Paxos, which lies at the foundation of many production systems, is conservative. Specifically, we observe that each of the phases of Paxos may use non-intersecting quorums. Majority quorums are not necessary as intersection is required only across phases. Using this weakening of the requirements made in the original formulation, we propose Flexible Paxos, which generalizes over the Paxos algorithm to provide flexible quorums. We show that Flexible Paxos is safe, efficient and easy to utilize in existing distributed systems. We conclude by discussing the wide reaching implications of this result. Examples include improved availability from reducing the size of second phase quorums by one when the number of acceptors is even and utilizing small disjoint phase-2 quorums to speed up the steady-state.
1 Introduction
Paxos is widely used for agreement across failures, but Flexible Paxos replaces the requirement that all quorums intersect with intersection only between phases. This permits flexible phase quorums, with practical trade-offs in replication performance and recovery availability.
1 Introduction
- In Multi-Paxos, phase 1 elects a leader while the more frequent phase 2 proposes successive values.This difference in phase frequency makes smaller replication quorums a practical target.Source: §1 · p. 2
- Flexible Paxos requires intersection only between phases, so quorums within one phase may be disjoint and majority quorums are unnecessary.It strictly generalizes Paxos, and when all quorums intersect, it is equivalent to Paxos.Source: §1 · p. 2
- With 10 nodes, simple quorums allow replication with 3 participants but require 8 for leader recovery, improving latency and steady-state throughput at the cost of recovery availability.The smaller phase-2 quorum also permits disjoint acceptor sets to accept proposals, improving participant utilization and reducing network load.Source: §1 · p. 2
- Reducing phase-2 quorum size by one can avoid an availability trade-off when the acceptor count is even; grid quorums can reduce both phase sizes.The paper also outlines the safety argument, evaluates an implementation, and discusses dynamically choosing quorums.Source: §1 · p. 2
2 Paxos
Paxos reaches agreement through two phases that conventionally require majorities, while Multi-Paxos reuses phase 1 to elect a leader for a sequence of values. The section also describes the quorum-intersection trade-off between participant load, throughput, and resilience.
2 Paxos
- In phase 1, a proposer sends a uniquely numbered prepare; acceptors persist promises and return their last accepted proposal, after which the proposer can proceed.The proposer may retry with a higher proposal number if it does not receive promises from a majority.Source: §2 · p. 3
- In phase 2, the proposer preserves the highest-numbered value returned in phase 1, or selects its own if none was returned, then seeks acceptor acceptance.Acceptors persist the accepted proposal when its number meets their promise, and a majority of acceptances decides the value.Source: §2 · p. 3
- Paxos preserves a decision once chosen and can make progress with a majority of acceptors up and communicating, but progress requires synchrony assumptions.The described system includes proposer, acceptor, and learner roles and allows process failures and lost messages.Source: §2 · p. 3
- Multi-Paxos agrees on a sequence of values by aggregating phase 1 across slots; a proposer that completes phase 1 becomes the leader.Phase 1 is independent of the proposed value, so it can run before that value is known.Source: §2 · p. 4
- As replica count rises, LibPaxos3 commit latency increases and average request throughput decreases (Figure 1).Figure 1 varies system size; the x-axis is replica count, with client commit latency and average request throughput shown separately.Source: §2 · p. 4, Figure 1 · p. 4
- With intersecting quorums, increasing throughput by reducing participant load trades off against resilience.The paper relates this constraint to the fundamental theorem of quorum intersection.Source: §2 · p. 4
3 FPaxos
Flexible Paxos (FPaxos) requires quorum intersection only across the two phases, allowing disjoint quorums within either phase. This flexibility can reduce the common phase-2 quorum, with phase-1 quorum availability remaining important for progress.
3 FPaxos
- FPaxos requires phase-1 and phase-2 quorums to intersect, but neither phase’s quorums need to intersect with one another.The paper names these quorums Q1 and Q2, respectively.Source: §3 · p. 5
- When Q1 and Q2 are restricted to quorums of at least ⌊n/2⌋+1 acceptors, FPaxos is equivalent to Paxos.Source: §3 · p. 5
- Reducing Q2 can lower common-case latency, tolerate slow acceptors, and allow disjoint acceptor sets for higher throughput, at the cost of requiring more participants for Q1.If failures prevent forming Q1, progress waits until acceptors recover.Source: §3 · p. 5
- With Q2 available, the system can continue safely after losing the ability to form Q1, until a new leader is needed; recovery beforehand avoids an availability loss.Source: §3 · p. 5
4 Implications
Flexible Paxos makes quorum intersection a cross-phase requirement, enabling practical quorum choices beyond majority quorums. The section illustrates majority, simple, and grid quorum trade-offs.
4.1 Majority quorums
- For even n, reducing Q2 from n/2 + 1 to n/2 lowers replication participation while preserving progress after exactly n/2 acceptor failures if the leader remains up.The paper says this change can reduce latency and improve throughput.Source: §4.1 · p. 6
- Flexible Paxos permits disjoint same-phase quorums, provided every phase-1 quorum intersects every phase-2 quorum.With four acceptors, the example uses three for Q1 and two for Q2; conflicting simultaneous proposals cannot both succeed.Source: §4.1 · p. 6
4.2 Simple quorums
- For simple quorums, safety requires |Q1| + |Q2| > N, so reducing Q2 requires increasing Q1; progress is guaranteed through |Q2| − 1 failures.With failures from |Q2| through N − |Q2|, replication can continue until a new leader is required.Source: §4.2 · p. 6, §4.3 · p. 8
- Sending prepare and propose messages only to quorum members reduces messages from 4 × N to (2 × |Q1|) + (2 × |Q2|), at the cost of possible retransmissions and latency.If an acceptor does not reply, the leader may contact more acceptors; it may also miss the fastest acceptors.Source: §4.2 · p. 8
4.3 Grid quorums
- Grid quorums arrange N acceptors in an N1-column by N2-row matrix; FPaxos can use one row for Q1 and one column for Q2, which may be disjoint within each phase.The construction restricts valid quorum combinations while maintaining cross-phase intersection; the paper describes quorum sizes N1 and N2.Source: §4.3 · p. 8
- With grid quorums, which acceptors fail matters: failures concentrated in one column can prevent Paxos progress while FPaxos continues until a new leader is needed.Distributing acceptors across machines, racks, or data centers can reduce the likelihood of simultaneous failures.Source: §4.3 · p. 9
- Setting N1 = 1 and N2 = N permits one-acceptor Q2 participation and one-hop learning, but leader recovery must wait for every acceptor to be up.The opposite setting, N1 = N and N2 = 1, uses a single-acceptor Q1 and tolerates f failures with f + 1 acceptors instead of 2f + 1.Source: §4.3 · p. 9
5 Safety
The safety argument weakens Paxos’s all-quorum intersection assumption to require intersection only between phases. It proves that a later proposal cannot choose a value different from one already decided.
5 Safety
- If value v is decided with proposal number p, every later propose(p’,v’) with p’ > p must have v’ = v, which implies that decisions remain final.The paper states this stronger condition as Theorem 2 and derives decision agreement as Theorem 1.Source: §5 · p. 9
- The proof by contradiction considers the smallest later proposal number that might carry a different value and shows the phase-1 proposer must retain the earlier value.The case analysis rules out conflicting accepted proposals between the earlier decision and the later prepare.Source: §5 · pp. 10–11
- Safety requires every phase-1 quorum to intersect every phase-2 quorum, while quorums within a phase need not intersect.The proof selects an acceptor shared by the earlier phase-2 quorum and the later phase-1 quorum, then reasons about the order of prepare and propose messages.Source: §5 · p. 10
- A TLA+ model of single-valued FPaxos with disjoint quorums preserved the safety requirement.The specification is described as a minor adaptation of the Paxos specification.Source: §5 · p. 11
6 Prototype
A LibPaxos3 prototype generalizes the sizes of the two quorums and sends messages only to quorum members. Its reported measurements show better latency and throughput in an eight-replica comparison, alongside implementation and quorum-selection caveats.
6 Prototype
- The prototype modifies LibPaxos3 by generalizing Q1 and Q2 sizes, randomly choosing simple quorums, and sending messages only to quorum nodes.The experiments used 64-byte requests, 10 in progress, and a simulated 10 Mbps network with 20 ms round-trip time.Source: §6 · p. 11
- Reducing Q2 sends fewer messages and increases throughput while decreasing latency, according to the reported steady-state results.The prototype’s gains also partly reflect sending only to quorum replicas, unlike LibPaxos3, which sends to all replicas.Source: §6 · pp. 11–12
- In an eight-replica system, FPaxos with Q2 size 4 lowers latency from 42ms to 37 ms and raises throughput from 198 to 264 reqs/sec versus Paxos.Figure 4 presents steady-state throughput and average latency for FPaxos quorum sizes and LibPaxos3.Source: §6 · p. 12
- A Q2 of size 2 cannot elect a new leader after two acceptor failures, and practical quorum selection must account for replica failures, speeds, and communication delays.The authors describe the prototype as trivial to implement and expect disjoint acceptors and smarter quorum construction to improve performance and failure tolerance.Source: §6 · p. 12
7 Enhancements
The paper proposes dynamically announcing a leader’s quorum choices so later proposers need only intersect phase-2 quorums already used. The mechanism’s safe integration with leader election is left outside the paper’s scope.
7 Enhancements
- A proposer’s phase-1 quorum need only intersect phase-2 quorums used with lower proposal numbers if it can learn which such quorums were used.This weakens the requirement to intersect all possible phase-2 quorums.Source: §7 · p. 12
- Leaders can announce selected quorum sets, but the announcement mechanism must be woven carefully into leader election for safety.The paper leaves implementation details out of scope and says the approach would resemble Paxos reconfiguration using principles of Vertical Paxos.Source: §7 · p. 12
- For N = 100f nodes, announcing a fixed Q2 of size f + 1 lets higher proposal numbers and readers intersect only that Q2, allowing tolerance of N − f failures.Announcing several Q2 choices increases phase-2 flexibility at the cost of phase-1 availability; leaders may also change quorum choices over time.Source: §7 · p. 12
8 Related Works
Prior work has simplified, optimized, and extended Paxos, while FPaxos revisits its foundations and can complement earlier approaches.
8 Related Works
- Earlier research simplified, optimized, and extended Paxos, with variants exploring different quorum, leadership, replication, and command-agreement designs.FPaxos is presented as orthogonal to these performance-focused approaches and integrable with them.Source: §8 · p. 13
- Reconfiguration frameworks that separate steady-state agreement from reconfiguration events can be adopted to make FPaxos reconfigurable and dynamic.Earlier approaches include agreeing on new configurations or using phase 1 to select a phase-2 quorum.Source: §8 · p. 13
- The authors state they were first to prove and implement the Paxos generalization, while Sougoumarane independently made the same observation and summarized it in a blog post.Source: §8 · p. 13
9 Conclusion
FPaxos generalizes Paxos by removing the requirement that quorums within the same phase intersect. The authors point to simpler deployment trade-offs and a reduced constraint on scalability.
9 Conclusion
- FPaxos no longer requires quorums from the same Paxos phase to intersect.Source: §9 · p. 14
- Exposing phase-2 quorum size to developers offers a choice between failure tolerance and steady-state latency, and the authors expect adoption in existing Multi-Paxos systems to be straightforward.Source: §9 · p. 14
- Removing the requirement for replication quorums to intersect removes an important limit on scalability, according to the authors.They suggest smart quorum construction and pragmatic system design could support scalable, resilient, and performant consensus algorithms.Source: §9 · p. 14