The Weakest Failure Detector for Genuine Atomic Multicast

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