Document Open Access Logo

Good-Case Early-Stopping Latency of Synchronous Byzantine Reliable Broadcast: The Deterministic Case

Authors Timothé Albouy, Davide Frey, Michel Raynal, François Taïani

PDF
Thumbnail PDF

File

LIPIcs.DISC.2022.4.pdf
  • Filesize: 0.88 MB
  • 22 pages

Document Identifiers

Author Details

Timothé Albouy
  • Univ Rennes, Inria, CNRS, IRISA, France
Davide Frey
  • Univ Rennes, Inria, CNRS, IRISA, France
Michel Raynal
  • Univ Rennes, Inria, CNRS, IRISA, France
François Taïani
  • Univ Rennes, Inria, CNRS, IRISA, France

Funding

This work was partially supported by the French ANR project ByBLoS (ANR-20-CE25-0002-01), and by the PriCLeSS project granted by the Labex CominLabs excellence laboratory of the French ANR (ANR-10-LABX-07-01).

Acknowledgements

The authors would like to thank the anonymous reviewers whose careful reading and suggestions helped them improve their paper.

Cite AsGet BibTex

Timothé Albouy, Davide Frey, Michel Raynal, and François Taïani. Good-Case Early-Stopping Latency of Synchronous Byzantine Reliable Broadcast: The Deterministic Case. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 4:1-4:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.DISC.2022.4

Abstract

This paper considers the good-case latency of Byzantine Reliable Broadcast (BRB), i.e., the time taken by correct processes to deliver a message when the initial sender is correct, and an essential property for practical distributed systems. Although significant strides have been made in recent years on this question, progress has mainly focused on either asynchronous or randomized algorithms. By contrast, the good-case latency of deterministic synchronous BRB under a majority of Byzantine faults has been little studied. In particular, it was not known whether a good-case latency below the worst-case bound of t+1 rounds could be obtained under a Byzantine majority. In this work, we answer this open question positively and propose a deterministic synchronous Byzantine reliable broadcast that achieves a good-case latency of max(2,t+3-c) rounds, where t is the upper bound on the number of Byzantine processes, and c the number of effectively correct processes.

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed algorithms
Keywords
  • Reliable Broadcast
  • Byzantine Faults
  • Synchronous Systems
  • Good-case latency
  • Deterministic Algorithms

