Document Open Access Logo

Expected Linear Round Synchronization: The Missing Link for Linear Byzantine SMR

Authors Oded Naor, Idit Keidar

PDF

File

Thumbnail PDF
PDF
LIPIcs.DISC.2020.26.pdf
  • Filesize: 0.79 MB
  • 17 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Computing methodologies → Distributed algorithms
Keywords
  • Distributed Systems
  • State Machine Replication

Metrics

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

Abstract

State Machine Replication (SMR) solutions often divide time into rounds, with a designated leader driving decisions in each round. Progress is guaranteed once all correct processes synchronize to the same round, and the leader of that round is correct. Recently suggested Byzantine SMR solutions such as HotStuff, Tendermint, and LibraBFT achieve progress with a linear message complexity and a constant time complexity once such round synchronization occurs. But round synchronization itself incurs an additional cost. By Dolev and Reischuk’s lower bound, any deterministic solution must have Ω(n²) communication complexity. Yet the question of randomized round synchronization with an expected linear message complexity remained open.
We present an algorithm that, for the first time, achieves round synchronization with expected linear message complexity and expected constant latency. Existing protocols can use our round synchronization algorithm to solve Byzantine SMR with the same asymptotic performance.

Cite As Get BibTex

Oded Naor and Idit Keidar. Expected Linear Round Synchronization: The Missing Link for Linear Byzantine SMR. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 26:1-26:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.DISC.2020.26

Author Details

Oded Naor
  • Technion - Israel Institute of Technology, Haifa, Israel
Idit Keidar
  • Technion - Israel Institute of Technology, Haifa, Israel

