Uniform reliable broadcast in anonymous distributed systems with fair lossy channels
- PDF / 477,570 Bytes
- 33 Pages / 439.37 x 666.142 pts Page_size
- 46 Downloads / 185 Views
Uniform reliable broadcast in anonymous distributed systems with fair lossy channels Jian Tang1 · Mikel Larrea2 · Sergio Arévalo1 · Ernesto Jiménez1 Received: 23 May 2019 / Accepted: 30 May 2020 © Springer-Verlag GmbH Austria, part of Springer Nature 2020
Abstract Uniform reliable broadcast (URB) is an important abstraction in distributed systems, offering delivery guarantee when spreading messages between processes. Informally, URB guarantees that if a process (correct or not) delivers a message m, then all correct processes deliver m. This abstraction has been extensively investigated in distributed systems where all processes have unique identifiers. Furthermore, the majority of papers in the literature usually assume that the communication channels of the system are reliable, which is not always the case in real systems. In this paper, the URB abstraction is investigated in anonymous asynchronous message passing distributed systems with process crash failures and fair lossy channels. For that, we assume the availability of a random number generator that generates unique global values with very high probability. Firstly, a simple URB algorithm is given assuming a majority of correct processes. Then, we prove the impossibility of solving URB without a majority of correct processes if no failure detector is used. Subsequently, a new failure detector class AΘ is proposed, which can be used to implement URB with any number of correct processes. However, the two previous URB algorithms are non-quiescent because every correct process, to offset the loss of messages caused by fair lossy channels, has to broadcast all URB_delivered messages forever. Hence, a perfect anonymous failure detector A P ∗ is proposed, together with AΘ, to make the URB algorithm quiescent. Finally, we discuss an alternative failure detector AΘ P ∗ , which combines the properties of AΘ and A P ∗ . Keywords Anonymous system · Asynchronous system · Message passing · Uniform reliable broadcast · Fault-tolerance · Fair lossy channel · Failure detector · Quiescence Mathematics Subject Classification 68W10 · 68R01
This research is partially supported by the Community of Madrid, under Grant EDGEDATA (P2018/TCS-4499), the Spanish Research Council, under Grants TIN2013-41123-P, TIN2013-46883-P, TIN2016-80350 and TIN2016-79897-P, the Basque Government, under Grants IT395-10 and IT980-16, and a scholarship of the Chinese Scholarship Council. Extended author information available on the last page of the article
123
J. Tang et al.
Contents 1 2 3 4 5
Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . System model and definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Implementing uniform reliable broadcast in A AS_Fn,t [t < n/2] . . . . . . . . . . An impossibility result . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Implementation of uniform reliable broadcast in A AS_Fn,t [AΘ] . . . . . . . . . . 5.1 Failure detector AΘ . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Data Loading...