Metrics

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

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 ACM Symposium on Principles of Distributed Computing (PODC), pages 317-326, New York, NY, USA, 2019. URL: https://doi.org/10.1145/3293611.3331629.
  2. Ittai Abraham, Dahlia Malkhi, Kartik Nayak, Ling Ren, and Maofan Yin. Sync hotstuff: Simple and practical synchronous state machine replication. In IEEE Symposium on Security and Privacy (S&P), pages 106-118, 2020. Google Scholar
  3. Ittai Abraham, Kartik Nayak, Ling Ren, and Zhuolun Xiang. Good-case latency of byzantine broadcast: A complete categorization. In ACM Symposium on Principles of Distributed Computing (PODC), pages 331-341, 2021. Google Scholar
  4. Ittai Abraham, Kartik Nayak, Ling Ren, and Zhuolun Xiang. Good-case latency of byzantine broadcast: A complete categorization. In arXiv:2102.07240v2, pages 1-38, 2021. Google Scholar
  5. Hagit Attiya and Jennifer L. Welch. Distributed computing - fundamentals, simulations, and advanced topics (2. ed.). Wiley series on parallel and distributed computing. Wiley, 2004. Google Scholar
  6. Alex Auvolat, Davide Frey, Michel Raynal, and François Taïani. Money transfer made simple: a specification, a generic algorithm and its proof. Bulletin of EATCS, 132, 2020. Google Scholar
  7. Alex Auvolat, Davide Frey, Michel Raynal, and François Taïani. Byzantine-tolerant causal broadcast. Theoretical Computer Science, 885:55-68, 2021. Google Scholar
  8. Mathieu Baudet, George Danezis, and Alberto Sonnino. Fastpay: High-performance byzantine fault tolerant settlement. In ACM Advances in Financial Technologies, pages 163-177, 2020. Google Scholar
  9. Gabriel Bracha. Asynchronous byzantine agreement protocols. Information & Computation, 75(2):130-143, 1987. Google Scholar
  10. Christian Cachin, Rachid Guerraoui, and Luís E. T. Rodrigues. Introduction to Reliable and Secure Distributed Programming (2. ed.). Springer, 2011. Google Scholar
  11. Jing Chen and Silvio Micali. Algorand: A secure and efficient distributed ledger. Theoretical Computer Science, 777:155-183, 2019. Google Scholar
  12. Daniel Collins, Rachid Guerraoui, Jovan Komatovic, Petr Kuznetsov, Matteo Monti, Matej Pavlovic, Yvonne-Anne Pignolet, Dragos-Adrian Seredinschi, Andrei Tonkikh, and Athanasios Xygkis. Online payments by merely broadcasting messages. In Dependable Systems and Networks (DSN), pages 26-38. IEEE, 2020. Google Scholar
  13. Danny Dolev, Ruediger Reischuk, and H Raymond Strong. Early stopping in byzantine agreement. Journal of the ACM, 37(4):720-741, 1990. Google Scholar
  14. Danny Dolev and H. Raymond Strong. Authenticated algorithms for byzantine agreement. SIAM Journal on Computing, 12(4):656-666, 1983. Google Scholar
  15. Cynthia Dwork, Nancy A. Lynch, and Larry J. Stockmeyer. Consensus in the presence of partial synchrony. Journal of the ACM, 35(2):288-323, 1988. Google Scholar
  16. Matthias Fitzi and Jesper Buus Nielsen. On the number of synchronous rounds sufficient for authenticated byzantine agreement. In International Symposium on Distributed Computing (DISC), pages 449-463. Springer, 2009. Google Scholar
  17. Rachid Guerraoui, Nikola Knezevic, Vivien Quéma, and Marko Vukolic. The next 700 BFT protocols. In EuroSys, pages 363-376. ACM, 2010. Google Scholar
  18. Rachid Guerraoui, Petr Kuznetsov, Matteo Monti, Matej Pavlovic, and Dragos-Adrian Seredinschi. The consensus number of a cryptocurrency. Distributed Computing, 35(1):1-15, 2022. Google Scholar
  19. Damien Imbs and Michel Raynal. Trading off t-resilience for efficiency in asynchronous byzantine reliable broadcast. Parallel Processing Letters, 26(4):1650017:1-1650017:8, 2016. Google Scholar
  20. Leslie Lamport, Robert E. Shostak, and Marshall C. Pease. The Byzantine Generals Problem. ACM Transactions on Programming Languages and Systems, 4(3):382-401, 1982. Google Scholar
  21. Silvio Micali, Michael O. Rabin, and Salil P. Vadhan. Verifiable random functions. In 40th IEEE Symposium on the Foundations of Computer Science (FOCS), pages 120-130, 1999. Google Scholar
  22. Achour Mostéfaoui, Moumen Hamouma, and Michel Raynal. Signature-free asynchronous byzantine consensus with t < n/3 and o(n²) messages. In ACM Symposium on Principles of Distributed Computing (PODC), pages 2-9. ACM, 2014. Google Scholar
  23. Kartik Nayak, Ling Ren, Elaine Shi, Nitin H. Vaidya, and Zhuolun Xiang. Improved extension protocols for byzantine broadcast and agreement. In International Symposium on Distributed Computing (DISC), volume 179 of LIPIcs, pages 28:1-28:17, 2020. Google Scholar
  24. Marshall C. Pease, Robert E. Shostak, and Leslie Lamport. Reaching agreement in the presence of faults. Journal of the ACM, 27(2):228-234, 1980. Google Scholar
  25. Michel Raynal. Fault-Tolerant Message-Passing Distributed Systems - An Algorithmic Approach. Springer, 2018. Google Scholar
  26. Jun Wan, Hanshen Xiao, Srinivas Devadas, and Elaine Shi. Round-efficient byzantine broadcast under strongly adaptive and majority corruptions. In 18th Theory of Cryptography Conference (TCC), LNCS 12550, pages 412-456. Springer, 2020. Google Scholar
  27. Jun Wan, Hanshen Xiao, Elaine Shi, and Srinivas Devadas. Expected constant round byzantine broadcast under dishonest majority. In 18th Theory of Cryptography Conference (TCC), LNCS 12550, pages 381-411. Springer, 2020. 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 Imprint Privacy Contact