DROPS

Document

Brief Announcement

DOI: 10.4230/LIPIcs.DISC.2022.39

Brief Announcement: It’s not easy to relax: liveness in chained BFT protocols

Authors: Ittai Abraham, Natacha Crooks, Neil Giridharan, Heidi Howard, and Florian Suri-Payer

Published in: LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022)

Abstract

Modern chained BFT SMR protocols have poor liveness under failures as they require multiple consecutive honest leaders to commit a single block. Siesta, our proposed new BFT SMR protocol, is instead able to commit a block that spans multiple non-consecutive honest leaders. Siesta reduces the expected commit latency of HotStuff by a factor of three under failures, and the worst-case latency by a factor of eight.

Cite as

Ittai Abraham, Natacha Crooks, Neil Giridharan, Heidi Howard, and Florian Suri-Payer. Brief Announcement: It’s not easy to relax: liveness in chained BFT protocols. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 39:1-39:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{abraham_et_al:LIPIcs.DISC.2022.39,
  author =	{Abraham, Ittai and Crooks, Natacha and Giridharan, Neil and Howard, Heidi and Suri-Payer, Florian},
  title =	{{Brief Announcement: It’s not easy to relax: liveness in chained BFT protocols}},
  booktitle =	{36th International Symposium on Distributed Computing (DISC 2022)},
  pages =	{39:1--39:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-255-6},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{246},
  editor =	{Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2022.39},
  URN =		{urn:nbn:de:0030-drops-172305},
  doi =		{10.4230/LIPIcs.DISC.2022.39},
  annote =	{Keywords: Consensus, blockchain, BFT}
}

Document

DOI: 10.4230/LIPIcs.OPODIS.2016.25

Flexible Paxos: Quorum Intersection Revisited

Authors: Heidi Howard, Dahlia Malkhi, and Alexander Spiegelman

Published in: LIPIcs, Volume 70, 20th International Conference on Principles of Distributed Systems (OPODIS 2016)

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.

Cite as

Heidi Howard, Dahlia Malkhi, and Alexander Spiegelman. Flexible Paxos: Quorum Intersection Revisited. In 20th International Conference on Principles of Distributed Systems (OPODIS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 70, pp. 25:1-25:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{howard_et_al:LIPIcs.OPODIS.2016.25,
  author =	{Howard, Heidi and Malkhi, Dahlia and Spiegelman, Alexander},
  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 =	{Fatourou, Panagiota and Jim\'{e}nez, Ernesto and Pedone, Fernando},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2016.25},
  URN =		{urn:nbn:de:0030-drops-70947},
  doi =		{10.4230/LIPIcs.OPODIS.2016.25},
  annote =	{Keywords: Paxos, Distributed Consensus, Quorums}
}

Search Results

Documents authored by Howard, Heidi

Brief Announcement: It’s not easy to relax: liveness in chained BFT protocols

Abstract

Cite as

Flexible Paxos: Quorum Intersection Revisited

Abstract

Cite as

Thanks for your feedback!

Could not send message