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

Cachin, Christian ; Zanolini, Luca

Brief Announcement: Revisiting Signature-Free Asynchronous Byzantine Consensus

pdf-format:
LIPIcs-DISC-2021-51.pdf (0.5 MB)

Abstract

Among asynchronous, randomized, and signature-free implementations of consensus, the protocols of Mostéfaoui et al. (PODC 2014 and JACM 2015) represent a landmark result, which has been extended later and taken up in practical systems. The protocols achieve optimal resilience and take, in expectation, only a constant expected number of rounds and have quadratic message complexity. Randomization is provided through a common-coin primitive. However, the first version of this simple and appealing protocol suffers from a little-known liveness issue due to asynchrony. The JACM 2015 version avoids the problem, but is considerably more complex.
This work revisits the original protocol of PODC 2014 and points out in detail why it may not progress. A fix for the protocol is presented, which does not affect any of its properties, but lets it regain the original simplicity in asynchronous networks enhanced with a common-coin protocol.

BibTeX - Entry

@InProceedings{cachin_et_al:LIPIcs.DISC.2021.51,
  author =	{Cachin, Christian and Zanolini, Luca},
  title =	{{Brief Announcement: Revisiting Signature-Free Asynchronous Byzantine Consensus}},
  booktitle =	{35th International Symposium on Distributed Computing (DISC 2021)},
  pages =	{51:1--51:4},
  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/14853},
  URN =		{urn:nbn:de:0030-drops-148535},
  doi =		{10.4230/LIPIcs.DISC.2021.51},
  annote =	{Keywords: Randomized consensus}
}

Keywords: Randomized consensus
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