Document

**Published in:** LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022)

Atomic broadcast is a group communication primitive to order messages across a set of distributed processes. Atomic multicast is its natural generalization where each message m is addressed to dst(m), a subset of the processes called its destination group. A solution to atomic multicast is genuine when a process takes steps only if a message is addressed to it. Genuine solutions are the ones used in practice because they have better performance.
Let 𝒢 be all the destination groups and ℱ be the cyclic families in it, that is the subsets of 𝒢 whose intersection graph is hamiltonian. This paper establishes that the weakest failure detector to solve genuine atomic multicast is 𝜇 = (∧_{g,h ∈ 𝒢} Σ_{g ∩ h}) ∧ (∧_{g ∈ 𝒢} Ω_g) ∧ γ, where Σ_P and Ω_P are the quorum and leader failure detectors restricted to the processes in P, and γ is a new failure detector that informs the processes in a cyclic family f ∈ ℱ when f is faulty.
We also study two classical variations of atomic multicast. The first variation requires that message delivery follows the real-time order. In this case, 𝜇 must be strengthened with 1^{g ∩ h}, the indicator failure detector that informs each process in g ∪ h when g ∩ h is faulty. The second variation requires a message to be delivered when the destination group runs in isolation. We prove that its weakest failure detector is at least 𝜇 ∧ (∧_{g, h ∈ 𝒢} Ω_{g ∩ h}). This value is attained when ℱ = ∅.

Pierre Sutra. The Weakest Failure Detector for Genuine Atomic Multicast. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 35:1-35:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{sutra:LIPIcs.DISC.2022.35, author = {Sutra, Pierre}, title = {{The Weakest Failure Detector for Genuine Atomic Multicast}}, booktitle = {36th International Symposium on Distributed Computing (DISC 2022)}, pages = {35:1--35:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-255-6}, ISSN = {1868-8969}, year = {2022}, volume = {246}, editor = {Scheideler, Christian}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2022.35}, URN = {urn:nbn:de:0030-drops-172267}, doi = {10.4230/LIPIcs.DISC.2022.35}, annote = {Keywords: Failure Detector, State Machine Replication, Consensus} }

Document

**Published in:** LIPIcs, Volume 179, 34th International Symposium on Distributed Computing (DISC 2020)

Modern Internet services commonly replicate critical data across several geographical locations using state-machine replication (SMR). Due to their reliance on a leader replica, classical SMR protocols offer limited scalability and availability in this setting. To solve this problem, recent protocols follow instead a leaderless approach, in which each replica is able to make progress using a quorum of its peers. In this paper, we study this new emerging class of SMR protocols and states some of their limits. We first propose a framework that captures the essence of leaderless state-machine replication (Leaderless SMR). Then, we introduce a set of desirable properties for these protocols: (R)eliability, (O)ptimal (L)atency and (L)oad Balancing. We show that protocols matching all of the ROLL properties are subject to a trade-off between performance and reliability. We also establish a lower bound on the message delay to execute a command in protocols optimal for the ROLL properties. This lower bound explains the persistent chaining effect observed in experimental results.

Tuanir França Rezende and Pierre Sutra. Leaderless State-Machine Replication: Specification, Properties, Limits. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 24:1-24:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{francarezende_et_al:LIPIcs.DISC.2020.24, author = {Fran\c{c}a Rezende, Tuanir and Sutra, Pierre}, title = {{Leaderless State-Machine Replication: Specification, Properties, Limits}}, booktitle = {34th International Symposium on Distributed Computing (DISC 2020)}, pages = {24:1--24:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-168-9}, ISSN = {1868-8969}, year = {2020}, volume = {179}, editor = {Attiya, Hagit}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2020.24}, URN = {urn:nbn:de:0030-drops-131024}, doi = {10.4230/LIPIcs.DISC.2020.24}, annote = {Keywords: Fault Tolerance, State Machine Replication, Consensus} }

Document

**Published in:** LIPIcs, Volume 46, 19th International Conference on Principles of Distributed Systems (OPODIS 2015)

The k-set agreement problem is a generalization of the consensus problem. Namely, assuming that each process proposes a value, every non-faulty process should decide one of the proposed values, and no more than k different values should be decided. This is a hard problem in the sense that we cannot solve it in an asynchronous system, as soon as k or more processes may crash. One way to sidestep this impossibility result consists in weakening the termination property, requiring that a process must decide a value only if it executes alone during a long enough period of time. This is the well-known obstruction-freedom progress condition.
Consider a system of n anonymous asynchronous processes that communicate through atomic read/write registers, and such that any number of them may crash. In this paper, we address and solve the challenging open problem of designing an obstruction-free k-set agreement algorithm using only (n-k+1) atomic registers. From a shared memory cost point of view, our algorithm is the best algorithm known so far, thereby establishing a new upper bound on the number of registers needed to solve the problem, and in comparison to the previous upper bound, its gain is (n-k) registers. We then extend this algorithm into a space-optimal solution for the repeated version of k-set agreement, and an x-obstruction-free solution that employs 0(n-k+x) atomic registers (with 1 <= x <= k < n).

Zohir Bouzid, Michel Raynal, and Pierre Sutra. Anonymous Obstruction-Free (n,k)-Set Agreement with n-k+1 Atomic Read/Write Registers. In 19th International Conference on Principles of Distributed Systems (OPODIS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 46, pp. 18:1-18:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{bouzid_et_al:LIPIcs.OPODIS.2015.18, author = {Bouzid, Zohir and Raynal, Michel and Sutra, Pierre}, title = {{Anonymous Obstruction-Free (n,k)-Set Agreement with n-k+1 Atomic Read/Write Registers}}, booktitle = {19th International Conference on Principles of Distributed Systems (OPODIS 2015)}, pages = {18:1--18:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-98-9}, ISSN = {1868-8969}, year = {2016}, volume = {46}, editor = {Anceaume, Emmanuelle and Cachin, Christian and Potop-Butucaru, Maria}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2015.18}, URN = {urn:nbn:de:0030-drops-66092}, doi = {10.4230/LIPIcs.OPODIS.2015.18}, annote = {Keywords: Anonymous processes, Asynchronous system, Atomic read/write register, Consensus, Fault-tolerance, \$k\$-Set agreement, Obstruction-freedom, Upper bound} }