Document Open Access Logo

Byzantine Consensus Is Θ(n²): The Dolev-Reischuk Bound Is Tight Even in Partial Synchrony!

Authors Pierre Civit, Muhammad Ayaz Dzulfikar, Seth Gilbert, Vincent Gramoli, Rachid Guerraoui, Jovan Komatovic, Manuel Vidigueira

PDF
Thumbnail PDF

File

LIPIcs.DISC.2022.14.pdf
  • Filesize: 0.84 MB
  • 21 pages

Document Identifiers

Author Details

Pierre Civit
  • Sorbonne University, Paris, France
Muhammad Ayaz Dzulfikar
  • NUS Singapore, Singapore
Seth Gilbert
  • NUS Singapore, Singapore
Vincent Gramoli
  • University of Sydney, Australia
  • Redbelly Network, Sydney, Australia
Rachid Guerraoui
  • Ecole Polytechnique Fédérale de Lausanne (EPFL), Switzerland
Jovan Komatovic
  • Ecole Polytechnique Fédérale de Lausanne (EPFL), Switzerland
Manuel Vidigueira
  • Ecole Polytechnique Fédérale de Lausanne (EPFL), Switzerland

Funding

This work is supported in part by the ARC Future Fellowship funding scheme (#180100496).
  • Gilbert, Seth: Supported in part by Singapore MOE grant MOE2018-T2-1-160.

Acknowledgements

The authors would like to thank Gregory Chockler and Alexey Gotsman for helpful conversations.

Cite As Get BibTex

Pierre Civit, Muhammad Ayaz Dzulfikar, Seth Gilbert, Vincent Gramoli, Rachid Guerraoui, Jovan Komatovic, and Manuel Vidigueira. Byzantine Consensus Is Θ(n²): The Dolev-Reischuk Bound Is Tight Even in Partial Synchrony!. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 14:1-14:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.DISC.2022.14

Abstract

The Dolev-Reischuk bound says that any deterministic Byzantine consensus protocol has (at least) quadratic communication complexity in the worst case. While it has been shown that the bound is tight in synchronous environments, it is still unknown whether a consensus protocol with quadratic communication complexity can be obtained in partial synchrony. Until now, the most efficient known solutions for Byzantine consensus in partially synchronous settings had cubic communication complexity (e.g., HotStuff, binary DBFT).
This paper closes the existing gap by introducing SQuad, a partially synchronous Byzantine consensus protocol with quadratic worst-case communication complexity. In addition, SQuad is optimally-resilient and achieves linear worst-case latency complexity. The key technical contribution underlying SQuad lies in the way we solve view synchronization, the problem of bringing all correct processes to the same view with a correct leader for sufficiently long. Concretely, we present RareSync, a view synchronization protocol with quadratic communication complexity and linear latency complexity, which we utilize in order to obtain SQuad.

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed algorithms
Keywords
  • Optimal Byzantine consensus
  • Communication complexity
  • Latency complexity

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Ittai Abraham, T-H. Hubert Chan, Danny Dolev, Kartik Nayak, Rafael Pass, Ling Ren, and Elaine Shi. Communication Complexity of Byzantine Agreement, Revisited. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC '19, pages 317-326, New York, NY, USA, 2019. Association for Computing Machinery. URL: https://doi.org/10.1145/3293611.3331629.
  2. Ittai Abraham, Srinivas Devadas, Kartik Nayak, and Ling Ren. Brief Announcement: Practical Synchronous Byzantine Consensus. In Andréa W. Richa, editor, 31st International Symposium on Distributed Computing, DISC 2017, October 16-20, 2017, Vienna, Austria, volume 91 of LIPIcs, pages 41:1-41:4. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. URL: https://doi.org/10.4230/LIPIcs.DISC.2017.41.
  3. Ittai Abraham, Philipp Jovanovic, Mary Maller, Sarah Meiklejohn, Gilad Stern, and Alin Tomescu. Reaching Consensus for Asynchronous Distributed Key Generation. In Avery Miller, Keren Censor-Hillel, and Janne H. Korhonen, editors, PODC '21: ACM Symposium on Principles of Distributed Computing, Virtual Event, Italy, July 26-30, 2021, pages 363-373. ACM, 2021. URL: https://doi.org/10.1145/3465084.3467914.
  4. Ittai Abraham, Dahlia Malkhi, Kartik Nayak, Ling Ren, and Alexander Spiegelman. Solida: A Blockchain Protocol Based on Reconfigurable Byzantine Consensus. In James Aspnes, Alysson Bessani, Pascal Felber, and João Leitão, editors, 21st International Conference on Principles of Distributed Systems, OPODIS 2017, Lisbon, Portugal, December 18-20, 2017, volume 95 of LIPIcs, pages 25:1-25:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. URL: https://doi.org/10.4230/LIPIcs.OPODIS.2017.25.
  5. Ittai Abraham, Dahlia Malkhi, and Alexander Spiegelman. Asymptotically Optimal Validated Asynchronous Byzantine Agreement. Proceedings of the Annual ACM Symposium on Principles of Distributed Computing, pages 337-346, 2019. Google Scholar
  6. 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 (PODC), pages 337-346, 2019. Google Scholar
  7. Marcin Andrychowicz and Stefan Dziembowski. PoW-Based Distributed Cryptography with No Trusted Setup. In Rosario Gennaro and Matthew Robshaw, editors, Advances in Cryptology - CRYPTO 2015 - 35th Annual Cryptology Conference, Santa Barbara, CA, USA, August 16-20, 2015, Proceedings, Part II, volume 9216 of Lecture Notes in Computer Science, pages 379-399. Springer, 2015. URL: https://doi.org/10.1007/978-3-662-48000-7_19.
  8. Karolos Antoniadis, Antoine Desjardins, Vincent Gramoli, Rachid Guerraoui, and Igor Zablotchi. Leaderless Consensus. In Proceedings - International Conference on Distributed Computing Systems, volume 2021-July, pages 392-402, 2021. Google Scholar
  9. Michael Ben-Or. Another Advantage of Free Choice: Completely Asynchronous Agreement Protocols. Proceedings of the Second Annual Symposium on Principles of Distributed Computing, pages 27-30, 1983. Google Scholar
  10. Piotr Berman, Juan A. Garay, and Kenneth J. Perry. Bit Optimal Distributed Consensus. Computer Science: Research and Applications, pages 313-321, 1992. Google Scholar
  11. Gabriel Bracha. Asynchronous Byzantine Agreement Protocols. Inf. Comput., 75(2):130-143, 1987. URL: https://doi.org/10.1016/0890-5401(87)90054-X.
  12. Manuel Bravo, Gregory Chockler, and Alexey Gotsman. Making Byzantine Consensus Live. In 34th International Symposium on Distributed Computing (DISC), volume 179(23), pages 1-17, 2020. Google Scholar
  13. Ethan Buchman, Jae Kwon, and Zarko Milosevic. The latest gossip on BFT consensus. CoRR, pages 1-14, 2018. URL: http://arxiv.org/abs/1807.04938.
  14. Christian Cachin, Klaus Kursawe, and Victor Shoup. Random Oracles in Constantinople: Practical Asynchronous Byzantine Agreement Using Cryptography. J. Cryptol., 18(3):219-246, 2005. URL: https://doi.org/10.1007/s00145-005-0318-0.
  15. Miguel Castro and Barbara Liskov. Practical Byzantine Fault Tolerance. ACM Trans. Comput. Syst., pages 359-368, 2002. Google Scholar
  16. Tushar Chandra and Sam Toueg. Unreliable Failure Detectors for Reliable Distributed Systems. Proceedings of the 10th ACM Symposium on Principles of Distributed Computing, pages 225-267, 1996. Google Scholar
  17. Tushar Deepak Chandra, Vassos Hadzilacos, and Sam Toueg. The Weakest Failure Detector for Solving Consensus. Proceedings of the Annual ACM Symposium on Principles of Distributed Computing, 43(4):147-158, 1992. Google Scholar
  18. Jing Chen, Sergey Gorbunov, Silvio Micali, and Georgios Vlachos. Algorand Agreement: Super Fast and Partition Resilient Byzantine Agreement. Cryptology ePrint Archive, 377:1-10, 2018. URL: https://eprint.iacr.org/2018/377.pdf.
  19. Pierre Civit, Muhammad Ayaz Dzulfikar, Seth Gilbert, Vincent Gramoli, Rachid Guerraoui, Jovan Komatovic, and Manuel Vidigueira. Byzantine Consensus is Θ(n²): The Dolev-Reischuk Bound is Tight even in Partial Synchrony! [Extended Version], 2022. URL: https://doi.org/10.48550/ARXIV.2208.09262.
  20. Shir Cohen, Idit Keidar, and Oded Naor. Byzantine Agreement with Less Communication: Recent Advances. SIGACT News, 52(1):71-80, 2021. URL: https://doi.org/10.1145/3457588.3457600.
  21. Shir Cohen, Idit Keidar, and Alexander Spiegelman. Brief Announcement: Not a COINcidence: Sub-Quadratic Asynchronous Byzantine Agreement WHP. Proceedings of the Annual ACM Symposium on Principles of Distributed Computing, pages 175-177, 2020. Google Scholar
  22. Tyler Crain, Vincent Gramoli, Mikel Larrea, and Michel Raynal. DBFT: Efficient Byzantine Consensus with a Weak Coordinator and its Application to Consortium Blockchains. In 17th IEEE International Symposium on Network Computing and Applications, NCA, pages 1-41, 2017. URL: http://arxiv.org/abs/1702.03068.
  23. D. Dolev and H. R. Strong. Authenticated Algorithms for Byzantine Agreement. SIAM Journal on Computing, 12(4):656-666, 1983. Google Scholar
  24. 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. Google Scholar
  25. Danny Dolev and Rüdiger Reischuk. Bounds on information exchange for Byzantine agreement. Journal of the ACM (JACM), 1985. Google Scholar
  26. Cynthia Dwork, Lynch Nancy, and Larry Stockmeyer. Consensus in the Presence of Partial Synchrony. Journal of the ACM (JACM), 35(2):288-323, 1988. Google Scholar
  27. Michael J. Fischer, Nancy A. Lynch, and Michael S. Paterson. Impossibility of Distributed Consensus with One Faulty Process. Journal of the Association for Computing Machinery,, 32(2):374-382, 1985. Google Scholar
  28. Eli Gafni. Round-by-Round Fault Detectors: Unifying Synchrony and Asynchrony. Proceedings of the Annual ACM Symposium on Principles of Distributed Computing, pages 143-152, 1998. Google Scholar
  29. Juan A. Garay, Aggelos Kiayias, Nikos Leonardos, and Giorgos Panagiotakos. Bootstrapping the Blockchain, with Applications to Consensus and Fast PKI Setup. In Michel Abdalla and Ricardo Dahab, editors, Public-Key Cryptography - PKC 2018 - 21st IACR International Conference on Practice and Theory of Public-Key Cryptography, Rio de Janeiro, Brazil, March 25-29, 2018, Proceedings, Part II, volume 10770 of Lecture Notes in Computer Science, pages 465-495. Springer, 2018. URL: https://doi.org/10.1007/978-3-319-76581-5_16.
  30. Guy Golan Gueta, Ittai Abraham, Shelly Grossman, Dahlia Malkhi, Benny Pinkas, Michael Reiter, Dragos Adrian Seredinschi, Orr Tamir, and Alin Tomescu. SBFT: A Scalable and Decentralized Trust Infrastructure. Proceedings - 49th Annual IEEE/IFIP International Conference on Dependable Systems and Networks, DSN 2019, pages 568-580, 2019. Google Scholar
  31. Vincent Gramoli. From blockchain consensus back to Byzantine consensus. Future Gener. Comput. Syst., 107:760-769, 2020. URL: https://doi.org/10.1016/j.future.2017.09.023.
  32. Rachid Guerraoui and Michel Raynal. The Information Structure of Indulgent Consensus. IEEE Trans. Computers, 53(4):453-466, 2004. Google Scholar
  33. Idit Keidar and Alexander Shraer. Timeliness, Failure-Detectors, and Consensus Performance. Proceedings of the Annual ACM Symposium on Principles of Distributed Computing, 2006:169-178, 2006. Google Scholar
  34. Kim Potter Kihlstrom, Louise E. Moser, and P. M. Melliar-Smith. Byzantine Fault Detectors for Solving Consensus. The Computer Journal, 46(1):16-35, 2003. Google Scholar
  35. Valerie King and Jared Saia. Breaking the O(n²) Bit Barrier: Scalable Byzantine agreement with an Adaptive Adversary. Journal of the ACM, 58(4):1-24, 2011. Google Scholar
  36. Ramakrishna Kotla, Lorenzo Alvisi, Mike Dahlin, Allen Clement, and Edmund Wong. Zyzzyva: Speculative Byzantine Fault Tolerance. ACM Transactions on Computer Systems, 27(4), 2009. Google Scholar
  37. Petr Kuznetsov, Andrei Tonkikh, and Yan X. Zhang. Revisiting Optimal Resilience of Fast Byzantine Consensus. Proceedings of the Annual ACM Symposium on Principles of Distributed Computing (PODC), 1(1):343-353, 2021. Google Scholar
  38. Leslie Lamport, Robert Shostak, and Marshall Pease. The Byzantine Generals Problem. ACM Trans. Program. Lang. Syst., 4(3):382-401, 1982. Google Scholar
  39. Andrew Lewis-Pye. Quadratic worst-case message complexity for State Machine Replication in the partial synchrony model, 2022. URL: https://doi.org/10.48550/ARXIV.2201.01107.
  40. Benoît Libert, Marc Joye, and Moti Yung. Born and Raised Distributively: Fully Distributed Non-Interactive Adaptively-Secure Threshold Signatures with Short Shares. Theoretical Computer Science, 645:1-24, 2016. Google Scholar
  41. JongBeom Lim, Taeweon Suh, Joon-Min Gil, and Heon-Chang Yu. Scalable and leaderless Byzantine consensus in cloud computing environments. Inf. Syst. Frontiers, 16(1):19-34, 2014. URL: https://doi.org/10.1007/s10796-013-9460-7.
  42. Thomas Locher. Fast Byzantine Agreement for Permissioned Distributed Ledgers. Annual ACM Symposium on Parallelism in Algorithms and Architectures, pages 371-382, 2020. Google Scholar
  43. Yuan Lu, Zhenliang Lu, Qiang Tang, and Guiling Wang. Dumbo-MVBA: Optimal Multi-Valued Validated Asynchronous Byzantine Agreement, Revisited. Proceedings of the Annual ACM Symposium on Principles of Distributed Computing, pages 129-138, 2020. Google Scholar
  44. Jean Philippe Martin and Lorenzo Alvisi. Fast Byzantine Consensus. Proceedings of the International Conference on Dependable Systems and Networks, pages 402-411, 2005. Google Scholar
  45. Silvio Micali. Byzantine Agreement , Made Trivial, 2017. Google Scholar
  46. Atsuki Momose and Ling Ren. Optimal Communication Complexity of Authenticated Byzantine Agreement. In 35th International Symposium on Distributed Computing (DISC), volume 209(32), pages 32:1-32:0. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany, 2021. Google Scholar
  47. Achour Mostéfaoui, Hamouma Moumen, and Michel Raynal. Signature-Free Asynchronous Binary Byzantine Consensus with t less n/3, O(n2) Messages, and O(1) Expected Time. J. ACM, 62(4):31:1-31:21, 2015. URL: https://doi.org/10.1145/2785953.
  48. Oded Naor, Mathieu Baudet, Dahlia Malkhi, and Alexander Spiegelman. Cogsworth: Byzantine View Synchronization. Cryptoeconomic Systems, 2021. Google Scholar
  49. Oded Naor and Idit Keidar. Expected Linear Round Synchronization: The Missing Link for Linear Byzantine SMR. 34th International Symposium on Distributed Computing (DISC), 179, 2020. Google Scholar
  50. Rafael Pass and Elaine Shi. Thunderella: Blockchains with Optimistic Instant Confirmation. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 10821 LNCS:3-33, 2018. Google Scholar
  51. Michael O. Rabin. Randomized Byzantine Generals. In 24th Annual Symposium on Foundations of Computer Science, Tucson, Arizona, USA, 7-9 November 1983, pages 403-409. IEEE Computer Society, 1983. URL: https://doi.org/10.1109/SFCS.1983.48.
  52. Hari Govind V. Ramasamy and Christian Cachin. Parsimonious Asynchronous Byzantine-Fault-Tolerant Atomic Broadcast. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 3974 LNCS:88-102, 2006. Google Scholar
  53. Alexander Spiegelman. In Search for an Optimal Authenticated Byzantine Agreement. In Seth Gilbert, editor, 35th International Symposium on Distributed Computing (DISC 2021), volume 209 of Leibniz International Proceedings in Informatics (LIPIcs), pages 38:1-38:19, Dagstuhl, Germany, 2021. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. URL: https://doi.org/10.4230/LIPIcs.DISC.2021.38.
  54. T. K. Srikanth and Sam Toueg. Optimal Clock Synchronization. Journal of the Association for Computing Machinery, 34(3):71-86, 1987. Google Scholar
  55. The Diem Team. DiemBFT v4: State Machine Replication in the Diem Blockchain, 2021. URL: https://developers.diem.com/papers/diem-consensus-state-machine-replication-in-the-diem-blockchain/2021-08-17.pdf.
  56. Maofan Yin, Dahlia Malkhi, Michael K. Reiter, Guy Golan Gueta, and Ittai Abraham. HotStuff: BFT Consensus with Linearity and Responsiveness. Proceedings of the Annual ACM Symposium on Principles of Distributed Computing, pages 347-356, 2019. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact