hesela.devFlexible Paxos
Flexible Paxos generalizes Paxos by requiring intersection between phase-1 and phase-2 quorum families without requiring intersection within each phase.
For arbitrary q1- and q2-member subsets of N acceptors, q1 + q2 > N ensures cross-phase intersection. These are proposal phases, not application read/write quorums. [1]
At N=5, q1=4, q2=2, two reachable acceptors can meet a prepared, unpreempted leader's phase-2 count; replacing it needs four for phase 1. [1]
Restricted families differ: in a 2-by-3 grid, full rows for phase 1 intersect full columns for phase 2. Losing a row preserves phase 1 but blocks phase 2. Identities matter, not just counts. [1]
Ordered proposals, promises, accepted-value selection and retained state remain necessary. Changing membership or families requires a protocol. Six size-based and four grid examples check sets, not messages, crash persistence or probabilities. [2] [3]
Across three two-acceptor domains, none of the 15 placements preserves both families after every domain loss: nine do for two losses, six for none. All retain phase 2, usable with a surviving prepared, unpreempted leader. These are not outage probabilities. [4]
A failed set blocks a family by hitting every quorum. The grid has nine minimal phase-1 cuts and eight phase-2 cuts. A fresh round needs both families: their blocking union has eleven inclusion-minimal cuts, nine cross-row pairs and two whole-row triples. Minimal is not minimum-size; keeping only pairs misses the triples. These are not data-loss or outage probabilities. Naor/Wool supplies the event definition, not these counts or its independent-failure assumption for this grid. [5] [6]
Relations
Citations
- Howard, Malkhi and Spiegelman. Flexible Paxos: Quorum Intersection Revisited. OPODIS 2016, LIPIcs 70 (2017), sections 3-7.
- Leslie Lamport. Paxos Made Simple (2001), sections 2-3.
- Hesela: Flexible Paxos phase availability, exact set examples and limits
- Hesela: all 15 grid placements and 45 single-domain-loss cases, exact constructed enumeration
- Naor and Wool. The Load, Capacity, and Availability of Quorum Systems. SIAM J. Comput. 27(2), 1998, section 2.2.
- Hesela: minimal-cut certificates and all 64 failure subsets for the fixed six-acceptor grid
Sources & caveats
- The OPODIS 2016 paper was published in LIPIcs on 6 April 2017; its prototype, safety proof and scope were reviewed separately. [1]
- The worked calculation does not rerun the authors' Mininet benchmark or TLA+ verification. No deployment speedup or availability percentage is claimed.
- Protocol classification, not a hardware lifecycle; status is unknown and firstSeen remains unset.