License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.OPODIS.2016.25
URN: urn:nbn:de:0030-drops-70947
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7094/
Go to the corresponding LIPIcs Volume Portal

Howard, Heidi ; Malkhi, Dahlia ; Spiegelman, Alexander

Flexible Paxos: Quorum Intersection Revisited

pdf-format:
LIPIcs-OPODIS-2016-25.pdf (0.5 MB)

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, e cient 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.

BibTeX - Entry

@InProceedings{howard_et_al:LIPIcs:2017:7094,
  author =	{Heidi Howard and Dahlia Malkhi and Alexander Spiegelman},
  title =	{{Flexible Paxos: Quorum Intersection Revisited}},
  booktitle =	{20th International Conference on Principles of Distributed Systems (OPODIS 2016)},
  pages =	{25:1--25:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-031-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{70},
  editor =	{Panagiota Fatourou and Ernesto Jim{\'e}nez and Fernando Pedone},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7094},
  URN =		{urn:nbn:de:0030-drops-70947},
  doi =		{10.4230/LIPIcs.OPODIS.2016.25},
  annote =	{Keywords: Paxos, Distributed Consensus, Quorums}
}

Keywords: Paxos, Distributed Consensus, Quorums
Collection: 20th International Conference on Principles of Distributed Systems (OPODIS 2016)
Issue Date: 2017
Date of publication: 06.04.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI