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

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.

Mots clés: Algorithm; Asynchronous message-passing system; Byzantine process; Causal message delivery; Fault-tolerance; Modularity; Reliable broadcast; Simplicity

Domaines: Calcul parallèle, distribué et partagé [cs.DC]

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⟩