Telecom SudParis, France pierre.sutra@telecom-
sudparis.euhttps://orcid.org/0000-0002-0573-2572 P. Sutra [300]Theory of
computation Distributed computing models [300]Software and its engineering
Distributed systems organizing principles [300]General and reference
Reliability Christian Scheideler 1 36th International Symposium on Distributed
Computing (DISC 2022) DISC 2022 DISC 2022 October 25–27, 2022 Augusta,
Georgia, USA 246 5

# The Weakest Failure Detector for Genuine Atomic Multicast (Extended Version)

Pierre Sutra

###### Abstract

$\Sigma_{P}$and $\Omega_{P}$ are the quorum and leader failure detectors
restricted to the processes in $P$, and  $\gamma$is a new failure detector
that informs the processes in a cyclic family $\mathfrak{f}\in\mathcal{F}$
when $\mathfrak{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, $\mu$ must be strengthened with $1^{g\cap
h}$, the indicator failure detector that informs each process in $g\cup h$
when $g\cap 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
$\mu\land(\land_{g,h\in\mathcal{G}}\leavevmode\nobreak\ \Omega_{g\cap h})$.
This value is attained when $\mathcal{F}=\varnothing$.

###### keywords:

Failure Detector, State Machine Replication, Consensus

##  1 Introduction

##### Context

Multicast is a fundamental group communication primitive used in modern
computing infrastructures. This primitive allows to disseminate a message to a
subset of the processes in the system, its destination group. Implementations
exist over point-to-point protocols such as the Internet Protocol. Multicast
is atomic when it offers the properties of atomic broadcast to the multicast
primitive: each message is delivered at most once, and delivery occurs
following some global order. Atomic multicast is used to implement strongly
consistent data storage [isis, granola, pstore, janus].

It is easy to see that atomic multicast can be implemented atop atomic
broadcast. Each message is sent through atomic broadcast and delivered where
appropriate. Such a naive approach is however used rarely in practice because
it is inefficient when the number of destination groups is large
[multiringpaxos, versus]. To rule out naive implementations, Guerraoui and
Schiper [gamcast] introduce the notion of genuineness. An implementation of
atomic multicast is _genuine_ when a process takes steps only if a message is
addressed to it.

Existing genuine atomic multicast algorithms that are fault-tolerant have
strong synchrony assumptions on the underlying system. Some protocols (such as
[SchiperP08]) assume that a perfect failure detector is available.
Alternatively, a common assumption is that the destination groups are
decomposable into disjoint groups, each of these behaving as a logically
correct entity. Such an assumption is a consequence of the impossibility
result established in [gamcast]. This result states that genuine atomic
multicast requires some form of perfect failure detection in intersecting
groups. Consequently, almost all protocols published to date (e.g., [ramcast,
tempo, whitebox, fastcast, FritzkeIMR01, delporte]) assume the existence of
such a decomposition.

##### Motivation

A key observation is that the impossibility result in [gamcast] is established
when atomic multicast allows a message to be disseminated to _any_ subset of
the processes. However, where there is no such need, weaker synchrony
assumptions may just work. For instance, when each message is addressed to a
single process, the problem is trivial and can be solved in an asynchronous
system. Conversely, when every message is addressed to all the processes in
the system, atomic multicast boils down to atomic broadcast, and thus
ultimately to consensus. Now, if no two groups intersect, solving consensus
inside each group seems both necessary and sufficient. In this paper, we
further push this line of thought to characterize the necessary and sufficient
synchrony assumptions to solve genuine atomic multicast.

Our results are established in the unreliable failure detectors model [CT96,
petr]. A failure detector is an oracle available locally to each process that
provides information regarding the speed at which the other processes are
taking steps. Finding the weakest failure detector to solve a given problem is
a central question in distributed computing literature [petr]. In particular,
the seminal work in [omega] shows that a leader oracle ($\Omega$) is the
weakest failure detector for consensus when a majority of processes is
correct. If any processes might fail, then a quorum failure detector
($\Sigma$) is required in addition to $\Omega$ [sigma].

A failure detector is realistic when it cannot guess the future. In
[realistic], the authors prove that the perfect failure detector ($P$) is the
weakest realistic failure detector to solve consensus. Building upon this
result, Schiper and Pedone [SchiperP08] shows that $P$ is sufficient to
implement genuine atomic multicast. However, $P$ is the weakest only when
messages are addressed to all the processes in the system. The present paper
generalizes this result and the characterization given in [gamcast] (see Table
1). It establishes the weakest failure detector to solve genuine atomic
multicast for any set of destination groups.

##### Primer on the findings

Let $\mathcal{G}$ be all the destination groups and $\mathcal{F}$ be the
cyclic families in it, that is the subsets of $\mathcal{G}$ whose intersection
graph is hamiltonian. This paper shows that the weakest failure detector to
solve genuine atomic multicast is
$\mu=(\land_{g,h\in\mathcal{G}}\leavevmode\nobreak\ \Sigma_{g\cap
h})\land(\land_{g\in\mathcal{G}}\leavevmode\nobreak\ \Omega_{g})\land\gamma$,
where  $\Sigma_{P}$and $\Omega_{P}$ are the quorum and leader failure
detectors restricted to the processes in $P$, and  $\gamma$is a new failure
detector that informs the processes in a cyclic family
$\mathfrak{f}\in\mathcal{F}$ when $\mathfrak{f}$ is faulty. Our results
regarding $\gamma$ are established wrt. realistic failure detectors.
Genuiness Order Weakest $\times$ Global $\Omega\land\Sigma$ [omega, sigma]
$\surd$ $\cdot$ $\notin\mathcal{U}_{2}$ [gamcast] $\cdot$ $\cdot$ $\leq P$
[SchiperP08] $\cdot$ $\cdot$ $\mu$ §5, §4 $\cdot$ Strict
$\mu\land(\land_{g,h\in\mathcal{G}}\leavevmode\nobreak\ 1^{g\cap h})$
§LABEL:sect:variations:rt $\cdot$ Pairwise
$(\land_{g,h\in\mathcal{G}}\leavevmode\nobreak\ \Sigma_{g\cap
h})\land(\land_{g\in\mathcal{G}}\leavevmode\nobreak\ \Omega_{g})$
§LABEL:sect:discussion $\surd\surd$ Global if $\mathcal{F}=\varnothing$ then
$\mu\land(\land_{g,h\in\mathcal{G}}\leavevmode\nobreak\ \Omega_{g\cap h})$
§LABEL:sect:variations:strong else
$\geq\mu\land(\land_{g,h\in\mathcal{G}}\leavevmode\nobreak\ \Omega_{g\cap h})$
Table 1:  About the weakest failure detector for atomic multicast. _(
$\surd\surd$= strongly genuine ) _ This paper also studies two classical
variations of the atomic multicast problem. The strict variation requires that
message delivery follows the real-time order. In this case, we prove that
$\mu$ must be strengthen with $1^{g\cap h}$, the indicator failure detector
that informs each process in $g\cup h$ when $g\cap h$ is faulty. The strongly
genuine variation requires a message to be delivered when its destination
group runs in isolation. In that case, the weakest failure detector is at
least $\mu\land(\land_{g,h\in\mathcal{G}}\leavevmode\nobreak\ \Omega_{g\cap
h})$. This value is attained when $\mathcal{F}=\varnothing$.

##### Outline of the paper

§2 introduces the atomic multicast problem and the notion of genuineness. We
present the candidate failure detector in §3. §4 proves that this candidate is
sufficient. Its necessity is established in §5. §LABEL:sect:variations details
the results regarding the two variations of the problem. We cover related work
and discuss our results in §LABEL:sect:discussion. §LABEL:sect:conclusion
closes this paper. For clarity, some of our proofs are deferred to the
Appendix.

##  2 The Atomic Multicast Problem

###  2.1 System Model

In [CT96], the authors extend the usual model of asynchronous distributed
computation to include failure detectors. The present paper follows this model
with the simplifications introduced in [ever, commit]. This model is recalled
in Appendix LABEL:appendix:model.

###  2.2 Problem Definition

Atomic multicast is a group communication primitive that allows to disseminate
messages between processes. This primitive is used to build transactional
systems [granola, pstore] and partially-replicated (aka., sharded) data stores
[tempo, janus]. In what follows, we consider the most standard definition for
this problem [isis, Hadzilacos94amodular, survey]. In the parlance of
Hadzilacos and Toueg [Hadzilacos94amodular], it is named uniform global total
order multicast. Other variations are studied in §LABEL:sect:variations. Given
a set of messages $\mathcal{M}$, the interface of atomic multicast consists of
operations $\mathit{multicast}(m)$ and $\mathit{deliver}(m)$, with
$m\in\mathcal{M}$. Operation $\mathit{multicast}(m)$ allows a process to
_multicast_ a message $m$ to a set of processes denoted by $\mathit{dst}(m)$.
This set is named the _destination group_ of $m$. When a process executes
$\mathit{deliver}(m)$, it delivers message $m$, typically to an upper
applicative layer. Consider two messages $m$ and $m^{\prime}$ and some process
$p\in\mathit{dst}(m)\cap\mathit{dst}(m^{\prime})$. Relation $m\buildrel
p\over{\mapsto}m^{\prime}$ captures the local delivery order at process $p$.
This relation holds when, at the time $p$ delivers $m$, $p$ has not delivered
$m^{\prime}$. The union of the local delivery orders gives the _delivery
order_ , that is $\mapsto=\cup_{p\in\mathcal{P}}\buildrel p\over{\mapsto}$.
The runs of atomic multicast must satisfy: (_Integrity_) For every process $p$
and message $m$, $p$ delivers $m$ at most once, and only if $p$ belongs to
$\mathit{dst}(m)$ and $m$ was previously multicast. (_Termination_) For every
message $m$, if a correct process multicasts $m$, or a process delivers $m$,
eventually every correct process in $\mathit{dst}(m)$ delivers $m$.
(_Ordering_) The transitive closure of $\mapsto$ is a strict partial order
over $\mathcal{M}$. Integrity and termination are two common properties in
group communication literature. They respectively ensure that only sound
messages are delivered to the upper layer and that the communication primitive
makes progress. Ordering guarantees that the messages could have been received
by a sequential process. A common and equivalent rewriting of this property is
as follows: (_Ordering_) Relation $\mapsto$ is acyclic over $\mathcal{M}$. If
the sole destination group is $\mathcal{P}$, that is the set of all the
processes, the definition above is the one of atomic broadcast. In what
follows, $\mathcal{G}\subseteq 2^{\mathcal{P}}$ is the set of all the
destinations groups, i.e., $\mathcal{G}=\\{g:\exists m\in\mathcal{M}\ldotp
g=\mathit{dst}(m)\\}$. For some process $p$, $\mathcal{G}(p)$ denotes the
destination groups in $\mathcal{G}$ that contain $p$. Two groups $g$ and $h$
are _intersecting_ when $g\cap h\neq\varnothing$.

##### What can be sent and to who

The process that executes $\mathit{multicast}(m)$ is the sender of $m$,
denoted $\mathit{src}(m)$. As usual, we consider that processes disseminate
different messages (i.e., $\mathit{src}$ is a function). A message holds a
bounded payload $\mathit{payload}(m)$, and we assume that atomic multicast is
not payload-sensitive. This means that for every message $m$, and for every
possible payload $x$, there exists a message $m^{\prime}\in\mathcal{M}$ such
that $\mathit{payload}(m^{\prime})=x$,
$\mathit{dst}(m^{\prime})=\mathit{dst}(m)$ and
$\mathit{src}(m^{\prime})=\mathit{src}(m)$.

##### Dissemination model

In this paper, we consider a closed model of dissemination. This means that to
send a message to some group $g$, a process must belong to it (i.e.,
$\mathit{src}(m)\in\mathit{dst}(m)$). In addition, we do not restrict the
source of a message. This translates into the fact that for every message $m$,
for every process $p$ in $\mathit{dst}(m)$, there exists a message
$m^{\prime}$ with $\mathit{dst}(m)=\mathit{dst}(m^{\prime})$ and
$\mathit{src}(m^{\prime})=p$. Under the above set of assumptions, the atomic
multicast problem is fully determined by the destination groups $\mathcal{G}$.

###  2.3 Genuineness

At first glance, atomic multicast boils down to the atomic broadcast problem:
to disseminate a message it suffices to broadcast it, and upon reception only
messages addressed to the local machine are delivered. With this approach,
every process takes computational steps to deliver every message, including
the ones it is not concerned with. As a consequence, the protocol does not
scale [multiringpaxos, versus], even if the workload is embarrassingly
parallel (e.g., when the destinations groups are pairwise disjoint). Such a
strategy defeats the core purpose of atomic multicast and is thus not
satisfying from a performance perspective. To rule out this class of
solutions, Guerraoui and Schiper [gamcast] introduce the notion of _genuine_
atomic multicast. These protocols satisfy the minimality property defined
below. (_Minimality_) In every run $R$ of ${A}$, if some correct process $p$
sends or receives a (non-null) message in $R$, there exists a message $m$
multicast in $R$ with $p\in\mathit{dst}(m)$. All the results stated in this
paper concern genuine atomic multicast. To date, this is the most studied
variation for this problem (see, e.g., [ramcast, whitebox, fastcast]).

##  3 The Candidate Failure Detector

This paper characterizes the weakest failure detector to solve genuine atomic
multicast. Below, we introduce several notions related to failure detectors
then present our candidate.

##### Family of destination groups

A family of destination groups is a set of (non-repeated) destination groups
$\mathfrak{f}=(g_{i})_{i}$. For some family $\mathfrak{f}$,
$cpaths(\mathfrak{f})$ are the closed paths in the intersection graph of
$\mathfrak{f}$ visiting all its destination groups.111 The intersection graph
of a family of sets $(S_{i})_{i}$ is the undirected graph whose vertices are
the sets $S_{i}$, and such that there is an edge linking $S_{i}$ and $S_{j}$
iff $S_{i}\cap S_{j}\neq\varnothing$.  Family $\mathfrak{f}$ is _cyclic_ when
its intersection graph is hamiltonian, that is when $cpaths(\mathfrak{f})$ is
non-empty. A cyclic family $\mathfrak{f}$ is _faulty at time $t$_ when every
path $\pi\in cpaths(\mathfrak{f})$ visits an edge $(g,h)$ with $g\cap h$
faulty at $t$. In what follows, $\mathcal{F}$ denotes all the cyclic families
in $2^{\mathcal{G}}$. Given a destination group $g$, $\mathcal{F}(g)$ are the
cyclic families in $\mathcal{F}$ that contain $g$. For some process $p$,
$\mathcal{F}(p)$ are the cyclic families $\mathfrak{f}$ such that $p$ belongs
to some group intersection in $\mathfrak{f}$ (that is, $\exists
g,h\in\mathfrak{f}\ldotp p\in g\cap h$). To illustrate the above notions,
consider Figure 1. In this figure, $\mathcal{P}=\\{p_{1},\ldots,p_{5}\\}$ and
we have four destination groups:
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{g_{1}}}=\\{p_{1},p_{2}\\}$,
${\color[rgb]{.864,.08,.235}\definecolor[named]{pgfstrokecolor}{rgb}{.864,.08,.235}{g_{2}}}=\\{p_{2},p_{3}\\}$,
${\color[rgb]{0,0.6,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.6,0}\pgfsys@color@cmyk@stroke{0.64}{0}{0.95}{0.40}\pgfsys@color@cmyk@fill{0.64}{0}{0.95}{0.40}{g_{3}}}=\\{p_{1},p_{3},p_{4}\\}$
and
${\color[rgb]{.5,0,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,0,.5}{g_{4}}}=\\{p_{1},p_{4},p_{5}\\}$.
The intersection graphs of
$\mathfrak{f}=\\{{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{g_{1}}},{\color[rgb]{.864,.08,.235}\definecolor[named]{pgfstrokecolor}{rgb}{.864,.08,.235}{g_{2}}},{\color[rgb]{0,0.6,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.6,0}\pgfsys@color@cmyk@stroke{0.64}{0}{0.95}{0.40}\pgfsys@color<EMAIL_ADDRESS>and
$\mathfrak{f}^{\prime}=\\{{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{g_{1}}},{\color[rgb]{0,0.6,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.6,0}\pgfsys@color@cmyk@stroke{0.64}{0}{0.95}{0.40}\pgfsys@color@cmyk@fill{0.64}{0}{0.95}{0.40}{g_{3}}},{\color[rgb]{.5,0,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,0,.5}{g_{4}}}\\}$
are depicted respectively in Figures 1(b) and 1(c). These two families are
cyclic. This is also the case of
$\mathfrak{f}^{\prime\prime}=\mathcal{G}=\\{{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{g_{1}}},{\color[rgb]{.864,.08,.235}\definecolor[named]{pgfstrokecolor}{rgb}{.864,.08,.235}{g_{2}}},{\color[rgb]{0,0.6,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.6,0}\pgfsys@color@cmyk@stroke{0.64}{0}{0.95}{0.40}\pgfsys@color@cmyk@fill{0.64}{0}{0.95}{0.40}{g_{3}}},{\color[rgb]{.5,0,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,0,.5}{g_{4}}}\\}$
whose intersection graph is the union of the two intersection graphs of
$\mathfrak{f}$ and $\mathfrak{f}^{\prime}$. This family is faulty when
${\color[rgb]{.864,.08,.235}\definecolor[named]{pgfstrokecolor}{rgb}{.864,.08,.235}{g_{2}}}\cap{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{g_{1}}}=\\{p_{2}\\}$
fails. Group
${\color[rgb]{.864,.08,.235}\definecolor[named]{pgfstrokecolor}{rgb}{.864,.08,.235}{g_{2}}}$
belongs to two cyclic families, namely
$\mathcal{F}({\color[rgb]{.864,.08,.235}\definecolor[named]{pgfstrokecolor}{rgb}{.864,.08,.235}{g_{2}}})=\\{\mathfrak{f},\mathfrak{f}^{\prime\prime}\\}$.
Process $p_{1}$ belongs to all cyclic families, that is
$\mathcal{F}(p_{1})=\mathcal{F}$. Differently, since $p_{5}$ is part of no
group intersection, $\mathcal{F}(p_{5})=\varnothing$.

$p_{1}$$p_{2}$$p_{3}$$p_{4}$$p_{5}$ (a)

${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{g_{1}}}$${\color[rgb]{.864,.08,.235}\definecolor[named]{pgfstrokecolor}{rgb}{.864,.08,.235}{g_{2}}}$${\color[rgb]{0,0.6,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.6,0}\pgfsys@color@cmyk@stroke{0.64}{0}{0.95}{0.40}\pgfsys@color<EMAIL_ADDRESS>(b)

${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{g_{1}}}$${\color[rgb]{0,0.6,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.6,0}\pgfsys@color@cmyk@stroke{0.64}{0}{0.95}{0.40}\pgfsys@color@cmyk@fill{0.64}{0}{0.95}{0.40}{g_{3}}}$${\color[rgb]{.5,0,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,0,.5}{g_{4}}}$$\\{p_{1}\\}$$\\{p_{1}\\}$$\\{p_{1},p_{4}\\}$
(c)

Figure 1:  From left to right: the four groups
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{g_{1}}}$,
${\color[rgb]{.864,.08,.235}\definecolor[named]{pgfstrokecolor}{rgb}{.864,.08,.235}{g_{2}}}$,
${\color[rgb]{0,0.6,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.6,0}\pgfsys@color@cmyk@stroke{0.64}{0}{0.95}{0.40}\pgfsys@color<EMAIL_ADDRESS>and
${\color[rgb]{.5,0,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,0,.5}{g_{4}}}$,
and the intersection graphs of the two cyclic families
$\mathfrak{f}=\\{{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{g_{1}}},{\color[rgb]{.864,.08,.235}\definecolor[named]{pgfstrokecolor}{rgb}{.864,.08,.235}{g_{2}}},{\color[rgb]{0,0.6,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.6,0}\pgfsys@color@cmyk@stroke{0.64}{0}{0.95}{0.40}\pgfsys@color<EMAIL_ADDRESS>and
$\mathfrak{f}^{\prime}=\\{{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{g_{1}}},{\color[rgb]{0,0.6,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.6,0}\pgfsys@color@cmyk@stroke{0.64}{0}{0.95}{0.40}\pgfsys@color@cmyk@fill{0.64}{0}{0.95}{0.40}{g_{3}}},{\color[rgb]{.5,0,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,0,.5}{g_{4}}}\\}$.

##### Failure detectors of interest

Failure detectors are grouped into classes of equivalence that share common
computational power. Several classes of failure detectors have been proposed
in the past. This paper makes use of two common classes of failure detectors,
$\Sigma$ and $\Omega$, respectively introduced in [sigma] and [omega]. We also
propose a new class $\gamma$ named the _cyclicity failure detector_. All these
classes are detailed below. • The quorum failure detector ($\Sigma$) captures
the minimal amount of synchrony to implement an atomic register. When a
process $p$ queries at time $t$ a detector of this class, it returns a non-
empty subset of processes $\Sigma(p,t)\subseteq\mathcal{P}$ such that:
(_Intersection_) $\forall p,q\in\mathcal{P}\ldotp\forall
t,t^{\prime}\in\mathbb{N}\ldotp\Sigma(p,t)\cap\Sigma(q,t^{\prime})\neq\varnothing$
(_Liveness_) $\forall
p\in\mathit{Correct}\ldotp\exists\tau\in\mathbb{N}\ldotp\forall
t\geq\tau\ldotp\Sigma(p,t)\subseteq\mathit{Correct}$ The first property states
that the values of any two quorums taken at any times intersect. It is used to
maintain the consistency of the atomic register. The second property ensures
that eventually only correct processes are returned. • Failure detector
$\Omega$ returns an eventually reliable leader [eventualconsistency]. In
detail, it returns a value $\Omega(p,t)\in\mathcal{P}$ satisfying that:
(_Leadership_) $\mathit{Correct}\neq\varnothing\Rightarrow(\exists
l\in\mathit{Correct}\ldotp\forall
p\in\mathit{Correct}\ldotp\exists\tau\in\mathbb{N}\ldotp\forall
t\geq\tau\ldotp\Omega(p,t)=l)$ $\Omega$ is the weakest failure detector to
solve consensus when processes have access to a shared memory. For message-
passing distributed systems, $\Omega\land\Sigma$ is the weakest failure
detector. • The cyclicity failure detector ($\gamma$) informs each process of
the cyclic families it is currently involved with. In detail, failure detector
$\gamma$ returns at each process $p$ a set of cyclic families
$\mathfrak{f}\in\mathcal{F}(p)$ such that: (_Accuracy_) $\forall
p\in\mathcal{P}\ldotp\forall
t\in\mathbb{N}\ldotp(\mathfrak{f}\in\mathcal{F}(p)\land\mathfrak{f}\notin\gamma(p,t))\Rightarrow\mathfrak{f}\leavevmode\nobreak\
\text{faulty at }t$ (_Completeness_) $\forall
p\in\mathit{Correct}\ldotp\forall
t\in\mathbb{N}\ldotp(\mathfrak{f}\in\mathcal{F}(p)\land\mathfrak{f}\leavevmode\nobreak\
\text{faulty at }t)\Rightarrow\exists\tau\in\mathbb{N}\ldotp\forall
t^{\prime}\geq\tau\ldotp\mathfrak{f}\notin\gamma(p,t^{\prime})$ Accuracy
ensures that if some cyclic family $\mathfrak{f}$ is not output at $p$ and $p$
belongs to it, then $\mathfrak{f}$ is faulty at that time. Completeness
requires that eventually $\gamma$ does not output forever a faulty family at
the correct processes that are part of it. Hereafter, $\gamma(g)$ denotes the
groups $h$ such that $g\cap h\neq\varnothing$ and $g$ and $h$ belong to a
cyclic family output by $\gamma$. To illustrate the above definitions, we may
consider again the system depicted in Figure 1. Let us assume that
$\mathit{Correct}=\\{p_{1},p_{4},p_{5}\\}$. The quorum failure detector
$\Sigma$ can return
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{g_{1}}}$
or
${\color[rgb]{0,0.6,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.6,0}\pgfsys@color@cmyk@stroke{0.64}{0}{0.95}{0.40}\pgfsys@color<EMAIL_ADDRESS>then
${\color[rgb]{.5,0,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,0,.5}{g_{4}}}$
forever. Failure detector $\Omega$ may output any process, then at some point
in time, one of the correct processes (e.g., $p_{1}$) ought to be elected
forever. At processes $p_{1}$, $\gamma$ returns initially
$\\{\mathfrak{f},\mathfrak{f}^{\prime},\mathfrak{f}^{\prime\prime}\\}$. Then,
once families $\mathfrak{f}$ and $\mathfrak{f}^{\prime\prime}$ are faulty—this
should happen as $p_{2}$ is faulty—the output eventually stabilizes to
$\\{\mathfrak{f}^{\prime}\\}$. When this happens,
$\gamma({\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{g_{1}}})=\\{{\color[rgb]{0,0.6,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.6,0}\pgfsys@color@cmyk@stroke{0.64}{0}{0.95}{0.40}\pgfsys@color@cmyk@fill{0.64}{0}{0.95}{0.40}{g_{3}}},{\color[rgb]{.5,0,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,0,.5}{g_{4}}}\\}$.

##### Conjunction of failure detectors

We write $C\land D$ the conjunction of the failure detectors $C$ and $D$
[ever]. For a failure pattern $F$, failure detector $C\land D$ returns a
history in $D(F)\times C(F)$.

##### Set-restricted failure detectors

For some failure detector $D$, $D_{P}$ is the failure detector obtained by
restricting $D$ to the processes in $P\subseteq\mathcal{P}$. This failure
detector behaves as $D$ for the processes $p\in P$, and it returns $\bot$ at
$p\notin P$. In detail, let $F\cap P$ be the failure pattern $F$ obtained from
$F$ by removing the processes outside $P$, i.e., $(F\cap P)(t)=F(t)\cap P$.
Then, $D_{P}(F)$ equals $D(F\cap P)$ at $p\in P$, and the mapping
$p\times\mathbb{N}\rightarrow\bot$ elsewhere. To illustrate this definition,
$\Omega_{\\{p\\}}$ is the trivial failure detector that returns $p$ at process
$p$. Another example is given by $\Sigma_{\\{p_{1},p_{2}\\}}$ which behaves as
$\Sigma$ over $\mathcal{P}=\\{p_{1},p_{2}\\}$.

##### The candidate

Our candidate failure detector is
$\mu_{\mathcal{G}}=(\land_{g,h\in\mathcal{G}}\leavevmode\nobreak\
\Sigma_{g\cap h})\land(\land_{g\in\mathcal{G}}\leavevmode\nobreak\
\Omega_{g})\land\gamma$. When the set of destinations groups $\mathcal{G}$ is
clear from the context, we shall omit the subscript.

##  4 Sufficiency

This section shows that genuine atomic multicast is solvable with the
candidate failure detector. A first observation toward this result is that
consensus is wait-free solvable in $g$ using $\Sigma_{g}\land\Omega_{g}$.
Indeed, $\Sigma_{g}$ permits to build shared atomic registers in $g$ [sigma].
From these registers, we may construct an obstruction-free consensus and boost
it with $\Omega_{g}$ [alpha]. Thus, any linearizable wait-free shared objects
is implementable in $g$ [syn:1382]. Leveraging these observations, this
section depicts a solution built atop (high-level) shared objects. Below, we
first introduce group sequential atomic multicast (§4.1). From a computability
perspective, this simpler variation is equivalent to the common atomic
multicast problem. This is the variation that we shall implement hereafter. We
then explain at coarse grain how to solve genuine atomic multicast in a fault-
tolerant manner using failure detector $\mu$ (§4.2). Further, the details of
our solution are presented (§4.3) and its correctness established (§4.4).

###  4.1 A simpler variation

Group sequential atomic multicast requires that each group handles its
messages sequentially. In detail, given two messages $m$ and $m^{\prime}$
addressed to the same group, we write $m\prec m^{\prime}$ when
$\mathit{src}(m^{\prime})$ delivers $m$ before it multicasts $m^{\prime}$.
This variation requires that if $m$ and $m^{\prime}$ are multicast to the same
group, then $m\prec m^{\prime}$, or the converse, holds. Proposition 4.1 below
establishes that this variation is as difficult as (vanilla) atomic multicast.
Building upon this insight, this section depicts a solution to group
sequential atomic multicast using failure detector $\mu$.

######  Proposition 4.1.

Group sequential atomic multicast is equivalent to atomic multicast.

######  Proof 4.2.

Clearly, a group sequential algorithm implements (vanilla) atomic multicast.
For the converse direction, we proceed as detailed below. The reduction
algorithm uses an instance of a solution to the base problem. For each group
$g$, the algorithm also maintains a list $L_{g}$, shared among all the members
of $g$. This list is implemented using an instance of atomic multicast running
only between the members of $g$. In addition, each process stores a mapping
indicating whether a message $m$ is delivered locally or not. Initially, every
message is not delivered. The first time triggers, a process $p$ marks $m$ as
delivered and executes the upcall to deliver $m$. To multicast a message $m$,
a process $p$ first adds $m$ to the list $L_{g}$. Then $p$ waits that every
message prior to $m$ in $L_{g}$ is delivered, helping if necessary. To help
delivering some message $m^{\prime}$, $p$ executes . When all the messages
before $m$ in $L_{g}$ are delivered locally, $p$ calls . Then process $p$
returns from its invocation to $\mathit{multicast}(m)$ in the group sequential
algorithm.

###  4.2 Overview of the solution

First of all, we observe that if the groups are pairwise disjoint, it suffices
that each group orders the messages it received to solve atomic multicast. To
this end, we use a shared log ${\text{{LOG}}}_{g}$ per group $g$. Then,
consider that the intersection graph of $\mathcal{G}$ is acyclic, i.e.,
$\mathcal{F}$ is empty, yet groups may intersect. In that case, it suffices to
add a deterministic merge procedure in each group intersection, for instance,
using a set of logs ${\text{{LOG}}}_{g\cap h}$ when $g\cap h\neq\varnothing$.
Now, to solve the general case, cycles in the order built with the shared logs
must be taken into account. To this end, we use a fault-tolerant variation of
Skeen’s solution [Birman:1987, Guerraoui:97]: in each log, the message is
bumped to the highest initial position it occupies in all the logs. In the
original algorithm [Birman:1987], as in many other approaches (e.g.,
[whitebox, fastcast]), such a procedure is failure-free, and processes simply
agree on the final position (aka., timestamp) of the message in the logs. In
contrast, our algorithm allows a disagreement when the cyclic family becomes
faulty. This disagreement is however restricted to different logs, as in the
acyclic case.

###  4.3 Algorithm

Algorithm 1 Solving atomic multicast with failure detector $\mu$ – code at
process $p$ 1:variables: 2: $({\text{{LOG}}}_{h\cap
h^{\prime}})_{h,h^{\prime}\in\mathcal{G}(p)}$ 3:
$({\text{{CONS}}}_{m,\mathfrak{f}})_{m\in\mathcal{M},\mathfrak{f}\subseteq\mathcal{G}}$
4: ${\text{{phase}}}[m]\leftarrow\lambda m.\text{{start}}$
5:$\mathit{multicast}(m)$ := // $g=dst(m)\land g\in\mathcal{G}(p)$ 6: pre:
${\text{{phase}}}[m]=\text{{start}}$ 7: eff:
${\text{{LOG}}}_{g}.\mathit{append}(m)$ 8:$\mathit{pending}(m)$ :=  9: pre:
${\text{{phase}}}[m]=\text{{start}}$ 10: $m\in{\text{{LOG}}}_{g}$ 11: $\forall
m^{\prime}<_{{\text{{LOG}}}_{g}}m\ldotp{\text{{phase}}}[m^{\prime}]\geq\text{{commit}}$
12: eff: for all $h\in\mathcal{G}(p)$ do 13: $i\leftarrow{\text{{LOG}}}_{g\cap
h}.\mathit{append}(m)$ 14: ${\text{{LOG}}}_{g}.\mathit{append}(m,h,i)$ 15:
${\text{{phase}}}[m]\leftarrow\text{{pending}}$ 16:$\mathit{commit}(m)$ :=
17: pre: ${\text{{phase}}}[m]=\text{{pending}}$ 18: $\forall
h\in\gamma(g)\ldotp(m,h,\mathrel{-})\in{\text{{LOG}}}_{g}$ 19: eff:
$\text{{let}}\leavevmode\nobreak\
k=\max\\{i:\exists(m,\mathrel{-},i)\in{\text{{LOG}}}_{g}\\},$ 20:
$\text{{let}}\leavevmode\nobreak\
\mathfrak{f}=\\{h:\exists\mathfrak{f}^{\prime}\in\mathcal{F}(p)\ldotp
g,h\in\mathfrak{f}^{\prime}\land g\cap h\neq\varnothing\\}$ 21:
$k\leftarrow{\text{{CONS}}}_{m,\mathfrak{f}}.\mathit{propose}(k)$ 22: for all
$h\in\mathcal{G}(p)$ do 23: ${\text{{LOG}}}_{g\cap
h}.\mathit{bumpAndLock}(m,k)$ 24:
${\text{{phase}}}[m]\leftarrow\text{{commit}}$ 25:$\mathit{stabilize}(m,h)$ :=
26: pre: ${\text{{phase}}}[m]=\text{{commit}}$ 27: $h\in\mathcal{G}(p)$ 28:
$\forall m^{\prime}<_{{\text{{LOG}}}_{g\cap
h}}m\ldotp{\text{{phase}}}[m^{\prime}]\geq\text{{stable}}$ 29: eff:
${\text{{LOG}}}_{g}.\mathit{append}(m,h)$ 30:$\mathit{stable}(m)$ :=  31: pre:
${\text{{phase}}}[m]=\text{{commit}}$ 32: $\forall
h\in\gamma(g)\ldotp(m,h)\in{\text{{LOG}}}_{g}$ 33: eff:
${\text{{phase}}}[m]\leftarrow\text{{stable}}$ 34:$\mathit{deliver}(m)$ :=
35: pre: ${\text{{phase}}}[m]=\text{{stable}}$ 36: $\forall
m^{\prime}<_{{\text{{LOG}}}_{g\cap
h}}m\ldotp{\text{{phase}}}[m^{\prime}]=\text{{deliver}}$ 37: eff:
${\text{{phase}}}[m]\leftarrow\text{{deliver}}$ Algorithm 1 depicts a solution
to (group sequential) genuine atomic multicast using failure detector $\mu$.
To the best of our knowledge, this is only algorithm with [SchiperP08] that
tolerates arbitrary failures. Algorithm 1 is composed of a set of actions. An
action is executable once its preconditions (pre:) are true. The effects
(eff:) of an action are applied sequentially until it returns. Algorithm 1
uses a log per group and per group intersection. Logs are linearizable, long-
lived and wait-free. Their sequential interface is detailed below.

##### Logs

A _log_ is an infinite array of slots. Slots are numbered from $1$. Each slot
contains one or more data items. A datum $d$ is at position $k$ when slot $k$
contains it. This position is obtained through a call to $\mathit{pos}(d)$;
$0$ is returned if $d$ is absent. A slot $k$ is _free_ when it contains no
data item. In the initial state, every slot is free. The head of the log
points to the first free slot after which there are only free slots
(initially, slot $1$). Operation $\mathit{append}(d)$ inserts datum $d$ at the
slot pointed by the head of the log then returns its position. If $d$ is
already in the log, this operation does nothing. When $d$ is in the log, it
can be locked with operation $\mathit{bumpAndLock}(d,k)$. This operation moves
$d$ from its current slot $l$ to slot $\max(k,l)$, then locks it. Once locked,
a datum cannot be bumped anymore. Operation $\mathit{locked}(d)$ indicates if
$d$ is locked in the log. We write $d\in L$ when datum $d$ is at some position
in the log $L$. A log implies an ordering on the data items it contains. When
$d$ and $d^{\prime}$ both appear in $L$, $d<_{L}d^{\prime}$ is true when the
position of $d$ is lower than the position of $d^{\prime}$, or they both
occupy the same slot and $d<d^{\prime}$, for some a priori total order ($<$)
over the data items.

##### Variables

Algorithm 1 employs two types of shared objects at a process. First, for any
two groups $h$ and $h^{\prime}$ to which the local process belongs, Algorithm
1 uses a log ${\text{{LOG}}}_{h\cap h^{\prime}}$ (line 2). Notice that, when
$h=h^{\prime}$, the log coincides with the log of the destination group $h$,
i.e., ${\text{{LOG}}}_{h}$. Second, to agree on the final position of a
message, Algorithm 1 also employs consensus objects (line 3). Consensus
objects are both indexed by messages and group families. Given some message
$m$ and appropriate family $\mathfrak{f}$, Algorithm 1 calls
${\text{{CONS}}}_{m,\mathfrak{f}}$ (lines 20 and 21). Two processes call the
same consensus object at line 21 only if both parameters match. Finally, to
store the status of messages addressed to the local process, Algorithm 1 also
employs a mapping phase (line 4). A message is initially in the start phase,
then it moves to pending (line 15), commit (line 24), stable (line 33) and
finally the deliver (line 37) phase. Phases are ordered according to this
progression.

##### Algorithmic details

We now detail Algorithm 1 and jointly argue about its correctness. For
clarity, our argumentation is informal—the full proof appears in §4.4. To
multicast some message $m$ to $g=\mathit{dst}(m)$, a process adds $m$ to the
log of its destination group (line 7). When $p\in g$ observes $m$ in the log,
$p$ appends $m$ to each ${\text{{LOG}}}_{g\cap h}$ with $p\in g\cap h$ (line
13). Then, $p$ stores in the log of the destination group of $m$ the slot
occupied by $m$ in ${\text{{LOG}}}_{g\cap h}$ (line 14). This moves $m$ to the
pending phase. Similarly to Skeen’s algorithm [Birman:1987], a message is then
bumped to the highest slot it occupies in the logs. This step is executed at
lines 16-24. In detail, $p$ first agree with its peers on the highest position
$k$ occupied by $m$ (lines 19-21). Observe here that only the processes in $g$
that share some cyclic family with $p$ take part to this agreement (line 20).
Then, for each group $h$ in $\mathcal{G}(p)$, $p$ bumps $m$ to slot $k$ in
${\text{{LOG}}}_{g\cap h}$ and locks it in this position (line 23). This moves
$m$ to the commit phase. The next steps of Algorithm 1 compute the
predecessors of message $m$. With more details, once $m$ reaches the stable
phase and is ready to be delivered, the messages that precede it in the logs
at process $p$ cannot change anymore. In §4.4, this invariant is proved in
Lemma 4.8. If $g$ does not belong to any cyclic family, stabilizing $m$ is
immediate: the precondition at line 32 is always vacuously true. In this case,
$m$ is delivered in an order consistent with the order it is added to the logs
(line 28). This comes from the fact that when $\mathcal{F}=\varnothing$
ordering the messages reduces to a pairwise agreement between the processes.
Lemma 4.12 establish this second invariant in §4.4. When
$\mathcal{F}\neq\varnothing$, stabilizing $m$ is a bit more involved. Indeed,
messages can be initially in cyclic positions, e.g.,
$C=m_{1}<_{{\text{{LOG}}}_{g_{1}\cap g_{2}}}m_{2}<_{{\text{{LOG}}}_{g_{2}\cap
g_{3}}}m_{3}<_{{\text{{LOG}}}_{g_{3}\cap g_{1}}}m_{1}$, preventing them to be
delivered. As in [Birman:1987], bumping messages helps to resolve such a
situation. The bumping procedure is executed globally. A process must wait
that the positions in the logs of a message are cycle-free before declaring it
stable. Waiting can cease when the cyclic family is faulty (line 32). This is
correct because messages are stabilized in the order of their positions in the
logs (lines 25-29). Hence, if a cycle $C$ exists initially in the positions,
either  1. not all the messages in $C$ are delivered, or  2. the first message
to get stable in $C$ has no predecessors in $C$ in the logs.  In other words,
for any two messages $m$ and $m^{\prime}$ in $C$, if $m\mapsto m^{\prime}$
then $m$ is stable before $m^{\prime}$. In §4.4, Lemma 4.18 proves this third
invariant. A process indicates that message $m$ with $g=\mathit{dst}(m)$ is
stabilized in group $h$ with a pair $(m,h)$ in ${\text{{LOG}}}_{g}$ (line 29).
When this holds for all the groups $h$ intersecting with $g$ such that there
exists a correct family $\mathfrak{f}$ with $f\in\mathcal{F}(p)$ and
$g,h\in\mathfrak{f}$, $m$ is declared stable at $p$ (line 32). Once stable, a
message $m$ can be delivered (lines 34-37). Algorithm 1 stabilizes then
delivers messages according to their positions in the logs. To maintain
progress, these positions must remain acyclic at every correct process.
Furthermore, this should also happen globally when a cyclic family is correct.
Both properties are ensured by the calls to consensus objects (line 21). In
§4.4, Lemmas 4.35 and 4.40 establish that these two properties hold.

##### Implementing the shared objects

In each group $g$, consensus is solvable since $\mu$ provides
$\Sigma_{g}\land\Omega_{g}$. This serves to implement all the objects
$({\text{{CONS}}}_{m,\mathfrak{f}})_{m,\mathfrak{f}}$ when
$\mathit{dst}(m)=g$. Logs that are specific to a group, namely
$({\text{{LOG}}}_{g})_{g\in\mathcal{G}}$, are also built atop consensus in $g$
using a universal construction [syn:1382]. Failure detector $\mu$ does not
offer the means to solve consensus in $g\cap h$. Hence we must rely on either
$g$ or $h$ to build ${\text{{LOG}}}_{g\cap h}$. Minimality requires processes
in a destination group to take steps only in the case a message is addressed
to them. To achieve this, we have to slightly modify the universal
construction for ${\text{{LOG}}}_{g\cap h}$, as detailed next. First, we
consider that this construction relies on an unbounded list of consensus
objects.222 In the failure detector model, computability results can use any
amount of shared objects.  Each consensus object in this list is contention-
free fast [AttiyaGK05]. This means that it is guarded by an adopt-commit
object (AC) [Gafni98] before an actual consensus object CONS is called. Upon
calling $\mathit{propose}$, AC is first used and if it fails, that is “adopt”
is returned, CONS is called. Adopt-commit objects are implemented using
$\Sigma_{g\cap h}$, while consensus objects are implemented atop some group,
say $g$, using $\Sigma_{g}\land\Omega_{g}$. This modification ensures that
when processes execute operations in the exact same order, only the adopt-
commit objects are called. As a consequence, when no message is addressed to
either $g$ or $h$ during a run, only the processes in $g\cap h$ executes steps
to implement an operation of ${\text{{LOG}}}_{g\cap h}$. In §4.4, Proposition
4.51 establishes this result.

###  4.4 Correctness of Algorithm 1

In what follows, we prove that Algorithm 1 is a genuine implementation of
group sequential atomic multicast. To establish this result, we proves a
series of statement on the runs of Algorithm 1. When considering such a run,
as all the shared objects used in Algorithm 1 are linearizable, we reason
directly upon the linearization.

##### Additional notations & definitions

Consider some run of Algorithm 1. We note $\mathit{del}(m)$ when $m$ is
delivered at some process and $\mathit{del}_{p}(m)$ when $p$ has delivered
$m$. G and F are respectively the “always” and “eventually” modal operators of
temporal logic. For some variable $x$, ${x}^{p,t}$ denotes to the value of $x$
at time $t$ on process $p$. If $x$ is shared, we shall omit the name of the
process. When $t=\infty$, we refer to the value of $x$ at the end of the run.
We write $\text{{stable}}^{p,t}$ the stable messages at time $t$ at process
$p$, that is
$\text{{stable}}^{p,t}\triangleq\\{m:{\text{{phase}}}^{p,t}[m]=\text{{stable}}\\}$.
For each phase
$\phi\in\\{\text{{start}},\text{{pending}},\text{{commit}},\text{{deliver}}\\}$,
the set $\phi^{p,t}$ is defined similarly. $\phi^{t}$ are all the messages in
phase $\phi$ across the system, i.e., $\phi^{t}\triangleq\cup_{p}\phi^{p,t}$.

####  4.4.1 Trivias

About logs.

######  Claim 1.

$\textbf{G}(d\in L\Rightarrow\textbf{G}(d\in L))$

######  Claim 2.

$\textbf{G}(L.\mathit{pos}(d)=k\Rightarrow\textbf{G}(L.\mathit{pos}(d)\geq
k))$

######  Claim 3.

$\textbf{G}(L.\mathit{locked}(d)\Rightarrow\textbf{G}(L.\mathit{locked}(d)))$

######  Claim 4.

$\textbf{G}((L.\mathit{locked}(d)\land
L.\mathit{pos}(d)=k)\Rightarrow\textbf{G}(L.\mathit{pos}(d)=k))$

######  Claim 5.

$\textbf{G}(L.\mathit{locked}(d)\land
d<_{L}d^{\prime}\Rightarrow\textbf{G}(d<_{L}d^{\prime}))$

######  Claim 6.

$\textbf{G}((L.\mathit{locked}(d^{\prime})\land d\notin L\land\textbf{F}(d\in
L))\Rightarrow\textbf{G}(d\in L\Rightarrow d^{\prime}<_{L}d))$

######  Claim 7.

$\textbf{G}(L.\mathit{locked}(d)\land\textbf{F}(d^{\prime}<_{L}d)\Rightarrow
d^{\prime}<_{L}d)$

Others.

######  Claim 8.

$(\mathit{dst}(m)\cap\mathit{dst}(m^{\prime})\neq\varnothing\land\mathit{del}(m)\land\mathit{del}(m^{\prime}))\Rightarrow
m^{\prime}\mapsto m\lor m\mapsto m^{\prime}$

######  Claim 9.

$\textbf{G}(m\in{\text{{LOG}}}_{g\cap
h}\Rightarrow\mathit{dst}(m)=g\lor\mathit{dst}(m)=h)$

######  Claim 10.

$\textbf{G}(m^{\prime}<_{{\text{{LOG}}}_{x}}m\Rightarrow
x=\mathit{dst}(m)\cap\mathit{dst}(m^{\prime}))$

######  Claim 11.

$\mathit{del}_{p}(m)\Rightarrow p\in\mathit{dst}(m)$

######  Claim 12.

$\mathit{del}(m)\Rightarrow m\in{\text{{LOG}}}_{\mathit{dst}(m)}^{\infty}$

######  Claim 13.

${\text{{phase}}}^{p,t_{0}}[m]\leavevmode\nobreak\ =\leavevmode\nobreak\
\text{{deliver}}\Rightarrow{\text{{phase}}}^{p,t_{1}<t_{0}}[m]=\text{{stable}}\Rightarrow{\text{{phase}}}^{p,t_{2}<t_{1}}[m]=\text{{commit}}\Rightarrow{\text{{phase}}}^{p,t_{3}<t_{2}}[m]=\text{{pending}}\Rightarrow{\text{{phase}}}^{p,t_{4}<t_{3}}[m]=\text{{start}}$

######  Claim 14.

$\textbf{G}({\text{{phase}}}^{p}[m]=\phi\Rightarrow\textbf{G}({\text{{phase}}}^{p}[m]\geq\phi))$

Table 2:  Base invariants in Algorithm 1.  Table 2 lists some base invariants
that follow immediately from the specification of a log and the structure of
Algorithm 1.

####  4.4.2 Ordering

First, we establish that Algorithm 1 maintains the ordering property of the
group communication primitive. Formally,

######  Proposition 4.3.

In every run of Algorithm 1, relation $\mapsto$ is acyclic over $\mathcal{M}$.
The proof goes by contradiction. Let $C=m_{1}\mapsto m_{2}\mapsto\ldots
m_{\lvert C\rvert}\mapsto m_{1}$ be a cycle in $\mapsto$ that does not contain
any sub-cycle. By definition of relation $\mapsto$, for each message
$m_{i\in[1,\lvert C\rvert]}$, there exists a process $p_{i}$ that delivers
$m_{i}$ before $m_{i+1}$. We shall note $\mathfrak{f}=(g_{i})_{i}$ the family
of the destination groups of $(m_{i})_{i}$. Below, we prove some key
invariants regarding the way Algorithm 1 delivers a message $m\in C$ with
$g=\mathit{dst}(m)$.

######  Lemma 4.4.

${\text{{phase}}}^{p,t}[m]\geq\text{{commit}}\Rightarrow\forall
h\in\mathcal{G}(p)\ldotp{\text{{LOG}}}_{g\cap h}^{t}.\mathit{locked}(m)$

######  Proof 4.5.

By Claim 13, if $m$ is deliver, it must be first stable. Similarly, to be
stable, message $m$ must be first commit. Process $p$ commits message $m$ at
line 24. Let it be at some time $t^{\prime}\leq t$. Process $p$ executes lines
22 and 23 before time $t^{\prime}$. Thus, $m$ is bumped and locked in each
${\text{{LOG}}}_{g\cap h}$ with $h\in\mathcal{G}(p)$. For each such group $h$,
applying Claim 3, ${\text{{LOG}}}_{g\cap h}^{t}.\mathit{locked}(m)$. Let
$m^{\prime}$ be a message with $h=\mathit{dst}(m^{\prime})$.

######  Lemma 4.6.

$(m\buildrel p\over{\mapsto}m^{\prime})\Rightarrow\neg\leavevmode\nobreak\
(m^{\prime}\buildrel p\over{\mapsto}m)$

######  Proof 4.7.

To get delivered, a message must first reach the deliver phase (line 37). Each
action is guarded by a precondition on the phase of the message—precisely at
line 9, 17, 26, 31 and 35. It follows that the deliver phase is terminal.
Consequently, a message is delivered at most once. Thus $m\neq m^{\prime}$.
Assume $m\buildrel p\over{\mapsto}m^{\prime}$. Thus, process $p$ delivers $m$
and either this occurs before $p$ delivers $m^{\prime}$ or $p$ never delivers
$m^{\prime}$. In both cases, $\neg\leavevmode\nobreak\ (m^{\prime}\buildrel
p\over{\mapsto}m)$.

######  Lemma 4.8.

$m\buildrel p\over{\mapsto}m^{\prime}\Rightarrow(m<_{{\text{{LOG}}}_{g\cap
h}^{\infty}}m^{\prime}\lor m^{\prime}\notin{\text{{LOG}}}_{g\cap h}^{\infty})$

######  Proof 4.9.

(By contradiction.) As $m\buildrel p\over{\mapsto}m^{\prime}$, by Claim 11,
$p\in g$. Then, applying the definition of relation $\mapsto$, $p\in h$.
Process $p$ delivers $m$ at line 37. Let $t$ be the time at which this
happens. According to the precondition at line 35, message $m$ was stable at
$p$ before. Thus, applying Lemma 4.4, ${\text{{LOG}}}_{g\cap
h}^{t}.\mathit{locked}(m)$. By our contradiction hypothesis,
$m^{\prime}<_{{\text{{LOG}}}_{g\cap h}^{\infty}}m$. Hence,
${\text{{LOG}}}_{g\cap
h}^{p,t}.\mathit{locked}(m)\land\textbf{F}(m^{\prime}<_{{\text{{LOG}}}_{g\cap
h}}m)$. By Claim 7, $m^{\prime}<_{{\text{{LOG}}}_{g\cap h}^{p,t}}m$. The
precondition at line 36 requires that
${\text{{phase}}}^{p,t}[m^{\prime}]=\text{{deliver}}$. Thus, $m^{\prime}$ was
delivered before. Applying Lemma 4.6, $\neg(m\buildrel
p\over{\mapsto}m^{\prime})$.

######  Lemma 4.10.

$(m\buildrel p\over{\mapsto}m^{\prime})\Rightarrow\neg(m^{\prime}\buildrel
q\over{\mapsto}m)$

######  Proof 4.11.

(By contradiction) Messages $m$ and $m^{\prime}$ are delivered by respectively
$p$ and $q$. From Lemma 4.4, $m\in{\text{{LOG}}}_{g\cap h}^{\infty}$ and
$m^{\prime}\in{\text{{LOG}}}_{g\cap h}^{\infty}$. Hence, by Lemma 4.8,
$m<_{{\text{{LOG}}}_{g\cap h}^{\infty}}m^{\prime}$ and
$m^{\prime}<_{{\text{{LOG}}}_{g\cap h}^{\infty}}m$.

######  Lemma 4.12.

$f\notin\mathcal{F}\Rightarrow\lvert C\rvert\in{1,2}$

######  Proof 4.13.

(By contradiction.) As $\lvert C\rvert\geq 3$, we have $C=m_{1}\buildrel
p_{1}\over{\mapsto}m_{2}\buildrel p_{2}\over{\mapsto}m_{3}\ldots$. Consider
that all the destination groups are pair-wise distinct. Then
$\pi=g_{1}g_{2}{\ldots}g_{\lvert C\rvert\geq 3}g_{1}$ is a closed path in the
intersection graph of $\mathfrak{f}$ visiting all the destination groups. A
contradiction to $\mathfrak{f}\notin\mathcal{F}$. Without lack of generality
assume that $g_{1}=g_{2\leq k\leq\lvert C\rvert}$. Since process $p_{1}$
delivers $m_{1}$, either $m_{1}\buildrel p_{1}\over{\mapsto}m_{k}$ or the
converse holds. (Case $m_{1}\buildrel p_{1}\over{\mapsto}m_{k}$) Then
$m_{1}\buildrel p_{1}\over{\mapsto}m_{k}\buildrel p_{k+1}\over{\mapsto}\ldots
m_{\lvert C\rvert}\buildrel p_{\lvert C\rvert}\over{\mapsto}m_{1}$ is a sub-
cycle of $C$. (Otherwise) Applying Lemma 4.10, $m_{k}\buildrel
p_{k}\over{\mapsto}m_{1}\buildrel p_{1}\over{\mapsto}\ldots m_{k-1}\buildrel
p_{k-1}\over{\mapsto}m_{k}$ is a sub-cycle of $C$.

##### (Case $\mathfrak{f}\notin\mathcal{F}$.)

Lemma 4.12 establishes that, as $C$ does not contain any sub-cycle, its size
must be either $1$ or $2$. $\lvert C\rvert=1$ is forbidden by Lemma 4.6. Lemma
4.10 prevents $\lvert C\rvert=2$.

##### (Otherwise.)

Clearly, there exists some time $t_{0}>0$ until which family
$\mathfrak{f}\in\mathcal{F}$ is correct. Let $m\in C$ be a message and
$g=\mathit{dst}(m)$ be its destination group. Assume that $m$ is stable at
some process $p$ with $\mathfrak{f}\in\mathcal{F}(p)$. Consider this happens
first at time $t\leq t_{0}$. Then,

######  Lemma 4.14.

$\forall h\in\mathcal{F}(g)\ldotp(m,h)\in{\text{{LOG}}}_{g}^{t}$

######  Proof 4.15.

By definition, $p$ executes line 33 at time $t$. Since $\mathfrak{f}$ is still
correct at time $t$ and $\gamma$ ensures the accuracy property,
$f\in\gamma(p,t)$. Hence, $\gamma^{p,t}(g)=\mathcal{F}(g)$. According to line
32, $\forall h\in\gamma^{p,t}(g)\ldotp(m,h)\in{\text{{LOG}}}^{t}_{g}$. Choose
$h\in\mathcal{F}(g)$ and $\hat{t}\leq t$.

######  Lemma 4.16.

$(m,h)\in{\text{{LOG}}}_{g}^{\hat{t}}\Rightarrow{\text{{LOG}}}_{g\cap
h}^{\hat{t}}.\mathit{locked}(m)$

######  Proof 4.17.

Some process $q$ executes line 29 at time $t^{\prime}\leq\hat{t}$. From the
preconditions at lines 26-28, $q\in h$ and
${\text{{phase}}}^{q,t^{\prime}}[m]=\text{{commit}}$. From
${\text{{phase}}}^{q,t^{\prime}}[m]=\text{{commit}}$, $q$ executes lines 19-24
at some earlier time $t^{\prime\prime}<t^{\prime}$. As $q\in h$, $q$ called
${\text{{LOG}}}_{g\cap h}.\mathit{bumpAndLock}(m,\mathrel{-})$ at time
$t^{\prime\prime}$. Consider two messages $m$ and $m^{\prime}$ such that
$m^{\prime}\mapsto m\in C$. Note $\text{{stable}}^{\mathfrak{f},t}$ the
messages stable at time $t$ at any process $p$ with
$\mathfrak{f}\in\mathcal{F}(p)$. Then,

######  Lemma 4.18.

$\forall t\leq t_{0}\ldotp m\in\text{{stable}}^{\mathfrak{f},t}\Rightarrow
m^{\prime}\in\text{{stable}}^{\mathfrak{f},t}$

######  Proof 4.19.

Let $h=\mathit{dst}(m^{\prime})$. Then, $h\in\mathcal{F}(g)$. From Lemma 4.14,
$(m,h)\in{\text{{LOG}}}_{g}^{t}$. Thus, line 29 was executed before time $t$.
Let $p\in g\cap h$ be the process that executes this step first at some time
$t^{\prime}<t$. If $m^{\prime}\in C$, then some process delivers it. Applying
Lemma 4.8, $m^{\prime}<_{{\text{{LOG}}}_{g\cap h}^{\infty}}m$. Then, from
Lemma 4.16, ${\text{{LOG}}}_{g\cap h}^{t^{\prime}}.\mathit{locked}(m)$ By
Claim 7, $m^{\prime}<_{{\text{{LOG}}}_{g\cap h}^{t^{\prime}}}m$. As
$m<_{{\text{{LOG}}}_{g\cap h}^{t^{\prime}}}m^{\prime}$, the precondition at
line 28 requires that ${\text{{phase}}}^{t^{\prime},p}[m]=\text{{stable}}$
Without lack of generality, consider that $m_{\lvert C\rvert}$ is the message
delivered first in $C$, say at process $p$ and time $t$. At time $t-1$,
according to the precondition at line 35, $m_{\lvert C\rvert}$ is stable at
$p$. Let $t^{\prime}\leq t-1$ be the time at which $m_{\lvert C\rvert}$ is
stable first. By applying inductively Lemma 4.18 to $C$, we obtain a
contradiction.

####  4.4.3 Liveness

In what follows, we prove that Algorithm 1 ensures the termination property of
atomic multicast. To this end, we first observe that all of the objects used
in this algorithm are wait-free. As a consequence, no process may block at
some point in time when executing one of the actions of Algorithm 1. This base
observation is commonly used in our proof. Consider that some message $m$ is
multicast by a correct process. It follows that line 7 is executed. Similarly,
if $m$ is delivered at some process, it must have reached the pending phase at
that process (Claim 13). At that time, the precondition at line 10 is true.
Hence, in the above two cases, $m$ reaches ${\text{{LOG}}}_{g}$ at some point
in time. By Claim 1, $\textbf{F}(\textbf{G}(m\in{\text{{LOG}}}_{g}))$. In what
follows, we establish that any such message $m$ reaching the log of its
destination group $g$ is eventually delivered at every correct process in $g$.

######  Lemma 4.20.

$\textbf{G}((\forall p\in\mathit{Correct}\cap
g\ldotp\textbf{F}({\text{{phase}}}^{p}[m]\geq\text{{pending}}))\Rightarrow(\forall
p\in\mathit{Correct}\cap
g\ldotp\textbf{F}({\text{{phase}}}^{p}[m]\geq\text{{commit}})))$

######  Proof 4.21.

Pick $q\in\mathit{Correct}\cap g$. By assumption, $m$ is eventually pending at
$q$. If $m$ reaches a higher phase than pending, applying Claim 13, $m$ must
go through the commit phase at $q$. Otherwise, consider that $m$ is always
pending at $q$. We show that the precondition at line 18 is eventually always
true, leading to a contradiction. Consider $h\in\mathcal{F}(g)$. If $(g\cap
h)$ is faulty, then eventually every cyclic family $\mathfrak{f}$, with
$g,h\in\mathfrak{f}$, is also faulty. By the completeness property of
$\gamma$, eventually $h\notin\gamma(g)$ always holds at $q$. Otherwise, let
$q^{\prime}$ be a correct process in $g\cap h$. By assumption and Claim 13,
$q^{\prime}$ eventually executes line 14, adding a tuple $(m,h,\mathrel{-})$
to ${\text{{LOG}}}_{g}$. Thus, the precondition at line 18 is eventually
always true at process $q$, as required.

######  Lemma 4.22.

$\textbf{G}(m<_{{\text{{LOG}}}_{g}}m^{\prime}\Rightarrow\textbf{G}(m<_{{\text{{LOG}}}_{g}}m^{\prime}))$

######  Proof 4.23.

By Claim 9, $\mathit{dst}(m)=\mathit{dst}(m^{\prime})=g$. If
$m<_{{\text{{LOG}}}_{g}}m^{\prime}$, necessarily $m$ and $m^{\prime}$ are both
in ${\text{{LOG}}}_{g}$. A message is added to ${\text{{LOG}}}_{g}$ either at
line 7 or line 13. Observe that in the later case, it must already be in
${\text{{LOG}}}_{g}$. In fact, only the ordering of the execution of line 7
matters to prove the lemma. Notice that this line is necessarily executed by
the process multicasting the message. For starters, assume that line 7 is
executed first for $m$. Since the problem being solved is group sequential
atomic multicast, it must be the case that $m\prec m^{\prime}$. Name $q$ the
process that multicasts $m^{\prime}$ at some time $t$. As $m\prec m^{\prime}$,
${\text{{phase}}}^{q,t}[m]=\text{{deliver}}$. By Lemma 4.4,
${\text{{LOG}}}_{g}^{t}.\mathit{locked}(m)$. By Claim 6,
$\textbf{G}(m<_{{\text{{LOG}}}_{g}}m^{\prime})$ from that point in time.
Otherwise, line 7 is executed first for $m^{\prime}$. In that case, following
the same reasoning as above, $m^{\prime}$ is locked in ${\text{{LOG}}}_{g}$ at
the time $m$ is appended to the log. By Claim 6,
$\textbf{G}(\neg\leavevmode\nobreak\ (m<_{{\text{{LOG}}}_{g}}m^{\prime}))$.
From which, it follows:

######  Corollary 4.24.

$\forall t,t^{\prime}<t\ldotp
m<_{{\text{{LOG}}}_{g}^{t}}m^{\prime}\Rightarrow(m<_{{\text{{LOG}}}_{g}^{t^{\prime}}}m^{\prime}\lor
m^{\prime}\notin{\text{{LOG}}}_{g}^{t^{\prime}})$ Let
$\min({\text{{LOG}}}_{g})$ be the message at the lowest position in
${\text{{LOG}}}_{g}$ such that for some $p\in\mathit{Correct}\cap g$,
${\text{{phase}}}^{p}[m]\leq\text{{pending}}$.

######  Lemma 4.25.

$\textbf{G}(m=\min({\text{{LOG}}}_{g})\Rightarrow\textbf{F}(\forall
p\in\mathit{Correct}\cap g\ldotp{\text{{phase}}}^{p}[m]=\text{{commit}}))$

######  Proof 4.26.

Let $m$ be $\min({\text{{LOG}}}_{g})$ at some point in time $t_{0}$. Consider
a process $p\in\mathit{Correct}\cap g$. Initially
${\text{{phase}}}^{p}[m]=\text{{start}}$. For the sake of contradiction,
consider that this holds forever after $t_{0}$ Necessarily, the precondition
at line 11 is always false. Thus, at $t>t_{0}$, there must exist $m^{\prime}$
such that $m^{\prime}<_{{\text{{LOG}}}_{g}^{t^{\prime}}}m$ and
${\text{{phase}}}^{p,t}[m^{\prime}]\leq\text{{pending}}$. By Corollary 4.24
and Claim 14, this is also the case at time $t_{0}$. A contradiction to the
very definition of $m$. As a consequence, $m$ moves eventually to a higher
phase than start. Let $t_{p}\geq t_{0}$ be the time at which this happens. At
time $t=\max_{p\in\mathit{Correct}\cap g}t_{p}$, $m$ is in a phase
$\phi\geq\text{{pending}}$ at all the processes in $\mathit{Correct}\cap g$.
By Lemma 4.20, $m$ reaches later eventually the commit phase at all such
processes. Consider a message $m$ with $g=\mathit{dst}(m)$, either multicast
by a correct process or eventually delivered.

######  Lemma 4.27.

$\forall p\in\mathit{Correct}\cap
g\ldotp\textbf{G}(m\in{\text{{LOG}}}_{g}\Rightarrow\textbf{F}({\text{{phase}}}^{p}[m]=\text{{commit}}))$

######  Proof 4.28.

First consider that $\neg\leavevmode\nobreak\
\textbf{F}(m=\min({\text{{LOG}}}_{g}))$. By definition of
$\min({\text{{LOG}}}_{g})$, $\textbf{G}(\forall p\in\mathit{Correct}\cap g$,
${\text{{phase}}}^{p}[m]>\text{{pending}})$. We conclude using Claim 13.
Otherwise, $m$ is at some point in time equal to $\min({\text{{LOG}}}_{g})$.
In this case, Lemma 4.25 tells us that the lemma holds. From what precedes, a
message reaching the log of its destination group is eventually committed at
every correct process in $g$. Next, we prove that it eventually stabilizes. As
pointed in §4.3, if $\mathcal{F}$ is empty then a pair-wise agreement on the
order of messages is sufficient to reach the stable phase. However, in the
general case, stabilization must happen following the order in which messages
appears in _all_ the logs (line 28). As a consequence, we must show that there
is no cycle to ensure that this procedure eventually terminates. To do so, we
first prove that in the absence of failures of the cyclic family, the message
occupies the same final position in the logs of the intersection groups.

$g$$g^{\prime}$$\hat{g}$$g^{\prime\prime}$$h$$\\{p\\}$$\\{p^{\prime}\\}$$\mathfrak{f}$$\mathfrak{f}$’
(a)

$g$$g^{\prime}$$\hat{g}$$g^{\prime\prime}$$h$$\mathfrak{f}$” (b)

$g$$g^{\prime\prime}$$h_{i-1}$$h$$h_{i}$$\mathfrak{f}$” (c)

Figure 2:  Illustration of the construction of family
$\mathfrak{f}^{\prime\prime}\in\mathcal{F}(p^{\prime})$ in Lemma 4.29: _(a)
the two families $\mathfrak{f}$ and $\mathfrak{f}^{\prime}$, (b) case
$\mathfrak{f}\cap\mathfrak{f}^{\prime}=\\{g\\}$, (c) case
$\mathfrak{f}\cap\mathfrak{f}^{\prime}\setminus\\{g\\}\neq\varnothing$. _

######  Lemma 4.29.

For some group $g$ and some process $q$, define $H(q,g)$ as
$\\{h:\exists\mathfrak{f}^{\prime}\in\mathcal{F}(q)\ldotp
g,h\in\mathfrak{f}^{\prime}\land g\cap h\neq\varnothing\\}$. Consider some
$\mathfrak{f}\in\mathcal{F}$ with
$g,g^{\prime},g^{\prime\prime}\in\mathfrak{f}$, $p\in g\cap g^{\prime}$ and
$p^{\prime}\in g\cap g^{\prime\prime}$. Then, $H(p,g)=H(p^{\prime},g)$.

######  Proof 4.30.

The proof is illustrated in Figure 2. Choose $h\in H(p,g)$. By definition,
there exists $\mathfrak{f}^{\prime}\in\mathcal{F}(p)$ such that $g\cap
h\neq\varnothing$ and $g,h\in\mathfrak{f}^{\prime}$. For some appropriate
numbering, $\mathfrak{f}^{\prime}=(g_{i})_{i\in[1,n]}$ with $g_{1}=g$ and
$g_{2}=h$. Similarly, we have $\mathfrak{f}=(h_{i})_{i}$ with
$h_{1}=g^{\prime}$, $h_{2}=g$ and $h_{3}=g^{\prime\prime}$. As
$\mathfrak{f}^{\prime}\in\mathcal{F}(p)$ and $g\in\mathfrak{f}^{\prime}$,
there exists $\hat{g}\in\mathfrak{f}^{\prime}$ such that $p\in g\cap\hat{g}$.
Hence, $p\in g^{\prime}\cap\hat{g}$. We construct a cyclic family
$\mathfrak{f}^{\prime\prime}$ as follows. Assume $\mathfrak{f}$ and
$\mathfrak{f}^{\prime}$ have no other common group than $g$. Then
$\mathfrak{f}^{\prime\prime}$ is simply set to
$\mathfrak{f}\cup\mathfrak{f}^{\prime}$. Otherwise, let $h_{i}$ be the first
group in $(\mathfrak{f}\cap\mathfrak{f}^{\prime})\setminus\\{g\\}$.
$\mathfrak{f}^{\prime\prime}$ is set to
$g_{1},g_{2},\ldots,h_{i},h_{i-1},\ldots h_{3}$. As
$p^{\prime}\in\mathfrak{f}^{\prime\prime}$,
$g,h\in\mathfrak{f}^{\prime\prime}$ and $g\cap h\neq\varnothing$, we have
$h\in H(p^{\prime},g)$.

######  Lemma 4.31.

Assume some process $p$ executes
${\text{{CONS}}}_{m,\mathrel{-}}.\mathit{propose}(k)$ at time $t$ (line 21).
For any $\mathfrak{f}\in\mathcal{F}(p)\cap\mathit{Correct}$, if
$h\in\mathfrak{f}$ and $g\cap h\neq\varnothing$, then
$(m,h,l)\in{\text{{LOG}}}_{g}^{t}$ and $k\geq l$.

######  Proof 4.32.

As $\mathfrak{f}$ is correct, $\mathfrak{f}\in\gamma^{p,t}$ by the accuracy
property of failure detector $\gamma$. The precondition at line 18 requires
that $(m,h,l)\in{\text{{LOG}}}_{g}^{t}$, for some $l$. Variable $k$ is
computed at line 19. Hence, $k\geq l$ when $p$ calls line 21.

######  Lemma 4.33.

Let $\mathfrak{f}$ be a correct cyclic family and $g$, $g^{\prime}$ and
$g^{\prime\prime}$ be three groups in $\mathfrak{f}$ with $g\cap
g^{\prime}\neq\varnothing$ and $g\cap g^{\prime\prime}\neq\varnothing$. Assume
that message $m$ with $\mathit{dst}(m)=g$ is locked in both in both
${\text{{LOG}}}_{g\cap g^{\prime}}$ and ${\text{{LOG}}}_{g\cap
g^{\prime\prime}}$. Then, $m$ has the same position in the two logs.

######  Proof 4.34.

Name $p$ and $p^{\prime}$ respectively the processes that bump (and lock) $m$
in ${\text{{LOG}}}_{g\cap g^{\prime}}$ and ${\text{{LOG}}}_{g\cap
g^{\prime\prime}}$. Let $l$ and $l^{\prime}$ be the respective positions of
$m$ in the two logs before the bump. Applying Lemma 4.29, both processes call
the same instance ${\text{{CONS}}}_{m,\mathfrak{f}^{\prime}}$ at line 21
before executing line 23, for some appropriate family $\mathfrak{f}^{\prime}$.
Let $q$ be the process whose value, say $\kappa$, is decided in
${\text{{CONS}}}_{m,\mathfrak{f}^{\prime}}$. Processes $p$ and $p^{\prime}$
execute $\mathit{bumpAndLock}(m,\kappa)$ on the two logs. Observe that as
$g^{\prime}\in f^{\prime}$, $\hat{\mathfrak{f}}\in\mathcal{F}(q)$ for some
cyclic family $\hat{f}$ with $g,g^{\prime}\in\hat{\mathfrak{f}}$ The same
observation is true for the group $g^{\prime\prime}$. Thus, by Lemma 4.31,
$\kappa\geq\max(l,l^{\prime})$. It follows that $m$ occupies the same final
position in the two logs. To track the relative positions of messages in the
logs, we introduce a few notations. First, the predecessors of a message $m$
in the logs _at a correct process_ $p$ is denoted
$\mathit{pred}(m,p)\triangleq\\{m^{\prime}:\exists
L\in{\text{{LOGS}}}(p)\ldotp m^{\prime}<_{L}m\\}$, where ${\text{{LOGS}}}(p)$
are all the logs at process $p$. We shall write $m^{\prime}<_{p}m$ when
$m^{\prime}$ precedes $m$ at some log at $p$, i.e.,
$m^{\prime}<_{p}m\triangleq m^{\prime}\in\mathit{pred}(m,p)$. The transitive
closure of relation $<_{p}$ across all the correct processes is denoted $<$,
that is $<\triangleq(\cup_{p}<_{p})^{*}$. The predecessors of $m$ according to
$<$ are $\mathit{pred}(m)\triangleq\\{m^{\prime}:m^{\prime}<m\\}$.

######  Lemma 4.35.

$\forall
p\in\mathit{Correct}\ldotp\textbf{G}((\phi\geq\text{{commit}})^{p},<_{p})\leavevmode\nobreak\
\text{is a pos})$

######  Proof 4.36.

For starters, we show that messages addressed to the same destination group
form a monotonically growing totally-ordered set.

######  Claim 15.

$\textbf{G}(m<_{p}m^{\prime}\land\mathit{dst}(m)=\mathit{dst}(m^{\prime})\Rightarrow\textbf{G}(m<_{p}m^{\prime}))$

######  Proof 4.37.

Since the problem being solved is group sequential atomic multicast, either
$m\prec m^{\prime}$ or the converse holds. Without lack of generality,
consider the former case. Then $\mathit{multicast}(m^{\prime})$ occurs at
$q\in g$ and time $t$, after $m$ was delivered by $q$. By Lemma 4.4,
${\text{{LOG}}}_{g}^{q,t}.\mathit{locked}(m)$. Consider
$L\in{\text{{LOGS}}}(p)$ that contains both $m$ and $m^{\prime}$. Message
$m^{\prime}$ is added to $L$, say by $q^{\prime}$ at time $t^{\prime}>t$.
Clearly $q$ executes either line 7 or line 13. In both cases, we have
$L^{t^{\prime}}.\mathit{locked}(m)\land m<_{L^{t^{\prime}}}m^{\prime}$: The
case $\lvert{\text{{LOGS}}}(p)\rvert\leq 3$ is immediate: There are exactly
$\lvert\mathcal{G}(p)\rvert+\lvert\mathcal{G}(p)\rvert*(\lvert\mathcal{G}(p)\rvert-1)/2$
logs at $p$. Hence, either there is a single log at process $p$ and it should
be the one of a destination group; or, there are exactly two groups intersect
in $p$. In the two cases, Claim 15 implies that $<_{p}$ is acyclic. From now,
we assume $\lvert{\text{{LOGS}}}(p)\rvert>3$.

######  Claim 16.

$\exists K\ldotp\forall h\neq
g\in\mathcal{G}(p)\ldotp\textbf{G}({\text{{LOG}}}_{g\cap
h}.\mathit{locked}(m)\Rightarrow{\text{{LOG}}}_{g\cap h}.\mathit{pos}(m)=K)$

######  Proof 4.38.

Consider some family $\mathfrak{f}=\\{g,h,h^{\prime}\\}$, with
$\mathfrak{f}\subseteq\mathcal{G}(p)$. As $p$ belongs to all three groups,
$\mathfrak{f}$ is cyclic. By definition, process $p$ is correct, and thus
family $\mathfrak{f}$ too. Applying Lemma 4.33, if $m$ is locked in both
${\text{{LOG}}}_{g\cap h}$ and ${\text{{LOG}}}_{g\cap h^{\prime}}$ then it
occupies the same position.

######  Claim 17.

Consider $m$, $m^{\prime}$ and $m^{\prime\prime}$ with
${\text{{phase}}}^{p}[m^{\prime}]\geq\text{{commit}}$. Then, for any
$L,L^{\prime}\in{\text{{LOGS}}}(p)$,
$m<_{L}m^{\prime}<_{L^{\prime}}m^{\prime\prime}\Rightarrow(L.\mathit{pos}(m)<L^{\prime}.pos(m^{\prime\prime})\lor(L.\mathit{pos}(m)=L^{\prime}.pos(m^{\prime\prime})\land
m<m^{\prime\prime}))$

######  Proof 4.39.

As the three message are (at least) committed, they must be all locked in the
logs of $p$ (Lemma 4.4). Applying $m<_{L}m^{\prime}$,
$L.\mathit{pos}(m)<L.pos(m^{\prime})\lor(L.\mathit{pos}(m)=L.pos(m^{\prime})\land
m<m^{\prime})$ Similarly,
$(L^{\prime}.\mathit{pos}(m^{\prime})<L^{\prime}.pos(m^{\prime\prime})\lor(L^{\prime}.\mathit{pos}(m^{\prime})=L^{\prime}.pos(m^{\prime\prime})\land
m^{\prime}<m^{\prime\prime})$ Observe that
$L.\mathit{pos}(m^{\prime})=L^{\prime}.pos(m^{\prime})$: if $L=L^{\prime}$
this is trivial, and otherwise we apply Claim 16, From Claim 17,
$((\phi\geq\text{{commit}})^{p},<_{p})$ is a partially ordered set.

######  Lemma 4.40.

$\forall p\in\mathit{Correct}\cap
g\ldotp\textbf{G}(m\in{\text{{LOG}}}_{g}\Rightarrow\textbf{F}({\text{{phase}}}^{p}[m]=\text{{stable}}))$

######  Proof 4.41.

Let
$\mathcal{C}(m,t)\triangleq\mathit{pred}^{t}(m)\cap(\phi\leq\text{{commit}})^{t}$.
The series $(\mathcal{C}(m,t))_{t}$ is defined over $2^{\mathcal{M}}$, which
is a Cauchy space, hence it may converge. Assume that the lemma below holds.

######  Claim 18.

$\lim_{t\rightarrow\infty}\mathcal{C}(m,t)=\varnothing$ By Lemma 4.27, message
$m$ is eventually commit at process $p$, say at time $t_{0}$. Consider the
first moment in time at which $(\mathcal{C}(m,t))_{t}$ reaches its limit (by
Claim 18), say $t_{1}$. At $\max(t_{0},t_{1})$, at process $p$, all the
preconditions at lines 31 and 32 are true. Hence $p$ moves $m$ to the stable
phase, as required. The remainder of the proof is devoted to showing that
Claim 18 holds.

######  Claim 19.

$\forall m^{\prime}\ldotp m^{\prime}\in\mathcal{C}(m,t)\land\exists
t^{\prime}>t\ldotp m^{\prime}\notin\mathcal{C}(m,t^{\prime})\Rightarrow\forall
t^{\prime\prime}>t^{\prime}\ldotp
m^{\prime}\notin\mathcal{C}(m,t^{\prime\prime})$

######  Proof 4.42.

By definition of $\mathcal{C}(m,t)$ and Claim 14.

######  Claim 20.

$(\mathcal{C}(m,t))_{t}$ has a finite upper bound in $2^{\mathcal{M}}$.

######  Proof 4.43.

Immediate because the problem being solved is group sequential atomic
multicast. Let $\mathcal{C}$ be the finite upper bound of
$(\mathcal{C}(m,t))_{t}$. For $m^{\prime}\in\mathcal{C}$, define $t_{c}$
either the point in time satisfying Claim 19, or $0$ if there is no such
point. Let $T=\max_{m^{\prime}\in\mathcal{C}}t_{c}$.

######  Claim 21.

$\forall t\geq T\ldotp\mathcal{C}(m,t+1)\subseteq\mathcal{C}(m,t)$

######  Proof 4.44.

By definition of $t_{c}$ for every message $m^{\prime}\in\mathcal{C}$. From
what follows $(\mathcal{C}(m,t))_{t}$ is monotonically decreasing after time
$T$. Let $\mathcal{C}$ be its limit. We now establish that $\mathcal{C}$ is
empty. If this is the case, $(\mathcal{C}(m,t))_{t}$ converges toward
$\varnothing$, as required by Claim 18.

######  Claim 22.

$\textbf{G}((\mathcal{C},<)\leavevmode\nobreak\ \text{is a pos.})$.

######  Proof 4.45.

(By contradiction) Let $C=m_{1}<\ldots<m_{K}<m_{1}$ be a cycle in
$(\mathcal{C},<)$, with $K=\lvert C\rvert\geq 2$. We note
$\mathfrak{f}^{\prime}=(g_{k})_{k\in[1,K]}$ the family of destination groups.
Without lack of generality, consider that there is no sub-cycle in $C$. First,
since there is no sub-cycle in $C$, all messages in $C$ must have different
destination groups. Indeed, if $m_{k}$ and $m_{k^{\prime}}$ are both addressed
to the same destination group then they are both forever in some phase
$\phi\leq\text{{commit}}$. This contradicts that the problem solved is group
sequential atomic multicast. Second, applying the definition of $<$, for each
$k\in[1,K]$, there exists a correct process $p_{k}$ and some log
$L_{k}\in{\text{{LOGS}}}(p_{k})$ such that
$m_{k}<_{L_{k}}m_{k+1\leavevmode\nobreak\ \text{mod}\leavevmode\nobreak\ K}$.
Hence from what precedes,  1. $\pi=g_{1}g_{2}{\ldots}g_{K}g_{1}$is a closed
path in the intersection graph of $\mathfrak{f}^{\prime}$, and  2. for every
$k\in[1,K]$, $p_{k}\in g_{k}\cap g_{k+1}$ is correct.  It follows that
$\mathfrak{f}^{\prime}$ is correct. Hence, we can apply inductively Lemma 4.33
on each $(m_{k},m_{k+1})$, with $k\in[1,K]$. It follows that $m_{1}<m_{1}$; a
contradiction to the definition of a log. By Claim 22, $\mathcal{C}$ is
partially ordered by $<$. Pick $m_{0}$ an element with no predecessor in
$\mathcal{C}$ wrt.relation $<$, and name $h=\mathit{dst}(m_{0})$. Below , we
prove that $m_{0}$ is eventually stable at every correct process in $h$.

######  Claim 23.

$\forall p\in
h\cap\mathit{Correct}\ldotp\forall\mathfrak{f}\in\mathcal{F}(p)\cap\mathit{Correct}\ldotp\forall
h^{\prime}\in\mathfrak{f}(h)\ldotp\textbf{F}((m_{0},h^{\prime})\in{\text{{LOG}}}_{h})$

######  Proof 4.46.

Since $\mathfrak{f}$ is correct, there exists a correct process in $h\cap
h^{\prime}$, say $q$. At process $q$, line 26 is eventually always true by
Lemma 4.27, say at time $t_{0}$. By the definition of $m_{0}$, there exists a
time $t_{1}$ after which line 28 is also always true, at say $t_{1}$. Since
$h^{\prime}\in\mathcal{G}(q)$, $q$ eventually executes
$\mathit{stabilize}(m_{0},h^{\prime})$ after time $\max(t_{0},t_{1})$.

######  Claim 24.

$\forall p\in
h\cap\mathit{Correct}\ldotp\textbf{F}({\text{{phase}}}^{p}[m_{0}]\geq\text{{stable}})$

######  Proof 4.47.

According to Lemma 4.27, message $m_{0}$ is eventually commit at $p$. Observe
that the case $h\notin\mathcal{F}$ is immediate. Indeed, once $m_{0}$ is
committed, the precondition at line 32 is vacuously true. Thus consider some
family $\mathfrak{f}\in\mathcal{F}(p)$ with $h\in\mathfrak{f}$. By Claim 23,
for each $h^{\prime}\in\mathfrak{f}(h)$, a tuple $(m_{0},h^{\prime})$ is
eventually in ${\text{{LOG}}}_{h}$. Hence the preconditions at lines 31 and 32
are both eventually true, leading $p$ to move $m_{0}$ to the stable phase.
Clearly $\mathit{pred}(m_{0},p)$ is empty if $p\notin h$. By Claim 24, it is
also empty eventually at $p\in h$. Since
$\mathcal{C}(m,t)=\mathit{pred}^{t}(m)\cap(\phi\leq\text{{commit}})^{t}$,
$m_{0}$ is eventually not in $\mathcal{C}(m,t)$; a contradiction to
$m_{0}\in\mathcal{C}$.

######  Lemma 4.48.

$\forall p\in\mathit{Correct}\cap
g\ldotp\textbf{G}(m\in{\text{{LOG}}}_{g}\Rightarrow\textbf{F}({\text{{phase}}}^{p}[m]=\text{{deliver}}))$

######  Proof 4.49.

Let
$\mathcal{S}(m,t)\triangleq\\{m^{\prime}<_{p}m:{\text{{phase}}}^{p,t}[m^{\prime}]\leq\text{{stable}}\\}$.
By Lemma 4.40, $m$ is eventually stable at $p$, say at time $t_{0}$. Consider
some $t\geq t_{0}$. By Lemma 4.4 and Claim 6,
$\mathcal{S}(m,t+1)\subseteq\mathcal{S}(m,t)$. By Lemma 4.35,
$\mathcal{S}(m,t)$ is totally ordered by $(<_{p})^{*}$. Let $m_{0}$ be the
smallest element in $\mathcal{S}(m,t)$. By Lemma 4.40 and the definition of
$m_{0}$, the preconditions at lines 35 and 36 are eventually true for $m_{0}$.
Hence, eventually $m_{0}\notin\mathcal{S}(m,t)$. Applying inductively the
above reasoning, $(\mathcal{S}(m,t))_{t}$ converges toward an empty set. When
this happens, the preconditions at lines 35-36 are true for message $m$ As a
consequence, process $p$ eventually delivers $m$. As a corollary of the above
lemma, we obtain that:

######  Proposition 4.50.

Algorithm 1 ensures the termination property of atomic multicast.

####  4.4.4 Establishing the result

The lemma below is necessary to prove the genuineness of Algorithm 1.

######  Proposition 4.51.

Given two intersecting groups $g$ and $h$, if no message is addressed to $h$
during a run, then only the processes in $g\cap h$ take steps to implement an
operation of ${\text{{LOG}}}_{g\cap h}$

######  Proof 4.52.

First, let us establish that if $p$ and $p^{\prime}$ execute respectively the
sequences of operations $\sigma$ and $\sigma^{\prime}$ over
${\text{{LOG}}}_{g\cap h}$, then $\sigma\sigma^{\prime}$ or the converse
holds. A call to ${\text{{LOG}}}_{g\cap h}$ is executed at lines 13 and 23. It
requires that $m\in{\text{{LOG}}}_{g}$ at that time. Moreover, a process may
only call these two lines once and in this exact order. Consider that a
process $q$ executes an operation $\mathit{op}$ for $m$ then another operation
$\mathit{op}^{\prime}$ for $m^{\prime}$. For the sake of contradiction, assume
$m^{\prime}<_{{\text{{LOG}}}_{g}}m$. Since
$m^{\prime}<_{{\text{{LOG}}}_{g}}m$, when $q$ executes line 13, the
precondition at line 11 must be true for $m^{\prime}$. Thus the lines lines 13
and 23 were executed for $m^{\prime}$ before. Then let us observe that, as
processes in $g$ executes the operations of ${\text{{LOG}}}_{g\cap h}$ in the
exact same order then the run is contention free. As a consequence, only the
AC objects are used to execute these operations and only the processes in
$g\cap h$ take steps in the run, as required. At the light of the preceding
results, we may then conclude that the algorithm is correct.

######  Theorem 4.53.

Algorithm 1 implements genuine group sequential atomic multicast.

######  Proof 4.54.

Integrity follows from the pseudo-code of Algorithm 1. By Propositions 4.3 and
4.50, the algorithm satisfies the ordering and termination properties of
atomic multicast. Proposition 4.51 ensures that the solution is genuine.

##  5 Necessity

Consider some environment $\mathfrak{E}$, a failure detector $D$ and an
algorithm that uses $D$ to solve atomic multicast in $\mathfrak{E}$. This
section shows that $D$ is stronger than $\mu$ in $\mathfrak{E}$. To this end,
we first use the fact that atomic multicast solves consensus per group. Hence
$\mu$ is stronger than $\land_{g\in\mathcal{G}}\leavevmode\nobreak\
(\Omega_{g}\land\Sigma_{g})$. §5.1 proves that $D$ is stronger than
$\Sigma_{g\cap h}$ for any two groups $g,h\in\mathcal{G}$. Further, in §5.2,
we establish that $D$ is stronger than $\gamma$. This last result is
established when $D$ is realistic. The remaining cases are discussed in
§LABEL:sect:discussion.

###  5.1 Emulating $\Sigma_{g\cap h}$

Atomic multicast solves consensus in each destination group. This permits to
emulate $\land_{g\in\mathcal{G}}\Sigma_{g}$. However, for two intersecting
groups $g$ and $h$, $\Sigma_{g}\land\Sigma_{h}$ is not strong enough to
emulate $\Sigma_{g\cap h}$.333 The two detectors may return forever non-
intersecting quorums.  Hence, we must build the failure detector directly from
the communication primitive. Algorithm 2 presents such a construction. This
algorithm can be seen as an extension of the work of Bonnet and Raynal [kset-
bonnet] to extract $\Sigma_{k}$ when $k$-set agreement is solvable. Algorithm
2 emulates $\Sigma_{\cap_{g\in G}g}$, where $G\subseteq\mathcal{G}$ is a set
of at most two intersecting destination groups. At a process $p$, Algorithm 2
employs multiple instances of algorithm . In detail, for every group $g\in G$
and subset $x$ of $g$, if process $p$ belongs to $x$, then $p$ executes an
instance (line 2). Variable $Q_{g}$ stores the responsive subsets of $g$, that
is the sets $x\subseteq g$ for which delivers a message. Initially, this
variable is set to $\\{g\\}$. Algorithm 2 Emulating $\Sigma_{\cap_{g\in G}g}$
– code at process $p$ 1:variables: 2: $(A_{g,x})_{g\in G,x\subseteq g\ldotp
p\in x}$ 3: $(Q_{g})_{g\in G}\leftarrow\lambda g.\\{g\\}$ 4:
$(\mathit{qr}_{g})_{g\in G}\leftarrow\lambda g.g$ 5:for all $g\in G,x\subseteq
g:p\in x$ do 6: let $m$ such that
$\mathit{dst}(m)=g\land\mathit{payload}(m)=p$ 7:
$A_{g,x}.\mathit{multicast}(m)$ 8:when $A_{g,x}.\mathit{deliver}(\mathrel{-})$
9: $Q_{g}\leftarrow Q_{g}\cup\\{x\\}$ 10:when $\mathit{query}$ 11: if
$p\notin\bigcap_{g\in G}g$ then 12: return $\bot$ 13: for all $g\in G$ do 14:
$\mathit{qr}_{g}\leftarrow\leavevmode\nobreak\
\text{{choose}}\leavevmode\nobreak\ \underset{y\in
Q_{g}}{\operatorname*{arg\,max}}\leavevmode\nobreak\ \mathit{rank}(y)$ 15:
return $(\bigcup_{g\in G}\mathit{qr}_{g})\cap(\bigcap_{g\in G}g)$ Algorithm 2
uses the ranking function defined in [kset-bonnet]. For some set
$x\subseteq\mathcal{P}$, function $\mathit{rank}(x)$ outputs the rank of $x$.
Initially, all the sets have rank $0$. Function $\mathit{rank}$ ensures a
unique property: a set $x$ is correct if and only if it ranks grows forever.
To compute this function, processes keep track of each others by exchanging
(asynchronously) “alive” message. At a process $p$, the number of “alive”
messages received so far from $q$ defines the rank of $q$. The rank of a set
is the lowest rank among all of its members. At the start of Algorithm 2, a
process atomic multicasts its identity for every instance it is executing
(line 7). When, delivers a process identity, $x$ is added to variable $Q_{g}$
(line 9). Thus, variable $Q_{g}$ holds all the instances that progress
successfully despite that $g\setminus x$ do not participate. From this set,
Algorithm 2 computes the most responsive quorum using the ranking function
(line 14). As stated in Theorem 5.1 below, these quorums must intersect at any
two processes in $\cap_{g\in G}g$.

######  Theorem 5.1.

Algorithm 2 implements $\Sigma_{\cap_{g\in G}g}$ in $\mathfrak{E}$.

######  Proof 5.2.

For starters, we establish that the range of Algorithm 2 is valid. Let us
observe that if $p$ does not belong to $\bigcap_{g\in G}g$, then Algorithm 2
always returns $\bot$ (line 12). In the converse case, $p$ executes line 15
when it inquiries the emulated failure detector. Initially, variable $qr_{g}$
contains $g$. When it is changed to some set value $x$ (line 14), $x\subseteq
g$ holds with $p\in x$ (line 9) Thus, Algorithm 2 always returns at $p$ a non-
empty set in the range of $\bigcap_{g}g$, as required. It remains to prove
that Algorithm 2 also ensure the two key properties of the failure detector.
To this end, consider a run $R$ of Algorithm 2 during which correct processes
take an unbounded amount of steps $S$. Let $F$ and $H$ be respectively the
failure pattern and the history of $D$ in $R$.

##### (Intersection)

For the sake of contradiction, assume $p,q\in\bigcap_{g}g$ return at line 15
two disjoint subsets $s$ and $s^{\prime}$. Hence at process $p$, each $($
delivered some identity in $R$ and we have
$s=(\bigcup_{g}qr_{g})\cap(\bigcap_{g}g)$. The same observation holds at
process $q$ for some family $(qr^{\prime}_{g})_{g}$. We claim that there exist
two disjoint subsets $x$ and $y$ respectively in $(qr_{g})_{g}$ and
$(qr^{\prime}_{g})_{g}$. This is trivial if $G$ contains a single group, with
$s=x$ and $s^{\prime}=y$. Otherwise, $s=(qr_{g}\cup qr_{h})\cap(g\cap h)$ and
$s^{\prime}=(qr_{g}^{\prime}\cup qr_{h}^{\prime})\cap(g\cap h)$, with $g\neq
h$. Hence, we have immediately that $qr_{g}$ and $qr^{\prime}_{h}$ are
disjoint. Let $\hat{p}$ and $\hat{q}$ be the two identities returned
respectively in instances  and  during run $R$. Applying Lemma
LABEL:lem:model:1, there exists a run $R_{x}$ of algorithm  with steps $S|$
and with history $D$. Similarly, there exists a run $R_{y}$ of  with steps
$S|$ and the same history. Since $x$ and $y$ are disjoint, Lemma
LABEL:lem:model:3 tells us that there exists a run of  with steps $(S|$. In
this run, processes $p$ and $q$ deliver respectively identities $\hat{p}$ and
$\hat{q}$ first. A contradiction to the ordering property of atomic multicast.

##### (Liveness)

Consider some correct process $p\in\bigcap_{g}g$. We show that for each $g\in
G$, eventually $\mathit{qr}_{g}$ contains only correct processes at process
$p$. Let $\mathcal{C}_{g}$ be $g\cap\mathit{Correct}(F)$. Applying Lemma
LABEL:lem:model:1, there exists a run $\hat{R}$ of  with history $F$ and steps
$S|$. To the correct processes in $\hat{R}$, this run is indistinguishable
from a run $\hat{R^{\prime}}$ in which the faulty processes in $g$ take no
steps before they fail. As solves genuine atomic multicast and there is no
message addressed to groups outside $g$, every process in $\mathcal{C}_{g}$
delivers all the identities of $\mathcal{C}_{g}$ in $\hat{R^{\prime}}$. Thus,
this also happens in $R$. Consider a point in time from which
$\mathcal{C}_{g}$ is in $Q_{g}$ at process $p$. Assume that $\mathit{qr}_{g}$
takes infinitely often some value $x$ in $R$. It follows that quorum $x$ has
infinitely often a higher rank than $\mathcal{C}_{g}$. From the definition of
the ranking function, $x$ is a set of correct processes. Thus, for each $g\in
G$, there exists a point in time $t_{g}$ after which $\mathit{qr}_{g}$
contains only correct processes at process $p$. After time $t=\max_{g\in
G}t_{g}$, only correct processes are returned at line 15, as required.

###  5.2 Emulating $\gamma$

##### Target systems

A process $p$ is failure-prone in environment $\mathfrak{E}$ when for some
failure pattern $F\in\mathfrak{E}$, $p\in\mathit{Faulty}(F)$. By extension, we
say that $P\subseteq\mathcal{P}$ is failure-prone when for some
$F\in\mathfrak{E}$, $P\subseteq\mathit{Faulty}(F)$. A cyclic family
$\mathfrak{f}$ is failure-prone when one of its group intersections is
failure-prone. Below, we consider that $\mathfrak{E}$ satisfies that