Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Conferences, Workshops, Symposiums, and Seminars
  4. Dynamic Byzantine Reliable Broadcast
 
conference paper

Dynamic Byzantine Reliable Broadcast

Guerraoui, Rachid  
•
Komatovic, Jovan  
•
Kuznetsov, Petr
Show more
2021
Proceedings of the 24th International Conference on Principles of Distributed Systems (OPODIS 2020)
24th International Conference on Principles of Distributed Systems (OPODIS 2020)

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. LIPIcs, Vol. 184, 24th International Conference on Principles of Distributed Systems (OPODIS 2020), pages 23:1-23:18

  • Files
  • Details
  • Metrics
Type
conference paper
DOI
10.4230/lipics.opodis.2020.23
Author(s)
Guerraoui, Rachid  
Komatovic, Jovan  
Kuznetsov, Petr
Pignolet, Yvonne-Anne
Seredinschi, Dragos-Adrian
Tonkikh, Andrei
Date Issued

2021

Publisher

Schloss Dagstuhl--Leibniz-Zentrum f{"u}r Informatik

Publisher place

Dagstuhl

Published in
Proceedings of the 24th International Conference on Principles of Distributed Systems (OPODIS 2020)
ISBN of the book

978-3-959771-76-4

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
DCL  
Event nameEvent placeEvent date
24th International Conference on Principles of Distributed Systems (OPODIS 2020)

Strasbourg, France (Virtual Conference)

Decembre 14-16, 2020

Available on Infoscience
September 14, 2022
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/190806
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés