FIFO and Atomic broadcast algorithms with bounded message size for dynamic systems

Abstract : 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 TC^R of Time-varying Graph formalism). 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 an FIFO atomic broadcast algorithm in Class TC^R that uses the proposed FIFO broadcast and deliver primitives.