Did you know that quorums in Paxos do not need to intersect after a leader is elected?
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 Flex-
ible 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 discuss
far reaching implications of this result. For example, improved availability results from reducing
the size of second phase quorums by one when the system size is even, while keeping majority
quorums in the first phase. Another example is improved throughput of replication by using
much smaller phase 2 quorums, while increasing the leader election (phase 1) quorums. Finally,
non intersecting quorums in either first or second phases may enhance the efficiency of both.