  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.
