Search Results

Documents authored by Sutra, Pierre

Document
DOI: 10.4230/LIPIcs.DISC.2022.35
The Weakest Failure Detector for Genuine Atomic Multicast

Authors: Pierre Sutra

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

Abstract
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 ℱ = ∅.
Cite as

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
DOI: 10.4230/LIPIcs.DISC.2020.24
Leaderless State-Machine Replication: Specification, Properties, Limits

Authors: Tuanir França Rezende and Pierre Sutra

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

Abstract
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.
Cite as

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
DOI: 10.4230/LIPIcs.OPODIS.2015.18
Anonymous Obstruction-Free (n,k)-Set Agreement with n-k+1 Atomic Read/Write Registers

Authors: Zohir Bouzid, Michel Raynal, and Pierre Sutra

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

Abstract
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).
Cite as

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}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact