Skip to Main content Skip to Navigation
Conference papers

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.
Complete list of metadata

https://hal.inria.fr/hal-03332423
Contributor : Pierre Sens Connect in order to contact the contributor
Submitted on : Thursday, September 2, 2021 - 4:43:52 PM
Last modification on : Tuesday, June 14, 2022 - 8:26:53 AM
Long-term archiving on: : Friday, December 3, 2021 - 8:52:18 PM

File

srds-2021.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-03332423, version 1

Citation

Colette Johnen, Luciana Arantes, Pierre Sens. FIFO and Atomic broadcast algorithms with bounded message size for dynamic systems. SRDS 2021 - 40th International Symposium on Reliable Distributed Systems, Sep 2021, Chicago / Virtual, United States. ⟨hal-03332423⟩

Share

Metrics

Record views

80

Files downloads

118