Skip to Main content Skip to Navigation
Conference papers

Self-stabilizing Uniform Reliable Broadcast

Abstract : We study a well-known communication abstraction called Uniform Reliable Broadcast (URB). URB is central in the design and implementation of fault-tolerant distributed systems, as many non-trivial fault-tolerant distributed applications require communication with provable guarantees on message deliveries. Our study focuses on fault-tolerant implementations for time-free messagepassing systems that are prone to node-failures. Moreover, we aim at the design of an even more robust communication abstraction. We do so through the lenses of self-stabilization|a very strong notion of fault-tolerance. In addition to node and communication failures, self-stabilizing algorithms can recover after the occurrence of arbitrary transient faults; these faults represent any violation of the assumptions according to which the system was designed to operate (as long as the algorithm code stays intact). This work proposes the first self-stabilizing URB solution for time-free message-passing systems that are prone to node-failures. The proposed algorithm has an O(bufferUnitSize) stabilization time (in terms of asynchronous cycles) from arbitrary transient faults, where bufferUnitSize is a predefined constant that can be set according to the available memory. Moreover, the communication costs of our algorithm are similar to the ones of the non-self-stabilizing state-ofthe-art. The main differences are that our proposal considers repeated gossiping of O(1) bits,messages and deals with bounded space (which is a prerequisite for self-stabilization). Specifically, each node needs to store up to bufferUnitSize n records and each record is of size O(v + n log n) bits, where n is the number of nodes in the system and v is the number of bits needed to encode a single URB instance.
Complete list of metadata

https://hal.inria.fr/hal-03148662
Contributor : Davide Frey Connect in order to contact the contributor
Submitted on : Monday, February 22, 2021 - 2:07:08 PM
Last modification on : Tuesday, October 19, 2021 - 11:04:42 AM

Links full text

Identifiers

Citation

Oskar Lundström, Michel Raynal, Elad M. Schiller. Self-stabilizing Uniform Reliable Broadcast. NETYS 2020 - 8th International Conference on NETworked sYStems, Jun 2020, virtual online, Morocco. pp.296-313, ⟨10.1007/978-3-030-67087-0_19⟩. ⟨hal-03148662⟩

Share

Metrics

Les métriques sont temporairement indisponibles