Document Open Access Logo

Scalable Byzantine Reliable Broadcast

Authors Rachid Guerraoui, Petr Kuznetsov, Matteo Monti, Matej Pavlovic, Dragos-Adrian Seredinschi

PDF
Thumbnail PDF

File

LIPIcs.DISC.2019.22.pdf
  • Filesize: 0.58 MB
  • 16 pages

Document Identifiers

Author Details

Rachid Guerraoui
  • EPFL, Lausanne, Switzerland
Petr Kuznetsov
  • LTCI, Télécom Paris, IP Paris, Paris, France
Matteo Monti
  • EPFL, Lausanne, Switzerland
Matej Pavlovic
  • EPFL, Lausanne, Switzerland
Dragos-Adrian Seredinschi
  • EPFL, Lausanne, Switzerland

Funding

This work has been supported in part by the European ERC Grant 339539 - AOC.

Cite AsGet BibTex

Rachid Guerraoui, Petr Kuznetsov, Matteo Monti, Matej Pavlovic, and Dragos-Adrian Seredinschi. Scalable Byzantine Reliable Broadcast. In 33rd International Symposium on Distributed Computing (DISC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 146, pp. 22:1-22:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.DISC.2019.22

Abstract

Byzantine reliable broadcast is a powerful primitive that allows a set of processes to agree on a message from a designated sender, even if some processes (including the sender) are Byzantine. Existing broadcast protocols for this setting scale poorly, as they typically build on quorum systems with strong intersection guarantees, which results in linear per-process communication and computation complexity. We generalize the Byzantine reliable broadcast abstraction to the probabilistic setting, allowing each of its properties to be violated with a fixed, arbitrarily small probability. We leverage these relaxed guarantees in a protocol where we replace quorums with stochastic samples. Compared to quorums, samples are significantly smaller in size, leading to a more scalable design. We obtain the first Byzantine reliable broadcast protocol with logarithmic per-process communication and computation complexity. We conduct a complete and thorough analysis of our protocol, deriving bounds on the probability of each of its properties being compromised. During our analysis, we introduce a novel general technique that we call adversary decorators. Adversary decorators allow us to make claims about the optimal strategy of the Byzantine adversary without imposing any additional assumptions. We also introduce Threshold Contagion, a model of message propagation through a system with Byzantine processes. To the best of our knowledge, this is the first formal analysis of a probabilistic broadcast protocol in the Byzantine fault model. We show numerically that practically negligible failure probabilities can be achieved with realistic security parameters.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Probabilistic algorithms
  • Mathematics of computing → Stochastic processes
  • Theory of computation → Distributed algorithms
  • Theory of computation → Distributed computing models
Keywords
  • Byzantine reliable broadcast
  • probabilistic distributed algorithms
  • scalable distributed systems
  • stochastic processes

Metrics

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

Related Versions

  • An extended version of this article - which includes a thorough analysis of our protocols - appears on arXiv at https://arxiv.org/abs/1908.01738v1 [Guerraoui et al., 2019].

References

  1. Daron Acemoglu and Asu Ozdaglar. 6.207/14.15: Networks - Lecture 4: Erdős–Rényi Graphs and Phase Transitions, 2009. URL: https://economics.mit.edu/files/4622.
  2. Dan Alistarh, Seth Gilbert, Rachid Guerraoui, and Morteza Zadimoghaddam. How Efficient Can Gossip Be? (on the Cost of Resilient Information Exchange). In Proceedings of the 37th International Colloquium Conference on Automata, Languages and Programming: Part II, ICALP'10, pages 115-126, Berlin, Heidelberg, 2010. Springer-Verlag. URL: http://dl.acm.org/citation.cfm?id=1880999.1881012.
  3. Hagit Attiya, Amotz Bar-Noy, and Danny Dolev. Sharing memory robustly in message-passing systems. JACM, 42(1), 1995. Google Scholar
  4. Chen Avin, Michael Borokhovich, Keren Censor-Hillel, and Zvi Lotker. Order Optimal Information Spreading Using Algebraic Gossip. In Proceedings of the 30th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, PODC '11, pages 363-372, New York, NY, USA, 2011. ACM. URL: https://doi.org/10.1145/1993806.1993883.
  5. Baruch Awerbuch and Christian Scheideler. Towards a scalable and robust DHT. Theory of Computing Systems, 45(2):234-260, 2009. Google Scholar
  6. Petra Berenbrink, Robert Elsaesser, and Tom Friedetzky. Efficient Randomised Broadcasting in Random Regular Networks with Applications in Peer-to-peer Systems. In Proceedings of the Twenty-seventh ACM Symposium on Principles of Distributed Computing, PODC '08, pages 155-164, New York, NY, USA, 2008. ACM. URL: https://doi.org/10.1145/1400751.1400773.
  7. Petra Berenbrink, Robert Elsässer, and Thomas Sauerwald. Communication Complexity of Quasirandom Rumor Spreading. In Proceedings of the 18th Annual European Conference on Algorithms: Part I, ESA'10, pages 134-145, Berlin, Heidelberg, 2010. Springer-Verlag. URL: http://dl.acm.org/citation.cfm?id=1888935.1888952.
  8. Petra Berenbrink, Robert Elsässer, and Thomas Sauerwald. Randomised Broadcasting: Memory vs. Randomness. Theoretical Computer Science, 520:306-319, April 2010. URL: https://doi.org/10.1007/978-3-642-12200-2_28.
  9. Kenneth P. Birman, Mark Hayden, Oznur Ozkasap, Zhen Xiao, Mihai Budiu, and Yaron Minsky. Bimodal Multicast. ACM Trans. Comput. Syst., 17(2):41-88, May 1999. URL: https://doi.org/10.1145/312203.312207.
  10. Edward Bortnikov, Maxim Gurevich, Idit Keidar, Gabriel Kliot, and Alexander Shraer. Brahms: Byzantine resilient random membership sampling. Computer Networks, 53(13):2340-2359, 2009. Gossiping in Distributed Systems. URL: https://doi.org/10.1016/j.comnet.2009.03.008.
  11. Elette Boyle, Shafi Goldwasser, and Stefano Tessaro. Communication Locality in Secure Multi-party Computation. In Theory of Cryptography, 2013. Google Scholar
  12. Gabriel Bracha. Asynchronous Byzantine agreement protocols. Information and Computation, 75(2):130-143, 1987. Google Scholar
  13. Gabriel Bracha and Sam Toueg. Asynchronous Consensus and Broadcast Protocols. JACM, 32(4), 1985. Google Scholar
  14. Christian Cachin, Rachid Guerraoui, and Luís Rodrigues. Introduction to Reliable and Secure Distributed Programming. Springer Publishing Company, Incorporated, 2nd edition, 2011. Google Scholar
  15. Christian Cachin and Jonathan A. Poritz. Secure Intrusion-tolerant Replication on the Internet. In DSN, 2002. Google Scholar
  16. Nishanth Chandran, Wutichai Chongchitmate, Juan A. Garay, Shafi Goldwasser, Rafail Ostrovsky, and Vassilis Zikas. The Hidden Graph Model: Communication Locality and Optimal Resiliency with Adaptive Faults. In ITCS '15, 2015. Google Scholar
  17. Fan Chung and Linyuan Lu. The Diameter of Sparse Random Graphs. Advances in Applied Mathematics, 26:257–279, 2001. Google Scholar
  18. Roger Dingledine, Nick Mathewson, and Paul Syverson. Tor: The Second-generation Onion Router. In Proceedings of the 13th Conference on USENIX Security Symposium - Volume 13, SSYM'04, pages 21-21, Berkeley, CA, USA, 2004. USENIX Association. URL: http://dl.acm.org/citation.cfm?id=1251375.1251396.
  19. Sisi Duan, Michael K. Reiter, and Haibin Zhang. BEAT: Asynchronous BFT Made Practical. In CCS, 2018. Google Scholar
  20. Robert Elsässer and Dominik Kaaser. On the Influence of Graph Density on Randomized Gossiping. 2015 IEEE International Parallel and Distributed Processing Symposium, pages 521-531, 2015. Google Scholar
  21. Paul Erdös and Alfréd Rényi. On Random Graphs. Publicationes Mathematicae, 6:290–297, 1959. Google Scholar
  22. P. Th. Eugster, R. Guerraoui, S. B. Handurukande, P. Kouznetsov, and A.-M. Kermarrec. Lightweight Probabilistic Broadcast. ACM Trans. Comput. Syst., 21(4):341-374, November 2003. URL: https://doi.org/10.1145/945506.945507.
  23. Yaacov Fernandess, Antonio Fernández, and Maxime Monod. A Generic Theoretical Framework for Modeling Gossip-based Algorithms. SIGOPS Oper. Syst. Rev., 41(5):19-27, October 2007. URL: https://doi.org/10.1145/1317379.1317384.
  24. Juan Garay, Yuval Ishai, Rafail Ostrovsky, and Vassilis Zikas. The price of low communication in secure multi-party computation. In Annual International Cryptology Conference, pages 420-446. Springer, 2017. Google Scholar
  25. Juan A Garay, Jonathan Katz, Ranjit Kumaresan, and Hong-Sheng Zhou. Adaptively Secure Broadcast, Revisited. In PODC, pages 179-186, 2011. Google Scholar
  26. Chryssis Georgiou, Seth Gilbert, Rachid Guerraoui, and Dariusz R. Kowalski. On the Complexity of Asynchronous Gossip. In Proceedings of the Twenty-seventh ACM Symposium on Principles of Distributed Computing, PODC '08, pages 135-144, New York, NY, USA, 2008. ACM. URL: https://doi.org/10.1145/1400751.1400771.
  27. Chryssis Georgiou, Seth Gilbert, Rachid Guerraoui, and Dariusz R. Kowalski. Asynchronous Gossip. J. ACM, 60(2):11:1-11:42, May 2013. URL: https://doi.org/10.1145/2450142.2450147.
  28. Chryssis Georgiou, Seth Gilbert, and Dariusz R. Kowalski. Meeting the deadline: on the complexity of fault-tolerant continuous gossip. Distributed Computing, 24(5):223-244, December 2011. URL: https://doi.org/10.1007/s00446-011-0144-6.
  29. Mohsen Ghaffari and Merav Parter. A Polylogarithmic Gossip Algorithm for Plurality Consensus. In Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, PODC '16, pages 117-126, New York, NY, USA, 2016. ACM. URL: https://doi.org/10.1145/2933057.2933097.
  30. George Giakkoupis, Yasamin Nazari, and Philipp Woelfel. How Asynchrony Affects Rumor Spreading Time. In Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, PODC '16, pages 185-194, New York, NY, USA, 2016. ACM. URL: https://doi.org/10.1145/2933057.2933117.
  31. Rachid Guerraoui, Florian Huc, and Anne-Marie Kermarrec. Highly dynamic distributed computing with byzantine failures. In PODC, 2013. URL: http://dl.acm.org/citation.cfm?doid=2484239.2484263.
  32. Rachid Guerraoui, Anne-Marie Kermarrec, Matej Pavlovic, and Dragos-Adrian Seredinschi. Atum: Scalable Group Communication Using Volatile Groups. In Proceedings of the 17th International Middleware Conference, Middleware '16, pages 19:1-19:14, New York, NY, USA, 2016. ACM. URL: https://doi.org/10.1145/2988336.2988356.
  33. Rachid Guerraoui, Petr Kuznetsov, Matteo Monti, Matej Pavlovic, and Dragos Seredinschi. The Consensus Number of a Cryptocurrency. In PODC, 2019. Google Scholar
  34. Rachid Guerraoui, Petr Kuznetsov, Matteo Monti, Matej Pavlovic, and Dragos-Adrian Seredinschi. Scalable Byzantine Reliable Broadcast (Extended Version). arXiv preprint arXiv:1908.01738, Version 1, 2019. URL: http://arxiv.org/abs/1908.01738v1.
  35. Vassos Hadzilacos and Sam Toueg. Fault-tolerant broadcasts and related problems. In Sape J. Mullender, editor, Distributed Systems, chapter 5, pages 97-145. Addison-Wesley, 1993. Google Scholar
  36. Bernhard Haeupler, Gopal Pandurangan, David Peleg, Rajmohan Rajaraman, and Zhifeng Sun. Discovery Through Gossip. In Proceedings of the Twenty-fourth Annual ACM Symposium on Parallelism in Algorithms and Architectures, SPAA '12, pages 140-149, New York, NY, USA, 2012. ACM. URL: https://doi.org/10.1145/2312005.2312031.
  37. Márk Jelasity, Alberto Montresor, and Ozalp Babaoglu. T-Man: Gossip-based Fast Overlay Topology Construction. Comput. Netw., 53(13):2321-2339, August 2009. URL: https://doi.org/10.1016/j.comnet.2009.03.013.
  38. Valerie King, Steven Lonargan, Jared Saia, and Amitabh Trehan. Load Balanced Scalable Byzantine Agreement through Quorum Building, with Full Information. In International Conference on Distributed Computing and Networking, pages 203-214. Springer, 2011. Google Scholar
  39. Valerie King, Jared Saia, Vishal Sanwalani, and Erik Vee. Scalable Leader Election. In SODA, 2006. Google Scholar
  40. Leslie Lamport, Robert Shostak, and Marshall Pease. The Byzantine generals problem. TOPLAS, 4(3), 1982. Google Scholar
  41. Meng-Jang Lin, Keith Marzullo, and Stefano Masini. Gossip Versus Deterministically Constrained Flooding on Small Networks. In Proceedings of the 14th International Conference on Distributed Computing, DISC '00, pages 253-267, London, UK, UK, 2000. Springer-Verlag. URL: http://dl.acm.org/citation.cfm?id=645957.675970.
  42. Dahlia Malkhi, Michael Merritt, and Ohad Rodeh. Secure Reliable Multicast Protocols in a WAN. In ICDCS, 1997. Google Scholar
  43. Dahlia Malkhi and Michael Reiter. Byzantine quorum systems. In Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, pages 569-578. ACM, 1997. Google Scholar
  44. Dahlia Malkhi and Michael K. Reiter. A High-Throughput Secure Reliable Multicast Protocol. In CSFW, 1996. Google Scholar
  45. Dahlia Malkhi and Michael K. Reiter. A High-Throughput Secure Reliable Multicast Protocol. Journal of Computer Security, 5(2):113-128, 1997. URL: https://doi.org/10.3233/JCS-1997-5203.
  46. Dahlia Malkhi, Michael K Reiter, Avishai Wool, and Rebecca N Wright. Probabilistic Quorum Systems. Inf. Comput., 170(2):184-206, November 2001. URL: https://doi.org/10.1006/inco.2001.3054.
  47. Satoshi Nakamoto. Bitcoin: A Peer-to-Peer Electronic Cash System, 2008. Google Scholar
  48. Fernando Pedone and André Schiper. Handling message semantics with generic broadcast protocols. Distributed Computing, 15(2):97-107, 2002. Google Scholar
  49. Michael K. Reiter. Secure Agreement Protocols: Reliable and Atomic Group Multicast in Rampart. In CCS, 1994. Google Scholar
  50. Michael K. Reiter and Kenneth P. Birman. How to securely replicate services. ACM Transactions on Programming Languages and Systems (TOPLAS), 16(3), 1994. Google Scholar
  51. Christian Scheideler. How to Spread Adversarial Nodes? Rotate! In STOC, pages 704-713. ACM, 2005. Google Scholar
  52. Suman Sourav, Peter Robinson, and Seth Gilbert. Slow Links, Fast Links, and the Cost of Gossip. 2018 IEEE 38th International Conference on Distributed Computing Systems (ICDCS), pages 786-796, 2018. Google Scholar
  53. Sam Toueg. Randomized Byzantine Agreements. In Proceedings of the Third Annual ACM Symposium on Principles of Distributed Computing, PODC '84, pages 163-178, New York, NY, USA, 1984. ACM. URL: https://doi.org/10.1145/800222.806744.
  54. Jelle van den Hooff, David Lazar, Matei Zaharia, and Nickolai Zeldovich. Vuvuzela: Scalable Private Messaging Resistant to Traffic Analysis. In Proceedings of the 25th Symposium on Operating Systems Principles, SOSP '15, pages 137-152, New York, NY, USA, 2015. ACM. URL: https://doi.org/10.1145/2815400.2815417.
  55. Spyros Voulgaris, Márk Jelasity, and Maarten van Steen. A Robust and Scalable Peer-to-peer Gossiping Protocol. In Proceedings of the Second International Conference on Agents and Peer-to-Peer Computing, AP2PC'03, pages 47-58, Berlin, Heidelberg, 2004. Springer-Verlag. URL: https://doi.org/10.1007/978-3-540-25840-7_6.
  56. Marko Vukolic. The Origin of Quorum Systems. Bulletin of the EATCS, 101:125-147, 2010. URL: http://eatcs.org/beatcs/index.php/beatcs/article/view/183.
  57. B. Zhang, K. Han, B. Ravindran, and E. D. Jensen. RTQG: Real-Time Quorum-based Gossip Protocol for Unreliable Networks. In 2008 Third International Conference on Availability, Reliability and Security, pages 564-571, March 2008. URL: https://doi.org/10.1109/ARES.2008.139.
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