HackerPapers

arXiv:1608.06696cs.DC

Flexible Paxos: Quorum intersection revisited

Heidi Howard, Dahlia Malkhi, Alexander Spiegelman

Abstract

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.

arXiv comments
Journal reference
DOI
Subjects
cs.DCDistributed, Parallel, and Cluster Computing

On Hacker News

Linked by 5 identifiable commenters in 5 comments across 5 threads, from Mar 2017 to Aug 2026. Found in 2 HN submissions from Aug 2016 to Aug 2016. Open submission discussions.

Comments linking this paper, per year.

Discussed in comments5 threads

  1. TigerBeetle Core System Architecture: Deconstructing Performance Engineering 1 comment

    • It's an insight from Heidi Howard et al. that came out after VSR: https://arxiv.org/abs/1608.06696 and can be applied to VSR (and others). The basic idea is pretty simple. In VSR, there are two main phases: 1. Leader election 2. Normal replication / request processing Before…

      to_zieglerView on HNParent context

  2. Did we miss P In CAP? Partial Progress Conjecture under Asynchrony 1 comment

    • I think that's a different thing... I believe you're talking about flexible paxos (https://arxiv.org/abs/1608.06696). Flexible paxos doesn't change the underlying guarantees at all, whereas this does.

      footaView on HNParent context

  3. Raft: Understandable Distributed Consensus (2014) 1 comment

    • The papers and talks[1] by Heidi Howard and Richard Mortier, in particular “Paxos vs Raft: Have we reached consensus on distributed consensus?”[2,3] and “Flexible Paxos”[4,5], are what finally made things click for me. A real implementation also needs other stuff[6], though…

      mananaysiempreView on HNParent context

  4. Paxos in 25 Lines 1 comment
  5. In search of a simple consensus algorithm 1 comment

    • Funnily enough, there is a paper on exactly what you're referring to from Microsoft Research called "Flexible Paxos": https://arxiv.org/pdf/1608.06696.pdf The gist of it is that there are realistically 2 quorums to be had: One for read/write to a cluster, and one for leader…

      SEJeffView on HNParent context

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.