2026-07-26T21:06:43Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14853 2024-03-06T10:55:01Z ddc:004 open_access

Brief Announcement: Revisiting Signature-Free Asynchronous Byzantine Consensus Cachin, Christian Zanolini, Luca Randomized consensus 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Christian Cachin and Luca Zanolini 2021 Is Part Of LIPIcs, Volume 209, 35th International Symposium on Distributed Computing (DISC 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.DISC.2021.51 urn:nbn:de:0030-drops-148535 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2021.51 eng https://creativecommons.org/licenses/by/4.0/legalcode