LIPIcs.DISC.2023.39.pdf
- Filesize: 0.53 MB
- 6 pages
Document
Brief Announcement: Subquadratic Multivalued Asynchronous Byzantine Agreement WHP
Authors
-
Part of:
Volume:
37th International Symposium on Distributed Computing (DISC 2023)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Symposium on Distributed Computing (DISC) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2023-10-05
Cite As Get BibTex
Shir Cohen and Idit Keidar. Brief Announcement: Subquadratic Multivalued Asynchronous Byzantine Agreement WHP. In 37th International Symposium on Distributed Computing (DISC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 281, pp. 39:1-39:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.DISC.2023.39
Abstract
There have been several reductions from multivalued consensus to binary consensus over the past 20 years. To the best of our knowledge, none of them solved it for Byzantine asynchronous settings. In this short paper, we close this gap. Moreover, we do so in subquadratic communication, using newly developed subquadratic binary Byzantine Agreement techniques.
Subject Classification
ACM Subject Classification
- Theory of computation → Distributed algorithms
- Theory of computation → Cryptographic primitives
- Mathematics of computing → Probabilistic algorithms
Keywords
- Byzantine agreement
- subquadratic communication
- fault tolerance in distributed systems
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
Ittai Abraham, Dahlia Malkhi, and Alexander Spiegelman. Asymptotically optimal validated asynchronous byzantine agreement. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, pages 337-346, 2019.
-
Erica Blum, Jonathan Katz, Chen-Da Liu-Zhang, and Julian Loss. Asynchronous byzantine agreement with subquadratic communication. Cryptology ePrint Archive, Report 2020/851, 2020.
-
Shir Cohen and Idit Keidar. Subquadratic multivalued asynchronous byzantine agreement whp. arXiv preprint arXiv:2308.02927, 2023.
-
Shir Cohen, Idit Keidar, and Alexander Spiegelman. Not a coincidence: Sub-quadratic asynchronous byzantine agreement whp. In 34th International Symposium on Distributed Computing (DISC 2020). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2020.
-
Danny Dolev and Rüdiger Reischuk. Bounds on information exchange for byzantine agreement. J. ACM, 32(1):191-204, January 1985.
-
Yossi Gilad, Rotem Hemo, Silvio Micali, Georgios Vlachos, and Nickolai Zeldovich. Algorand: Scaling byzantine agreements for cryptocurrencies. In Proceedings of the 26th Symposium on Operating Systems Principles, pages 51-68, 2017.
-
Valerie King and Jared Saia. Breaking the O(n²) bit barrier: scalable byzantine agreement with an adaptive adversary. Journal of the ACM (JACM), 58(4):1-24, 2011.
-
Leslie Lamport, Robert Shostak, and Marshall Pease. The byzantine generals problem. ACM Trans. Program. Lang. Syst., 4(3):382-401, July 1982.
-
Silvio Micali, Michael Rabin, and Salil Vadhan. Verifiable random functions. In Foundations of Computer Science, 1999. 40th Annual Symposium on, pages 120-130. IEEE, 1999.
-
Achour Mostéfaoui, Hamouma Moumen, and Michel Raynal. Signature-free asynchronous binary byzantine consensus with t < n/3, O(n²) messages, and O(1) expected time. Journal of the ACM (JACM), 62(4):31, 2015.
-
Achour Mostefaoui, Michel Raynal, and Frédéric Tronel. From binary consensus to multivalued consensus in asynchronous message-passing systems. Information Processing Letters, 73(5-6):207-212, 2000.
-
Russell Turpin and Brian A Coan. Extending binary byzantine agreement to multivalued byzantine agreement. Information Processing Letters, 18(2):73-76, 1984.