• Byzantine-Tolerant Causal Broa...

Treffer: Byzantine-Tolerant Causal Broadcast

Title:
Byzantine-Tolerant Causal Broadcast
Authors:
Auvolat, Alex, Frey, Davide, Raynal, Michel, Taïani, François
Contributors:
the World Is Distributed Exploring the tension between scale and coordination (WIDE), Centre Inria de l'Université de Rennes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-SYSTÈMES LARGE ÉCHELLE (IRISA-D1), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT), Région Bretagne, "Stratégie d’Attractivité Durable” (Grant 462-2017), ANR-20-CE25-0002,ByBloS,Au-delà des Blockchains : Modules de construction pour les applications à grande échelle zero-confiance multi-utilisateurs(2020), ANR-10-LABX-0007,COMIN Labs,Digital Communication and Information Sciences for the Future Internet(2010)
Source:
Theoretical Computer Science. 885:55-68
Publisher Information:
CCSD; Elsevier, 2021.
Publication Year:
2021
Collection:
collection:UNIV-RENNES1
collection:CNRS
collection:INRIA
collection:UNIV-UBS
collection:INSA-RENNES
collection:INRIA-RENNES
collection:IRISA
collection:IRISA_SET
collection:INRIA_TEST
collection:TESTALAIN1
collection:CENTRALESUPELEC
collection:INRIA2
collection:UR1-HAL
collection:UR1-MATH-STIC
collection:UR1-UFR-ISTIC
collection:TEST-UR-CSS
collection:UNIV-RENNES
collection:INRIA-RENGRE
collection:ANR
collection:UR1-MATH-NUM
collection:CYBERSCHOOL
collection:INRIAARTDOI
Subject Terms:
Algorithm, Asynchronous message-passing system, Byzantine process, Causal message delivery, Fault-tolerance, Modularity, Reliable broadcast, Simplicity, [INFO.INFO-DC]Computer Science [cs], Distributed, Parallel, and Cluster Computing [cs.DC]
Original Identifier:
HAL: hal-03346710
Document Type:
Zeitschrift article<br />Journal articles
Language:
English
ISSN:
0304-3975
1879-2294
Relation:
info:eu-repo/semantics/altIdentifier/doi/10.1016/j.tcs.2021.06.021
DOI:
10.1016/j.tcs.2021.06.021
Access URL:
https://inria.hal.science/hal-03346710
https://inria.hal.science/hal-03346710v1/document
https://inria.hal.science/hal-03346710v1/file/Byz-CO-broadcast-TCS_20200702.pdf
Rights:
info:eu-repo/semantics/OpenAccess
Accession Number:
edshal.hal.03346710v1
Database:
HAL

Weitere Informationen

Causal broadcast is a communication abstraction built on top of point-to-point send/receive networks, which ensures that any two messages whose broadcasts are causally related (as captured by Lamport's "happened before" relation) are delivered in their sending order. Several causal broadcast algorithms have been designed for failure-free and crash-prone asynchronous message-passing systems. This article first gives a formal definition of a causal broadcast abstraction in the presence of Byzantine processes, in the form of two equivalent characterizations, and then presents a simple causal broadcast algorithm that implements it. The main difficulty in the design and the proof of this algorithm comes from the very nature of Byzantine faults: Byzantine processes may have arbitrary behavior, and the algorithm must ensure that correct processes (i) maintain a coherent view of causality and (ii) are never prevented from communicating between themselves. To this end, the algorithm is built modularly, namely it works on top of any Byzantine-tolerant reliable broadcast algorithm. Due to this modularity, the proposed algorithm is easy to understand and inherits the computability assumptions (notably the maximal number of processes that may be Byzantine) and the message/time complexities of the underlying reliable broadcast on top of which it is built.