License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.DISC.2022.35
URN: urn:nbn:de:0030-drops-172267
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/17226/
Go to the corresponding LIPIcs Volume Portal

Sutra, Pierre

The Weakest Failure Detector for Genuine Atomic Multicast

pdf-format:
LIPIcs-DISC-2022-35.pdf (0.9 MB)

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

BibTeX - Entry

@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/opus/volltexte/2022/17226},
  URN =		{urn:nbn:de:0030-drops-172267},
  doi =		{10.4230/LIPIcs.DISC.2022.35},
  annote =	{Keywords: Failure Detector, State Machine Replication, Consensus}
}

Keywords: Failure Detector, State Machine Replication, Consensus
Collection: 36th International Symposium on Distributed Computing (DISC 2022)
Issue Date: 2022
Date of publication: 17.10.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI