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.2021.38
URN: urn:nbn:de:0030-drops-148401
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14840/
Go to the corresponding LIPIcs Volume Portal

Spiegelman, Alexander

In Search for an Optimal Authenticated Byzantine Agreement

pdf-format:
LIPIcs-DISC-2021-38.pdf (1 MB)

Abstract

In this paper, we challenge the conventional approach of state machine replication systems to design deterministic agreement protocols in the eventually synchronous communication model. We first prove that no such protocol can guarantee bounded communication cost before the global stabilization time and propose a different approach that hopes for the best (synchrony) but prepares for the worst (asynchrony). Accordingly, we design an optimistic byzantine agreement protocol that first tries an efficient deterministic algorithm that relies on synchrony for termination only, and then, only if an agreement was not reached due to asynchrony, the protocol uses a randomized asynchronous protocol for fallback that guarantees termination with probability 1.
We formally prove that our protocol achieves optimal communication complexity under all network conditions and failure scenarios. We first prove a lower bound of Ω(ft+ t) for synchronous deterministic byzantine agreement protocols, where t is the failure threshold, and f is the actual number of failures. Then, we present a tight upper bound and use it for the synchronous part of the optimistic protocol. Finally, for the asynchronous fallback, we use a variant of the (optimal) VABA protocol, which we reconstruct to safely combine it with the synchronous part.
We believe that our adaptive to failures synchronous byzantine agreement protocol has an independent interest since it is the first protocol we are aware of which communication complexity optimally depends on the actual number of failures.

BibTeX - Entry

@InProceedings{spiegelman:LIPIcs.DISC.2021.38,
  author =	{Spiegelman, Alexander},
  title =	{{In Search for an Optimal Authenticated Byzantine Agreement}},
  booktitle =	{35th International Symposium on Distributed Computing (DISC 2021)},
  pages =	{38:1--38:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-210-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{209},
  editor =	{Gilbert, Seth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/14840},
  URN =		{urn:nbn:de:0030-drops-148401},
  doi =		{10.4230/LIPIcs.DISC.2021.38},
  annote =	{Keywords: Byzantine agreement, Optimistic, Asynchronous fallback}
}

Keywords: Byzantine agreement, Optimistic, Asynchronous fallback
Collection: 35th International Symposium on Distributed Computing (DISC 2021)
Issue Date: 2021
Date of publication: 04.10.2021

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