License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.DISC.2023.41
URN: urn:nbn:de:0030-drops-191675
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/19167/
Go to the corresponding LIPIcs Volume Portal

Gafni, Eli ; Losa, Giuliano

Brief Announcement: Byzantine Consensus Under Dynamic Participation with a Well-Behaved Majority

pdf-format:
LIPIcs-DISC-2023-41.pdf (0.5 MB)

Abstract

In a permissionless system like Ethereum, participation may fluctuate dynamically as some participants unpredictably go offline and some others come back online. In such an environment, traditional Byzantine fault-tolerant consensus algorithms may stall - even in the absence of failures - because they rely on the availability of fixed-sized quorums.
The sleepy model formally captures the main requirements for solving consensus under dynamic participation, and several algorithms solve consensus with probabilistic safety in this model assuming that, at any time, more than half of the online participants are well behaved. However, whether safety can be ensured deterministically under these assumptions, especially with constant latency, remained an open question.
Assuming a constant adversary, we answer in the positive by presenting a consensus algorithm that achieves deterministic safety and constant latency in expectation. In the full version of this paper, we also present a second algorithm which obtains both deterministic safety and liveness, but is likely only of theoretical interest because of its high round and message complexity. Both algorithms are striking in their simplicity.

BibTeX - Entry

@InProceedings{gafni_et_al:LIPIcs.DISC.2023.41,
  author =	{Gafni, Eli and Losa, Giuliano},
  title =	{{Brief Announcement: Byzantine Consensus Under Dynamic Participation with a Well-Behaved Majority}},
  booktitle =	{37th International Symposium on Distributed Computing (DISC 2023)},
  pages =	{41:1--41:7},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-301-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{281},
  editor =	{Oshman, Rotem},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/19167},
  URN =		{urn:nbn:de:0030-drops-191675},
  doi =		{10.4230/LIPIcs.DISC.2023.41},
  annote =	{Keywords: Consensus, Sleepy Model, Dynamic Participation, Byzantine Failures}
}

Keywords: Consensus, Sleepy Model, Dynamic Participation, Byzantine Failures
Collection: 37th International Symposium on Distributed Computing (DISC 2023)
Issue Date: 2023
Date of publication: 05.10.2023
Supplementary Material: Model: https://doi.org/10.5281/zenodo.8226236

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