Document Open Access Logo

Dynamic Byzantine Reliable Broadcast

Authors Rachid Guerraoui, Jovan Komatovic, Petr Kuznetsov, Yvonne-Anne Pignolet, Dragos-Adrian Seredinschi, Andrei Tonkikh

PDF
Thumbnail PDF

File

LIPIcs.OPODIS.2020.23.pdf
  • Filesize: 1.12 MB
  • 18 pages

Document Identifiers

Author Details

Rachid Guerraoui
  • EPFL, Lausanne, Switzerland
Jovan Komatovic
  • EPFL, Lausanne, Switzerland
Petr Kuznetsov
  • LTCI, Télécom Paris, Institut Polytechnique Paris, France
Yvonne-Anne Pignolet
  • DFINITY Foundation, Zürich, Switzerland
Dragos-Adrian Seredinschi
  • Informal Systems, Lausanne, Switzerland
Andrei Tonkikh
  • National Research University Higher School of Economics, St. Petersburg, Russia

Funding

This Work Has Been Supported in Part by the Interchain Foundation, Cross-Chain Validation Project.

Cite As Get BibTex

Rachid Guerraoui, Jovan Komatovic, Petr Kuznetsov, Yvonne-Anne Pignolet, Dragos-Adrian Seredinschi, and Andrei Tonkikh. Dynamic Byzantine Reliable Broadcast. In 24th International Conference on Principles of Distributed Systems (OPODIS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 184, pp. 23:1-23:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.OPODIS.2020.23

Abstract

Reliable broadcast is a communication primitive guaranteeing, intuitively, that all processes in a distributed system deliver the same set of messages. The reason why this primitive is appealing is twofold: (i) we can implement it deterministically in a completely asynchronous environment, unlike stronger primitives like consensus and total-order broadcast, and yet (ii) reliable broadcast is powerful enough to implement important applications like payment systems.
The problem we tackle in this paper is that of dynamic reliable broadcast, i.e., enabling processes to join or leave the system. This property is desirable for long-lived applications (aiming to be highly available), yet has been precluded in previous asynchronous reliable broadcast protocols. We study this property in a general adversarial (i.e., Byzantine) environment.
We introduce the first specification of a dynamic Byzantine reliable broadcast (dbrb) primitive that is amenable to an asynchronous implementation. We then present an algorithm implementing this specification in an asynchronous network. Our dbrb algorithm ensures that if any correct process in the system broadcasts a message, then every correct process delivers that message unless it leaves the system. Moreover, if a correct process delivers a message, then every correct process that has not expressed its will to leave the system delivers that message. We assume that more than 2/3 of processes in the system are correct at all times, which is tight in our context.
We also show that if only one process in the system can fail - and it can fail only by crashing - then it is impossible to implement a stronger primitive, ensuring that if any correct process in the system broadcasts or delivers a message, then every correct process in the system delivers that message - including those that leave.

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed algorithms
Keywords
  • Byzantine reliable broadcast
  • deterministic distributed algorithms
  • dynamic distributed systems

Metrics

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

Related Versions

References

  1. Marcos K Aguilera, Idit Keidar, Dahlia Malkhi, and Alexander Shraer. Dynamic atomic storage without consensus. Journal of the ACM (JACM), 58(2):7, 2011. Google Scholar
  2. Eduardo Alchieri, Alysson Bessani, Fabíola Greve, and Joni Fraga. Efficient and modular consensus-free reconfiguration for fault-tolerant storage. arXiv preprint arXiv:1607.05344, 2016. Google Scholar
  3. Hagit Attiya, Hyun Chul Chung, Faith Ellen, Saptaparni Kumar, and Jennifer L. Welch. Emulating a shared register in a system that never stops changing. IEEE Trans. Parallel Distrib. Syst., 30(3):544-559, 2019. Google Scholar
  4. Hagit Attiya, Sweta Kumari, Archit Somani, and Jennifer L. Welch. Store-collect in the presence of continuous churn with application to snapshots and lattice agreement. CoRR, abs/2003.07787, 2020. URL: https://arxiv.org/abs/2003.07787.
  5. Roberto Baldoni, Silvia Bonomi, Anne-Marie Kermarrec, and Michel Raynal. Implementing a register in a dynamic distributed system. In DISC, pages 639-647. IEEE, 2009. Google Scholar
  6. Roberto Baldoni, Silvia Bonomi, Anne-Marie Kermarrec, and Michel Raynal. Implementing a register in a dynamic distributed system. In ICDCS, pages 639-647, 2009. Google Scholar
  7. Gabriel Bracha. Asynchronous byzantine agreement protocols. Information and Computation, 75(2):130-143, 1987. Google Scholar
  8. Gabriel Bracha and Sam Toueg. Asynchronous Consensus and Broadcast Protocols. JACM, 32(4), 1985. Google Scholar
  9. Christian Cachin, Rachid Guerraoui, and Luís Rodrigues. Introduction to reliable and secure distributed programming. Springer Science & Business Media, 2011. Google Scholar
  10. Gregory V Chockler, Idit Keidar, and Roman Vitenberg. Group communication specifications: a comprehensive study. ACM Computing Surveys (CSUR), 33(4):427-469, 2001. Google Scholar
  11. 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.
  12. Eli Gafni and Dahlia Malkhi. Elastic configuration maintenance via a parsimonious speculating snapshot solution. In DISC, pages 140-153. Springer, 2015. Google Scholar
  13. Haoyan Geng and Robbert Van Renesse. Sprinkler - Reliable broadcast for geographically dispersed datacenters. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 8275 LNCS:247-266, 2013. URL: https://doi.org/10.1007/978-3-642-45065-5_13.
  14. Rachid Guerraoui, Jovan Komatovic, Petr Kuznetsov, Yvonne-Anne Pignolet, Dragos-Adrian Seredinschi, and Andrei Tonkikh. Dynamic Byzantine Reliable Broadcast [Technical Report]. arXiv preprint arXiv:2001.06271, 2020. URL: https://arxiv.org/abs/2001.06271.
  15. Rachid Guerraoui, Petr Kuznetsov, Matteo Monti, Matej Pavlovič, and Dragos-Adrian Seredinschi. The consensus number of a cryptocurrency. In PODC, pages 307-316, 2019. Google Scholar
  16. Rachid Guerraoui, Petr Kuznetsov, Matteo Monti, Matej Pavlovic, and Dragos-Adrian Seredinschi. Scalable byzantine reliable broadcast. In DISC, pages 22:1-22:16, 2019. Google Scholar
  17. Leander Jehl, Roman Vitenberg, and Hein Meling. Smartmerge: A new approach to reconfiguration for atomic storage. In International Symposium on Distributed Computing, pages 154-169. Springer, 2015. Google Scholar
  18. Anne-Marie Kermarrec and Maarten Van Steen. Gossiping in distributed systems. ACM SIGOPS operating systems review, 41(5):2-7, 2007. Google Scholar
  19. Saptaparni Kumar and Jennifer L. Welch. Byzantine-tolerant register in a system with continuous churn. CoRR, abs/1910.06716, 2019. URL: http://arxiv.org/abs/1910.06716.
  20. Petr Kuznetsov, Thibault Rieutord, and Sara Tucci-Piergiovanni. Reconfigurable lattice agreement and applications. In OPODIS, 2019. Google Scholar
  21. Petr Kuznetsov and Andrei Tonkikh. Asynchronous reconfiguration with byzantine failures. In DISC, pages 27:1-27:17, 2020. Google Scholar
  22. Dahlia Malkhi, Michael Merritt, and Ohad Rodeh. Secure Reliable Multicast Protocols in a WAN. In ICDCS, 1997. Google Scholar
  23. Dahlia Malkhi and Michael Reiter. A high-throughput secure reliable multicast protocol. Journal of Computer Security, 5(2):113-127, 1997. Google Scholar
  24. Satoshi Nakamoto. Bitcoin: A peer-to-peer electronic cash system. Whitepaper, 2008. Google Scholar
  25. Fernando Pedone and André Schiper. Handling message semantics with generic broadcast protocols. Distributed Computing, 15(2):97-107, 2002. Google Scholar
  26. Alexander Spiegelman and Idit Keidar. On liveness of dynamic storage. In SIROCCO, pages 356-376. Springer, 2017. Google Scholar
  27. Josef Widder and Ulrich Schmid. Booting clock synchronization in partially synchronous systems with hybrid process and link failures. Distributed Computing, 20(2):115-140, 2007. 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