LIPIcs.OPODIS.2021.5.pdf
- Filesize: 0.73 MB
- 20 pages
Document
Good-Case and Bad-Case Latency of Unauthenticated Byzantine Broadcast: A Complete Categorization
Authors
-
Part of:
Volume:
25th International Conference on Principles of Distributed Systems (OPODIS 2021)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Conference on Principles of Distributed Systems (OPODIS) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2022-02-28
File
Document Identifiers
Acknowledgements
The authors would like to thank Kartik Nayak for helpful discussions related to the paper.
Cite As Get BibTex
Ittai Abraham, Ling Ren, and Zhuolun Xiang. Good-Case and Bad-Case Latency of Unauthenticated Byzantine Broadcast: A Complete Categorization. In 25th International Conference on Principles of Distributed Systems (OPODIS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 217, pp. 5:1-5:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.OPODIS.2021.5
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.
Subject Classification
ACM Subject Classification
- Theory of computation → Distributed algorithms
- Security and privacy → Distributed systems security
Keywords
- Byzantine broadcast
- asynchrony
- synchrony
- latency
- good-case
- optimal
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
Ittai Abraham, Srinivas Devadas, Danny Dolev, Kartik Nayak, and Ling Ren. Synchronous byzantine agreement with expected O(1) rounds, expected O(n²) communication, and optimal resilience. In International Conference on Financial Cryptography and Data Security (FC), pages 320-334. Springer, 2019.
-
Ittai Abraham, Dahlia Malkhi, Kartik Nayak, Ling Ren, and Maofan Yin. Sync hotstuff: Simple and practical synchronous state machine replication. IEEE Symposium on Security and Privacy (SP), 2020.
-
Ittai Abraham, Kartik Nayak, Ling Ren, and Zhuolun Xiang. Brief announcement: Byzantine agreement, broadcast and state machine replication with optimal good-case latency. In 34th International Symposium on Distributed Computing (DISC), 2020.
-
Ittai Abraham, Kartik Nayak, Ling Ren, and Zhuolun Xiang. Good-case latency of byzantine broadcast: A complete categorization. In Proceedings of the third annual ACM Symposium on Principles of Distributed Computing (PODC), pages 331-341, 2021.
-
Gabriel Bracha. Asynchronous byzantine agreement protocols. Information and Computation, 75(2):130-143, 1987.
-
Ran Canetti and Tal Rabin. Fast asynchronous byzantine agreement with optimal resilience. In Proceedings of the twenty-fifth annual ACM symposium on Theory of computing (STOC), pages 42-51, 1993.
-
Danny Dolev, Joseph Y Halpern, Barbara Simons, and Ray Strong. Dynamic fault-tolerant clock synchronization. Journal of the ACM (JACM), 42(1):143-185, 1995.
-
Danny Dolev and Rüdiger Reischuk. Bounds on information exchange for byzantine agreement. Journal of the ACM (JACM), 32(1):191-204, 1985.
-
Danny Dolev, Ruediger Reischuk, and H Raymond Strong. Early stopping in byzantine agreement. Journal of the ACM (JACM), 37(4):720-741, 1990.
-
Danny Dolev and H. Raymond Strong. Authenticated algorithms for byzantine agreement. SIAM Journal on Computing, 12(4):656-666, 1983.
-
Michael J Fischer and Nancy A Lynch. A lower bound for the time to assure interactive consistency. Information Processing Letters, 14(4):183-186, 1982.
-
Damien Imbs and Michel Raynal. Trading off t-resilience for efficiency in asynchronous byzantine reliable broadcast. Parallel Processing Letters, 26(04):1650017, 2016.
-
Leslie Lamport, Robert Shostak, and Marshall Pease. The byzantine generals problem. ACM Transactions on Programming Languages and Systems, 4(3):382-401, 1982.