Skip to Main content Skip to Navigation
New interface
Journal articles

Byzantine-Tolerant Causal Broadcast

Alex Auvolat 1 Davide Frey 1 Michel Raynal 1 François Taïani 1 
1 WIDE - the World Is Distributed Exploring the tension between scale and coordination
Inria Rennes – Bretagne Atlantique , IRISA-D1 - SYSTÈMES LARGE ÉCHELLE
Abstract : 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.
Complete list of metadata
Contributor : François Taïani Connect in order to contact the contributor
Submitted on : Thursday, September 16, 2021 - 3:25:19 PM
Last modification on : Tuesday, October 25, 2022 - 4:20:38 PM
Long-term archiving on: : Friday, December 17, 2021 - 7:15:03 PM


Files produced by the author(s)



Alex Auvolat, Davide Frey, Michel Raynal, François Taïani. Byzantine-Tolerant Causal Broadcast. Theoretical Computer Science, 2021, 885, pp.55-68. ⟨10.1016/j.tcs.2021.06.021⟩. ⟨hal-03346710⟩



Record views


Files downloads