@inproceedings{e6d7f18c170f4ea2ab34e16925da9df5,
title = "Good-Case and Bad-Case Latency of Unauthenticated Byzantine Broadcast: A Complete Categorization",
abstract = "This paper studies the good-case latency of unauthenticated Byzantine fault-tolerant broadcast, which measures the time it takes for all non-faulty parties to commit given a non-faulty broadcaster. For both asynchrony and synchrony, we show that n ≥ 4f is the tight resilience threshold that separates good-case 2 rounds and 3 rounds. For asynchronous Byzantine reliable broadcast (BRB), we also investigate the bad-case latency for all non-faulty parties to commit when the broadcaster is faulty but some non-faulty party commits. We provide matching upper and lower bounds on the resilience threshold of bad-case latency for BRB protocols with optimal good-case latency of 2 rounds. In particular, we show 2 impossibility results and propose 4 asynchronous BRB protocols.",
keywords = "Asynchrony, Byzantine broadcast, Good-case, Latency, Optimal, Synchrony",
author = "Ittai Abraham and Ling Ren and Zhuolun Xiang",
note = "Publisher Copyright: {\textcopyright} Ittai Abraham, Ling Ren, and Zhuolun Xiang.; 25th International Conference on Principles of Distributed Systems, OPODIS 2021 ; Conference date: 13-12-2021 Through 15-12-2021",
year = "2022",
month = feb,
day = "1",
doi = "10.4230/LIPIcs.OPODIS.2021.5",
language = "English (US)",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
editor = "Quentin Bramas and Vincent Gramoli and Vincent Gramoli and Alessia Milani",
booktitle = "25th International Conference on Principles of Distributed Systems, OPODIS 2021",
}