GT AlgoDist, «FIFO and Atomic broadcast algorithms with bounded message size for dynamic systems», Colette Johnen
Colette Johnen (LaBRI)
Title: FIFO and Atomic broadcast algorithms with bounded message size for dynamic systems
FIFO broadcast provides application ordering semantics of messages broadcast by the same sender and have been mostly implemented on top of unreliable static networks.
A round-based FIFO broadcast algorithm with both termination detection and bounded message size for dynamic networks with recurrent connectivity is presented. 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. The size of any message is bounded to 2N+msgSize+O(log(N)) bits where msgSize is the bound size in bits of the broadcast data.
We also present an FIFO atomic broadcast algorithm that uses the proposed FIFO broadcast and deliver primitives.