2026-07-25T06:17:47Z https://drops.dagstuhl.de/oai
oai:drops-oai.dagstuhl.de:17226 2024-03-06T10:59:16Z ddc:004 open_access
The Weakest Failure Detector for Genuine Atomic Multicast Sutra, Pierre Failure Detector State Machine Replication Consensus 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 β„± = βˆ…. Schloss Dagstuhl – Leibniz-Zentrum fΓΌr Informatik Pierre Sutra 2022 Is Part Of LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.DISC.2022.35 urn:nbn:de:0030-drops-172267 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2022.35 eng https://creativecommons.org/licenses/by/4.0/legalcode