Brief Announcement: Revisiting Signature-Free Asynchronous Byzantine Consensus

Cachin, Christian; Zanolini, Luca (October 2021). Brief Announcement: Revisiting Signature-Free Asynchronous Byzantine Consensus. In: Gilbert, Seth (ed.) 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs): Vol. 209 (51:1-51:4). Dagstuhl, Germany: Schloss Dagstuhl, Leibniz-Zentrum für Informatik 10.4230/LIPIcs.DISC.2021.51

Preview

Text LIPIcs-DISC-2021-51.pdf - Published Version Available under License Creative Commons: Attribution (CC-BY). Download (549kB) | Preview

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.

Interest & Impact

Downloads

16 since deposited on 18 Feb 2022
12 in the past 12 months

Citations

5 Citations in Web of Science ®
6 Citations in Scopus

Search

in Google Scholar™

Services

Actions (login required)

Edit item

Actions (login required)

Edit item