FIFO and Atomic broadcast algorithms with bounded message size for dynamic systems
Colette Johnen, Luciana Arantes, Pierre Sens · 2021
FIFO broadcast provides application ordering semantics of messages broadcast by the same sender and have been mostly implemented on top of unreliable static networks. In this article, we propose a round-based FIFO broadcast algorithm with both termination detection and bounded message size for dynamic networks with recurrent connectivity (Class$\mathcal{TC}^{\mathcal{R}}$of Time-varying Graph formalism [1]). Initially, processes only know the number of processes$N$in the system and their identifier. Due to the dynamics of the network links, messages can be lost. Since no unbounded timestamp is used to identify a message, its size is bounded to$2N+O(log(N))+msgSize$bits where msgSize is the bound size in bits of the broadcast data. We also present a FIFO atomic broadcast algorithm for dynamic networks with recurrent connectivity that uses the proposed FIFO broadcast and deliver primitives. This algorithm provides causal total order broadcast primitives.