References

  1. 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. Google Scholar
  2. Marcin Andrychowicz, Stefan Dziembowski, Daniel Malinowski, and Lukasz Mazurek. Secure multiparty computations on bitcoin. In 2014 IEEE Symposium on Security and Privacy, pages 443-458. IEEE, 2014. Google Scholar
  3. Baruch Awerbuch. Complexity of network synchronization. Journal of the ACM (JACM), 32(4):804-823, 1985. Google Scholar
  4. Mathieu Baudet, Avery Ching, Andrey Chursin, George Danezis, François Garillot, Zekun Li, Dahlia Malkhi, Oded Naor, Dmitri Perelman, and Alberto Sonnino. State machine replication in the libra blockchain, 2019. Google Scholar
  5. Shai Ben-David, Allan Borodin, Richard Karp, Gabor Tardos, and Avi Wigderson. On the power of randomization in on-line algorithms. Algorithmica, 11(1):2-14, 1994. Google Scholar
  6. Ken Birman and Thomas Joseph. Exploiting virtual synchrony in distributed systems. In Proceedings of the eleventh ACM Symposium on Operating systems principles, pages 123-138, 1987. Google Scholar
  7. Erica Blum, Jonathan Katz, Chen-Da Liu-Zhang, and Julian Loss. Asynchronous byzantine agreement with subquadratic communication. Cryptology ePrint Archive, Report 2020/851, 2020. Google Scholar
  8. Manuel Blum. Coin flipping by telephone a protocol for solving impossible problems. ACM SIGACT News, 15(1):23-27, 1983. Google Scholar
  9. Dan Boneh, Ben Lynn, and Hovav Shacham. Short signatures from the weil pairing. In International Conference on the Theory and Application of Cryptology and Information Security, pages 514-532. Springer, 2001. Google Scholar
  10. Allan Borodin, Nathan Linial, and Michael E Saks. An optimal on-line algorithm for metrical task system. Journal of the ACM (JACM), 39(4):745-763, 1992. Google Scholar
  11. Gabriel Bracha. Asynchronous Byzantine agreement protocols. Information and Computation, 75(2):130-143, 1987. Google Scholar
  12. Manuel Bravo, Gregory Chockler, and Alexey Gotsman. Making byzantine consensus live. In 34st International Symposium on Distributed Computing (DISC 2020). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2020. Google Scholar
  13. Ethan Buchman, Jae Kwon, and Zarko Milosevic. The latest gossip on BFT consensus. arXiv preprint arXiv:1807.04938, 2018. Google Scholar
  14. Vitalik Buterin and Virgil Griffith. Casper the friendly finality gadget. arXiv preprint arXiv:1710.09437, 2017. Google Scholar
  15. Christian Cachin, Klaus Kursawe, and Victor Shoup. Random oracles in Constantinople: Practical asynchronous byzantine agreement using cryptography. Journal of Cryptology, 18(3):219-246, 2005. Google Scholar
  16. Miguel Castro, Barbara Liskov, et al. Practical Byzantine fault tolerance. In OSDI, volume 99, pages 173-186, 1999. Google Scholar
  17. Richard Cleve. Limits on the security of coin flips when half the processors are faulty. In Proceedings of the eighteenth annual ACM symposium on Theory of computing, pages 364-369, 1986. Google Scholar
  18. Shir Cohen, Idit Keidar, and Alexander Spiegelman. Not a coincidence: Sub-quadratic asynchronous byzantine agreement whp. In 34st International Symposium on Distributed Computing (DISC 2020). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2020. Google Scholar
  19. Danny Dolev and Ruediger Reischuk. Bounds on information exchange for byzantine agreement. In Proceedings of the First ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, PODC '82, page 132–140, New York, NY, USA, 1982. Association for Computing Machinery. Google Scholar
  20. Cynthia Dwork, Nancy Lynch, and Larry Stockmeyer. Consensus in the presence of partial synchrony. Journal of the ACM (JACM), 35(2):288-323, 1988. Google Scholar
  21. Amos Fiat, Richard Karp, Mike Luby, Lyle McGeoch, Daniel Sleator, and Neal E Young. Competitive paging algorithms. arXiv preprint cs/0205038, 2002. Google Scholar
  22. Michael J Fischer, Nancy A Lynch, and Michael S Paterson. Impossibility of distributed consensus with one faulty process. Journal of the ACM (JACM), 32(2):374-382, 1985. Google Scholar
  23. Bryan Ford. Threshold logical clocks for asynchronous distributed coordination and consensus. arXiv preprint arXiv:1907.07010, 2019. Google Scholar
  24. Eli Gafni. Round-by-round fault detectors (extended abstract) unifying synchrony and asynchrony. In Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing, pages 143-152, 1998. Google Scholar
  25. 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. In 2019 49th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN), pages 568-580. IEEE, 2019. Google Scholar
  26. Idit Keidar and Danny Dolev. Efficient message ordering in dynamic networks. In Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing, pages 68-76, 1996. Google Scholar
  27. Idit Keidar and Alexander Shraer. Timeliness, failure-detectors, and consensus performance. In Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, pages 169-178, 2006. Google Scholar
  28. Idit Keidar and Alexander Shraer. How to choose a timing model. IEEE Transactions on Parallel and Distributed Systems, 19(10):1367-1380, 2008. Google Scholar
  29. Ramakrishna Kotla, Lorenzo Alvisi, Mike Dahlin, Allen Clement, and Edmund Wong. Zyzzyva: speculative byzantine fault tolerance. In ACM SIGOPS Operating Systems Review, volume 41, pages 45-58. ACM, 2007. Google Scholar
  30. Leslie Lamport et al. Paxos made simple. ACM Sigact News, 32(4):18-25, 2001. Google Scholar
  31. Tal Moran, Moni Naor, and Gil Segev. An optimally fair coin toss. In Theory of Cryptography Conference, pages 1-18. Springer, 2009. Google Scholar
  32. Oded Naor, Mathieu Baudet, Dahlia Malkhi, and Alexander Spiegelman. Cogsworth: Byzantine view synchronization. In Proceedings of the Cryptoeconomic Systems Conference (CES'20), 2020. Google Scholar
  33. Oded Naor and Idit Keidar. Expected linear round synchronization: The missing link for linear byzantine smr. arXiv preprint arXiv:2002.07539, 2020. Google Scholar
  34. Brian M Oki and Barbara H Liskov. Viewstamped replication: A new primary copy method to support highly-available distributed systems. In Proceedings of the seventh annual ACM Symposium on Principles of distributed computing, pages 8-17. ACM, 1988. Google Scholar
  35. HariGovind V Ramasamy and Christian Cachin. Parsimonious asynchronous byzantine-fault-tolerant atomic broadcast. In International Conference On Principles Of Distributed Systems, pages 88-102. Springer, 2005. Google Scholar
  36. Victor Shoup. Practical threshold signatures. In International Conference on the Theory and Applications of Cryptographic Techniques, pages 207-220. Springer, 2000. Google Scholar
  37. Maofan Yin, Dahlia Malkhi, MK Reiter and, Guy Golan Gueta, and Ittai Abraham. HotStuff: BFT consensus with linearity and responsiveness. In 38th ACM symposium on Principles of Distributed Computing (PODC'19), 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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact