A weaker requirement
Classic Paxos uses majority quorums in both the prepare and the accept phase. Flexible Paxos observes that safety does not actually need both to be majorities. It only requires that every prepare quorum intersects every accept quorum. The two phases can use different quorum sizes.
Trading the phases
Let the prepare quorum have size Q1 and the accept quorum size Q2. Safety holds as long as Q1 plus Q2 exceeds the number of nodes N. This frees designers to tune the system.
- A small accept quorum makes the common case, committing a value, cheaper and faster.
- That forces a larger prepare quorum, making leader changes more expensive.
- Since leader changes are rare and commits are frequent, this is often a great trade.
Why it stays safe
The intersection of a prepare quorum and an accept quorum still contains at least one acceptor. That acceptor reports any previously accepted value to a new leader during prepare, so the original safety argument of Paxos carries through unchanged.
Key idea
Flexible Paxos requires only that prepare and accept quorums overlap, letting designers shrink the accept quorum for fast commits while enlarging the rarer prepare quorum.