2016/08/24 by Heidi Howard, Dahlia Malkhi, Howard, Heidi +3 · 2 voices · 47 citations
Computer Science · Engineering · Mathematics · #Algorithm #Computer science #Consensus #Consensus algorithm #Discrete mathematics #Disjoint sets #Distributed algorithm #Distributed computing #Distributed systems and fault tolerance #Engineering #Intersection (aeronautics) #Mathematics #Multi-agent system #Optimization and Search Problems #Petri Nets in System Modeling #Theoretical computer science #cs.DC
paper · pdf · doi:10.48550/arxiv.1608.06696
published in arXiv (Cornell University) (Cornell University)
arxiv created 2016/08/24 · openalex publication_date 2016/08/24 · arxiv updated 2016/08/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.