Consensus in Rooted Dynamic Networks with
Short-Lived Stability
Kyrill Winkler1 , Manfred Schwarz1 and Ulrich Schmid1

arXiv:1602.05852v3 [cs.DC] 10 Feb 2017

1

TU Wien, Vienna, Austria, {kwinkler, mschwarz, s}@ecs.tuwien.ac.at

ABSTRACT
We consider the problem of solving consensus using deterministic algorithms in a synchronous dynamic network with unreliable, directional point-to-point links,
which are under the control of a message adversary. In
contrast to a large body of existing work that focuses
on oblivious message adversaries where the communication graphs are picked from a predefined set, we consider
message adversaries where guarantees about stable periods that occur only eventually can be expressed. We
reveal to what extent such eventual stability is necessary
and sufficient, that is, we present the shortest period of
stability that permits solving consensus, a result that
should prove quite useful in systems that exhibit erratic
boot-up phases or recover after repeatedly occurring,
massive transient faults. Contrary to the case of longer
stability periods, where we show how standard algorithmic techniques for solving consensus can be employed,
the short-lived nature of the stability phase forces us to
use more unusual algorithmic methods that avoid waiting explicitly for the stability period to occur.

Keywords
Dynamic networks, consensus, message adversary, eventual stability, short stability periods, rooted directed
graphs

1.

INTRODUCTION

We consider deterministic consensus algorithms in
synchronous dynamic networks, where a potentially unknown number n of processes that never fail1 communicate via unacknowledged messages over unreliable pointto-point links. Consensus, which is a pivotal service in
truly distributed applications, is the problem of computing a common decision value based on local input
values of all the processes. An execution of a consensus
algorithm in our system proceeds in a sequence of lockstep synchronous2 rounds, where message loss is mod1

Nevertheless, a crash of some process p in some round
could easily be modelled by p sending no messages in
any later round.
2
It assumes that all processes simultaneously broadcast

elled using an omniscient message adversary that determines the directed communication graph G r for each
round r. A directed edge (p, q) present in G r means that
the message sent by p in round r is successfully received
by q.
In most existing work in this area, e.g. [2, 9, 19, 20],
the message adversary is oblivious, i.e., may choose each
G r from the same set of admissible graphs arbitrarily in
each round. For instance, the classic result from Santoro
and Widmayer [19] states that consensus is impossible
if the adversary may suppress n − 1 or more messages
in every round. More recently, [9] introduced an equivalence relation on the set of admissible communication
graphs such that consensus is solvable if and only if for
each equivalence class there is a common source (a node
that has a directed path to every other node) in every
graph. These (and similar) approaches characterize the
solvability of consensus by means of properties of the
set of admissible graphs.
We also explore the solvability/impossibility border
of consensus, albeit under non-oblivious message adversaries that support eventual stabilization [3,4,22]: Here,
the set of admissible choices for G r may change with
evolving round numbers r. Rather than constraining
the set of admissible graphs, we hence constrain admissible graph sequences. As it turns out, consensus can
be solved for graph sequences where the set of graphs
occurring in the sequence would render consensus impossible under an oblivious message adversary [9, 19].
Apart from being theoretically interesting, considering eventually stabilizing dynamic networks is also useful from a practical perspective: Algorithms that work
correctly under eventually stabilizing message adversaries are particularly suitable for systems that suffer
from uncoordinated boot-up sequences or systems that
must recover from massive transient faults: Network
connectivity can be expected to improve over time here,
e.g., due to improving clock synchronization quality.
Since it is usually difficult to determine the time when
a message at the beginning of a round, receive the messages from each other, and then simultaneously make a
state transition at the end of the round, thereby proceeding to the next round.

such a system has reached normal operation mode, algorithms that just terminate when a reasonably stable
period has been reached are obviously advantageous.
Algorithms that work correctly under short-lived stable periods are particularly interesting, since they have
higher coverage and terminate earlier in systems where
longer stable periods occur only rarely or even not at all.
Note that the occurrence of short-lived stability periods
could be confirmed in the case of a prototype wireless
sensor network [17].
Last but not least, stabilizing algorithms require less
reliable and, in our case, not inherently bidirectional
communication underneath, hence work with cheaper
and/or more energy-efficient network communication interfaces. After all, guaranteeing reliable bidirectional
communication links typically incurs significant costs
and/or delays and might even be impossible in adverse
environments. We hence conjecture that our findings
may turn out useful for applications such as mobile adhoc networks [12] with heavy interference or disasterrelief applications [15].
In view of such applications, our core assumption of
a synchronous system may appear somewhat unreasonable. However, it is not thanks to modern communication technology [24]: As synchronized clocks are
typically required for basic communication in wireless
systems anyway, e.g., for transmission scheduling and
sender/receiver synchronization, global synchrony is reasonably easy to achieve: It can be integrated directly
at low system levels as in 802.11 MAC+PHY [1], provided by GPS receivers, or implemented by means of
network time synchronization protocols like IEEE 1588
or FTSP [16].
Main contributions and paper organization: In
this paper, we thoroughly answer the question of the
minimal stability required for solving consensus under
eventual stabilizing message adversaries. After the introduction of our system model and our message adversaries in Section 2 and Section 3, respectively, we establish the following results:
(1) We provide a novel algorithm in Section 5, along
with its correctness proof, which solves consensus
for a message adversary that generates graph sequences consisting of graphs that (i) are rooted,
i.e., have exactly one root component (a strongly
connected component without any incoming edges
from outside of the component), and (ii) contain
a subsequence of x = D + 1 consecutive graphs
whose root component is formed by the same set of
nodes (“stable root component”). Herein, the system parameter D 6 n−1 is the dynamic diameter,
i.e., the number of rounds required for any node in
a stable root component to reach all nodes in the
system. Thanks to (i), our algorithm is always safe
in the sense that agreement is never violated; (ii)
is only needed to ensure termination. Compared
to all existing algorithms for non-oblivious mes-

sage adversaries like [3, 4, 22], where the processes
more or less wait for the stability window to occur, our algorithm uses quite different algorithmic
techniques.
(2) In previous work [3, 5], it has been shown that
x = D−1 is a lower bound for the stability interval
for any consensus algorithm working under message adversaries that guarantee a stable root component to occur eventually, and that (a bound on)
D must be a priori known.3 In Section 4 of this paper, we improve the lower bound to x = D, which
reveals that the previous bound was not tight and
that our new algorithm is optimal. This result
also shows that the mere propagation of some input value to every process does not suffice to solve
consensus in this setting.
(3) To complement earlier results [22] about consensus
algorithms that work for stability periods longer
than 2D + 1, we show in Section 6 that very large
periods of stability, namely, at least 3n − 3, also
allow to adopt the well-known uniform voting algorithm [8] for solving consensus in our setting.
Some conclusions and directions of future work in Section 7
complete the paper.
As a final remark, we note that our methodology is in
stark contrast to the approach advocated in [18], which
shows, among other insightful results, that the message adversary SOURCE + QUORUM allows to simulate an asynchronous message passing system with process crashes augmented by the failure detector (Σ, Ω).
Since this is a weakest failure detector for consensus [10],
it is possible to use classic consensus algorithms on top
of this simulation. Furthermore, as Σ is the weakest failure detector to simulate shared memory on top of waitfree asynchronous message passing [10], even shared
memory algorithms that rely on Ω could be employed.
In [5, Sec. 8], we hence investigated the potential of
simulating (Σ, Ω) on top of eventually stabilizing message adversaries, as this would allow us to employ such
well-established consensus solutions instead of specifically tailored algorithms. Unfortunately, it turned out
that Σ cannot be implemented here, even in the case of
message adversaries that eventually guarantee an infinite period of stability — not to speak of message adversaries that guarantee only a finite period of stability
like the one presented in this paper. Therefore, we had
to conclude that, for this type of message adversaries,
failure detector simulations are no viable alternative to
the approach taken here.
3

Whereas this may seem a somewhat unrealistic
(though inevitable) restriction at first sight, it must be
noted that D only needs to be guaranteed throughout
the stability interval. And indeed, our wireless sensor
network measurements [17] confirmed that this is not
an unrealistic assumption.

Related work
Research on consensus in synchronous message passing
systems subject to link failures dates back at least to
the seminal paper [19] by Santoro and Widmayer; generalizations have been provided in [6–9,20]. In all these
papers, consensus, resp. variants thereof, are solved in
systems where, in each round, a digraph is picked from
a set of possible communication graphs. The term message adversary was coined by Afek and Gafni in [2] for
this abstraction.
A different approach for modeling dynamic networks
has been proposed in [13]: T -interval connectivity guarantees a common subgraph in the communication graphs
of every T consecutive rounds. [14] studies agreement
problems in this setting. Note that solving consensus
is relatively easy here, since the model assumes bidirectional and always connected communication graphs. In
particular, 1-interval-connectivity, the weakest form of
T -interval connectivity, corresponds to all nodes constituting a perpetually constant set of source nodes.
In both lines of research, there is no notion of eventually stabilizing behavior of dynamic networks. To the
best of our knowledge, the first instance of a message
adversary that guarantees eventual stable root components has been considered in [3]: It assumed communication graphs with a non-empty set of sources and
long-living periods of stability x = 4D +1. [4,23] studies
consensus under a message adversary with comparably
long-lived stability, which gracefully degrades to general k-set agreement in case of unfavorable conditions.
However, this message adversary must also guarantee a
certain influence relation between subsequently existing
partitions. [22] established a characterization of uniform
consensus solvability/impossibility for longer stability
periods. In particular, it provides a consensus algorithm that works for stability periods of at least 2D + 1
but does not require graph sequences where all graphs
are rooted.
Finally, [18] used message adversaries that allow a
notion of “eventually forever” to establish a relation to
failure detectors. Albeit we do not consider this “extremal” case in this paper, which solely addresses shortlived stability, we note that interesting insights can be
drawn from this relation.

2.

MODEL

We consider a set Π of n deterministic state machines,
called processes, which communicate via message passing over unreliable point-to-point links. Processes have
unique identifiers and are typically denoted by p, q. We
call algorithms that do not depend on n uniform algorithms, whereas algorithms that rely on at least some
bound on n are called non-uniform. In this paper, we
will consider exclusively non-uniform algorithms, except for Theorem 1, where we touch upon uniform algorithms as well. Processes never fail and operate synchronously in lock-step rounds r = 1, 2, . . . , where each

round consists of a phase of communication followed by
a local state transition of every process. In the communication phase of a round, every process sends a message
(possibly empty) to every other process in the system,
and records the messages successfully received from the
other processes. A message adversary (see Section 3 for
the detailed definitions) is a set of graph sequences that
determine which messages are lost in each round.
The state of a process p at the end of its round r
computation is denoted by pr , and the collection of the
round r states of all processes is called round r configuration C r . Those messages that are delivered by the
message adversary in a given round r > 0 are specified
via a digraph4 G r = hΠ, E r i, called the round r communication graph. An edge (p → q) is in G r if and only if
the round r message of p sent to q is not lost. We assume
that every process p always successfully receives from
itself, so the self-loops (p → p) are in every G r . The
in-neighborhood of p in G r , Inp (G r ) = {q | (q, p) ∈ G r )
hence represents the processes from which p received a
message in round r.
A message adversary is characterized by the set of
infinite sequences of consecutive communication graphs
that it may generate, which are called admissible. A
sequence σ of consecutive communication graphs, ranging from round a to round b, is denoted as σ = (G r )br=a ,
where |σ| = b − a + 1, with b = ∞ for infinite sequences.
Since we actually identify a message adversary with its
set of admissible sequences, we can compare different
message adversaries via a simple set inclusion.
We consider the consensus problem, where each process p starts with some input value xp and has a dedicated write-once output variable yp ; eventually, every
process needs to irrevocably decide, i.e., assign a value
to yp (termination) that is the same at every process
(agreement ) and was the input of some process (validity). The assignment of the input values for each
process is summarized in some initial configuration C 0 .
Given a message adversary MA and a deterministic consensus algorithm A, an (admissible) execution or run
ε = hC 0 , σi is uniquely determined by C 0 and an admissible graph sequence σ ∈ MA.
Applying A and a finite sequence σ ′ to a configuration
C of A yields the configuration C ′ = hC, σ ′ i of A. As
usual, we write ε ∼p ε′ if the finite or infinite executions
ε and ε′ are indistinguishable to p (i.e., the round r state
of p is the same in both executions) until p decides.

Dynamic graph concepts
First, we introduce the pivotal notion of a root component R, often called root for brevity, which denotes the
vertex-set of a strongly connected component of a graph
where there is no edge from a process outside of R to a
process in R. Definition 1 gives its formal definition.
4
We sometimes write p ∈ G r instead of p ∈ Π to stress
that p is a vertex of G r , and sloppily write (p → q) ∈ G r
instead of (p → q) ∈ E(G r ).

Definition 1 (Root Component). R 6= ∅ is a
root (component) of graph G, if it is the set of vertices
of a strongly connected component R of G and ∀p ∈
G, q ∈ R : (p → q) ∈ G ⇒ p ∈ R.
It is easy to see that every graph has at least one root
component. A graph G that has a single root component is called rooted ; its root component is denoted by
root(G). Clearly, a graph G is rooted if and only if it
has a rooted spanning tree: the root component is the
union of the roots of all the spanning trees of G. Hence,
there is a directed path from every node of root(G) to
every other node of G.
Conceptually, root components have already been employed for solving consensus a long time ago: The asynchronous consensus algorithm for initially dead processes
introduced in the classic paper [11] relies on a suitably
constructed initial clique, which is just a special case of
a root component.
In order to model stability, we rely on root components that are present in every member of a (sub)sequence
of communication graphs. We call such a root component the stable root component of a sequence and stress
that, albeit the set of processes remains the same, the
interconnection topology between the processes of the
root component and to the processes outside may vary
greatly from round to round.
Definition 2 (Stable Root Component). We
say that a non-empty sequence (G r )r∈I of graphs has a
stable root component R, if and only if each G r of the sequence is rooted and ∀i, j ∈ I : root(G i ) = root(G j ) =
R. We call such a sequence a R-rooted sequence.
We would like to clarify that while “rooted” describes
a graph property, “R-rooted” describes a property of a
sequence of graphs.
Given two graphs G = hV, Ei, G ′ = hV, E ′ i with the
same vertex-set V , let the compound graph G ◦ G ′ :=
hV, E ′′ i where (p, q) ∈ E ′′ if and only if for some p′ ∈ V :
(p, p′ ) ∈ E and (p′ , q) ∈ E ′ . Since we assume self-loops
the compound graph can be written as the product of
the adjacency matrices of G and G ′ .
In order to model information propagation in the network, we use a notion of causal past : Intuitively, a process q is in p’s causal past, denoted q ∈ CPrp (r′ ) if q = p
or if, by round r, p received information (either directly
or via intermediate messages) that q sent in round r′ +1.
Definition 3 (Causal past). Given a sequence
σ of communication graphs that contains rounds a and
b, the causal past of process p from (the end of ) round b
down to (the end of ) round a is CPbp (a) = {p} if a = b
or CPbp (a) = Inp (G a+1 ◦ · · · ◦ G b ) if a < b.
A useful fact about the causal past is that in fullinformation protocols, where processes exchange their
entire state history in every round, we have q ∈ CPrp (s)

if and only if, in round r, p knows q s , the round s state
of q.
To familiarize the reader with our notation, we conclude this section with the following technical Lemma 1.
It describes the information propagation in a graph sequence containing an ordered set G = {G r1 , . . . , G rn },
i 6= j ⇒ ri 6= rj , and i > j ⇒ ri > rj , of n distinct communication graphs, where any G, G ′ ∈ G are
both rooted, but root(G) is not necessarily the same as
root(G ′ ). As we have mentioned earlier, every G ∈ G
has hence a rooted spanning tree and is therefore weakly
connected. In essence, the lemma shows that, by the
end of round rn , each process p received a message from
some process q that was sent after q was member of a
root component of some graph of G.
Lemma 1. Let G = {G r1 , . . . , G rn } be an ordered set
of rooted communication graphs and let X ⊆ Π with
X ∩ root(G r ) 6= ∅ for every G r ∈ G. For every p ∈ Π,
there is some q ∈ X (q may depend on p) and a G r ∈ G
s.t. q ∈ root(G r ) and q ∈ CPrpn (r).
Proof. Let S ri be the set of those processes that, in
round ri , have received information from a process of
X after it was member of a root component so far in
a graph in G. Formally, S ri := {p ∈ Π | ∃q ∈ X, ∃r ∈
{r1 , . . . , ri } : q ∈ root(G r ) ∧ q ∈ CPrpi (r)}. In order to
show the lemma, we prove by induction on i from 1
to n that |S ri | > i. We use the abbreviation X ri :=
X ∩ root(G ri ). The base of the induction, |S r1 | > 1,
follows from the observation that X r1 ⊆ S r1 . For the
induction step, assume for 1 6 i < n that |S ri | > i. We
show that then |S ri+1 | > i+1. If |S ri | > n, as obviously
S ri ⊆ S ri+1 , we are done. If |S ri | < n, consider that
X ri+1 ⊆ S ri+1 . If |X ri+1 \ S ri | > 1, we immediately
have |S ri+1 | > |S ri |. If |X ri+1 \ S ri | = 0, note that
there is a path in G ri+1 from every q ∈ X ri+1 to every
p ∈ Π. Hence, (u → v) ∈ G ri+1 for some u ∈ S ri , v ∈
|S ri | < n. As u ∈ S ri , there is
Π\S ri , since
Sriwe assumed
r
some q ∈ r=r1 X with q ∈ CPrui (r). By Definition 3,
since (u → v) ∈ G ri+1 , we have q ∈ CPvri+1 (r) and thus
v ∈ S ri+1 \ S ri which implies |S ri+1 | > |S ri |.

3.

MESSAGE ADVERSARIES

First, we introduce the adversary that adheres to dynamic diameter D, which gives a bound on the duration
of the information propagation from a stable root component to the entire network. We showed in [21, Lem. 1]
that always D 6 n − 1; a priori restricting D < n − 1
also allows modelling dynamic networks where information propagation is guaranteed to be faster than in the
worst case (as in expander graphs [5], for example).
Definition 4 (Dynamic diameter D). DIAM(D)
is the message adversary that guarantees dynamic (network) diameter D, i.e., for all graph sequences σ ∈
DIAM(D), for all subsequences G r1 , . . . , G r1 +D−1 ⊂ σ
of D consecutive R-rooted communication graphs, we
have R ⊆ CPrp1 +D−1 (r1 − 1) for every p ∈ Π.

The following liveness property, eventual stability, ensures that eventually every graph sequence σ has a Rrooted subsequence σ ′ ⊆ σ of length x. Here Σ denotes
the unrestricted message adversary, i.e., the set of all
communication graph sequences.
Definition 5. ♦STABILITY(x) := {σ ∈ Σ | ∃R ⊆
Π : some σ ′ ⊆ σ with |σ ′ | > x is R-rooted }.
For finite x, ♦STABILITY(x) alone is insufficient for
solving consensus: Arbitrarily long sequences of graphs
that are not rooted before the stability phase occurs
can fool any consensus algorithm to make wrong decisions. For this reason, we introduce a safety property in
the form of the message adversary that generates only
rooted graphs.
Definition 6. ROOTED := {σ ∈ Σ | every G r of σ
is rooted }.
The short-lived eventually stabilizing message adversary ♦STABLED (D + 1) used throughout the main part
of our paper adheres to the dynamic diameter D, guarantees that every G r is rooted and that every sequence
has a subsequence of at least x = D + 1 consecutive
communication graphs with a stable root component.
Since processes are aware under which adversary they
are, they have common knowledge of the dynamic diameter D and the duration of the stability phase x.
Definition 7. We call ♦STABLED (x) = ROOTED∩
♦STABILITY(x) ∩ DIAM(D) the short-lived eventually
stabilizing message adversary with stability period x.
We observe that ♦STABILITY(x) ⊇ ♦STABILITY(D)
for any 1 6 x 6 D, hence it follows that ♦STABLED (x) ⊇
♦STABLED (D). This simple set inclusion turns out to
be quite useful for the next section.

4.

Suppose some algorithm A solves consensus under
MA. We provide two admissible executions ε1 , ε2 (based
on σ1 , resp. σ2 , from Figure 1) of A where ε1 ∼pD+1 ε2 .
We show that pD+1 decides 0 in ε1 and, for almost all
values of n, process pn decides 1 in ε2 .
Let C 0 be the initial configuration with input values
x1 = . . . = xD+2 = 0 and xD+3 = . . . = xn = 1.
Consider execution ε1 = hC 0 , σ1 i with σ1 from Figure 1,
where a dotted edge exists only in every second graph
in a sequence, and all processes not depicted have an
in-edge from every depicted process. σ1 ∈ MA, since
it guarantees eventual stability for 2D − 1 rounds, adheres to the dynamic diameter D and in every round
the communication graph is rooted. By the assumed
correctness of A, there is a round τ by which every process has decided in ε1 . The decision must be 0 because
pD+1 only ever saw processes that knew of input value
0. This is indistinguishable for pD+1 from the execution where all processes did indeed start with input 0,
which, according to the validity property of consensus,
implies a decision on 0.
Now, consider the execution ε2 = hC 0 , σ2 i with σ2
from Figure 1. Again, σ2 ∈ MA, since pn is a stable
root component for r > τ + 1. In every round r 6 τ ,
p ∈ {pD+1 , pD+2 } have the same view in ε1 and ε2 : This
is immediately obvious for 1 6 r 6 D − 1. For D 6 r 6
2D − 1, the view of p1 is different, but this difference is
not revealed to p by the end of round 2D − 1. Finally,
in rounds 2D 6 r 6 τ , the processes {pD+1 , pD+2 }
hear only from themselves in both executions, hence
maintain ε1 ∼pD+1 ε2 .
Consequently, by round τ , pD+1 has decided 0. Yet,
in executions where n > τ + D + 3, according to ε2
in Figure 1, we have that pn never saw a process that
had an input value different from 1. By validity and an
analogous argument as above, pn must hence decide 1 in
ε2 here, which provides the required contradiction.

IMPOSSIBILITY RESULTS AND LOWER As our next result, we present a lower bound for the
duration x of the stable period: We prove that even
BOUNDS

Even though processes know the dynamic diameter
D, for very short stability periods, this is not enough
to solve consensus. In Theorem 1, we prove that if processes do not have access to an upper bound on n (some
N with N > n), i.e., when the algorithm is uniform,
solving consensus is impossible if the period x of eventual stability is shorter than 2D: Here, processes can
never be sure whether a stable root component occurred
for at least D rounds, albeit detecting such a stable root
component is necessary to satisfy validity.
Theorem 1. There is no uniform consensus algorithm for ♦STABLED (x) with 0 < x < 2D.
Proof. As, for x > x′ , it holds that ♦STABILITY(x) ⊂
♦STABILITY(x′ ), it suffices to show that consensus is
impossible under message adversary MA = ROOTED ∩
♦STABILITY(2D − 1) ∩ DIAM(D).

in the non-uniform case, consensus is impossible under
♦STABLED (x) if x 6 D (Theorem 2). Note that this
result improves the lower bound x > D − 1 established
in [3] and thus reveals that the latter was not tight.
Our lower bound can be seen as a generalization of
the “lossy-link” impossibility from [20, Theorem 2], a
particular formalization of consensus for two processes.
There, it was shown that consensus is impossible in a
two-process system where all messages except one may
get lost in every round. In our terminology, this means
that, for n = 2 and D = 1, consensus is impossible under ♦STABLED (1), even if processes are aware of the
size of the system. For general D, Theorem 2 below
shows that a stability period of D or less rounds is insufficient for solving consensus for any value of N as
well. Informally, the reason is that there are executions
where, even with a stability phase of D rounds, some
process cannot precisely determine the root component

pD

pD+2

1

pD+1

 p
1




pD+1

p2

pn 2D−1





pD

pD+2

D

p





D+2

pD+1

p1

pn  τ





...

pn D−1





p1 ∞




pD 2D

...

1

D+2

...

p2

pD+2






...

...
pD

p

...

 p
1




pD+1






...

σ2 :

2D−1

p2

...

σ1 :

 p
1




pD+1

pD

pD+3

2D



∞



 pn 





τ +1

Figure 1: Communication graph sequences of Theorem 1. A dotted edge represents and edge which is in G i if and
only if it is not in G i−1 . We assume there is an edge from every process depicted in the graph to every process not
depicted in the graph.
of the stability window. In Figure 2, for instance, pD+1
cannot determine whether p1 alone or p1 and p2 together constitute the root component after a sequence
of D successive occurrences of Ga , respectively, Gb . The
determination of this root component is crucial, however, since any root component could be the “base” for
a decision in the suffix of some indistinguishable execution.
Our impossibility proof relies on a bivalence argument: Consider some algorithm A that solves the binary consensus problem, where, for every process p, the
initial value xp ∈ {0, 1}. Given some message adversary MA, in analogy to [11], we call a configuration
C = hC 0 , σi of A univalent or, more specifically, vvalent, if all processes decided v in hC, σ ′ i for any σ ′
where σσ ′ ∈ MA. We call C bivalent, if it is not univalent.
Before stating our main theorem, we need to establish
an essential technical lemma. It shows for n > 2 that by
adding/removing a single edge at a time, we can arrive
at any desired rooted communication graph when starting from any other rooted communication graph. Furthermore, during this construction, we can avoid any
graphs that contain a certain “undesirable” root component R′′ .
Lemma 2. Let n > 2, G be a rooted communication
graph with root(G) = {R}, G ′ be a rooted communication graph with root(G ′ ) = {R′ }, and R′′ be some root
component with R′′ 6= R and R′′ 6= R′ . Then, there is a
sequence of communication graphs, G = G1 , . . . , Gk = G ′
s.t. each Gi of the sequence is rooted, root(Gi ) 6= R′′ ,
and, for 1 6 i < k, Gi and Gi+1 differ only in a single
edge.
Proof. We show that for any rooted communiaction
graph G with root(Gi ) = R, there is such a sequence
′
′
G = G 1 , . . . , G j = G for any communication graph G
′
′
′
with root(G ) = R if R differs from R in at most one
′
′
process, i.e., |R ∪ R \ R ∩ R| 6 1. Repeated application
of this fact implies the lemma, because for n > 2 we can
always find a sequence R = R1 , . . . , Rl = R′ of subsets
of Π s.t. for each Ri of the sequence we have Ri 6= R′′

and, for 1 6 i < l, Ri differs from Ri+1 by exactly
one process. To see this, we observe that in the Hasse
diagram of the power set of Π, ordered by set inclusion,
there are always two upstream paths leading from any
two subsets of Π to a common successor.
We sketch how to construct the desired communication graphs G i of the sequence in three phases.
Phase 1: Remove all edges (one by one) between
nodes of R until only a cycle (or, in general, a circuit)
remains, remove all edges between nodes outside of R
until only chains going out from R remain.
Phase 2: If we need to add a node p to R = root(Gi )
′
to arrive at R , for some q ∈ R, first add (q → p). For
any q ′ 6= q where (q ′ → p) ∈ G i with p 6= q ′ , remove
(q ′ → p). Finally, add (p → q).
If we need to remove a node p from R to arrive at
′
R , for any (q → p), (p → q ′ ) ∈ G i , with q, q ′ ∈ R
subsequently add (q → q ′ ) and (q ′ → q), then remove
(p → q) and (p → q ′ ). Note that we perform this step
also when q = q ′ .
Phase 3: Since we now already have some commu′
nication graph G i with root(G i ) = R , it is easy to
add/remove edges one by one to arrive at the topology
′
′
of G . First, we add edges until the nodes of R are
completely connected among each other, the nodes not
′
in R are completely connected among each other, and
′
there is an edge from every node of R to each node
′
not in R . Second, we remove the edges not present in
′
G.

Theorem 2. There is no non-uniform consensus algorithm for message adversary ♦STABLED (x) with 1 6
x 6 D. This holds even if the adversary must guarantee
that, in addition to ♦STABLED (x), the first D rounds
are R-rooted (provided the processes do not know R a
priori).
Proof. In the case where D = 1, we need to show
the impossibility of ♦STABLED (1). We immediately
note that σ ∈ ♦STABLED (1) if and only if we have
that each G ∈ σ is rooted and a has graph diameter of

p2

p2

p1

p1
...

p2

...

p2

...

p1

...

p1

pD+1

pD+1

pD+1

pD+1

Ga

Gb

Gc

Gd

Figure 2: Communication graphs for Theorem 2. We
assume there is an edge from every process depicted in
the graph to every process not depicted in the graph.

1. Clearly, the graph sequence where (i) two fixed processes p, q have non-self-loop in-edges at most from each
other and at least one of those present in every G r , and
(ii) all other processes have an in-edge from both p and
q is in ♦STABLED (1). However, a trivial modification
of [20, Theorem 2] shows that consensus (in particular,
among p and q) is impossible in this setting.
For the remainder of the proof, let us thus assume
D > 2. Since ♦STABLED (x) ⊃ ♦STABLED (D) for
x 6 D, it suffices to show the impossibility of consensus
under ♦STABLED (D): The execution ε where consensus cannot be solved is admissible under ♦STABLED (x)
if it is admissible under ♦STABLED (D). The proof proceeds roughly along the lines of [20, Lemma 3]. It first
shows that there is a bivalent round-D configuration
for any consensus algorithm and proceeds to show by
induction that every bivalent configuration has a bivalent successor configuration. Hence, any consensus algorithm permits a perpetually bivalent execution under
♦STABLED (D), where consensus cannot be solved.
We show that a bivalent execution is even contained
in the adversary ♦STABLE′D (D) ⊆ ♦STABLED (D), which
consists of those executions of ROOTED ∩ DIAM(D)
where already the first D rounds are R-rooted.
For the induction base, we show that not all round D
configurations of A can be univalent: Assume that some
algorithm A solves consensus under ♦STABLE′D (D) and
suppose that all round D configurations of A were univalent.
Let C 0 be some initial configuration of A with xp1 = 0
and xp2 = 1 and recall the graphs Ga , Gb , Gc and Gd from
Figure 2. For i ∈ {a, b, c, d} let CiD = hC 0 , (Gi )D
1 i denote the configuration which results from applying Gi D
times to C 0 . Let S(p) denote the star-like graph where
there is an edge from the center vertex p to every other
vertex and from every vertex to itself but there are no
other edges in the graph. Clearly, CaD is 0-valent since
′
hCaD , (S(p1 ))∞
D+1 i ∈ ♦STABLED (D) and for p1 this is
indistinguishable from the situation where all processes
p have xp = 0. A similar argument shows that CdD is
1-valent.
Consider two cases:
(1) CbD is 1-valent. But then, CaD cannot be 0-valent

D
∞
since hCaD , (S(pD+1 ))∞
D+1 i ∼pD+1 hCb , (S(pD+1 ))D+1 i.
D
D
(2) Cb is 0-valent. Then, Cc is also 0-valent since
D
∞
D
hCbD , (S(p1 ))∞
D+1 i ∼p1 hCc , (S(p1 ))D+1 i. But then Cd
D
∞
cannot be 1-valent because hCc , (S(pD+1 ))D+1 i ∼pD+1
hCdD , (S(pD+1 ))∞
D+1 i.
Hence, not all round D configurations are univalent.
For the induction step, let us assume that there exists a bivalent round r configuration C r at the end of
round r > D. For a contradiction, assume that all
round r + 1 configurations reachable from C r are univalent. Thus, there exists a 0-valent round r + 1 configuration C0r+1 = hC r , G0 i that results from applying
some communication graph G0 to C r . Moreover, there
is a 1-valent round r + 1 configuration C1r+1 = hC r , G1 i
that results from applying some communication graph
G1 to C r .
First, let us show that for G ∈ {G0 , G1 }, it holds
that, if root(G) = root(G r ), there is an applicable
graph G ′ s.t. hC r , G ′ i has the same valency as hC r , Gi
and root(G) 6= root(G ′ ). The reason for this is that
we can construct G ′ from G by simply adding an edge
(p → q) for some q 6= p, p 6∈ root(G), q ∈ root(G)
if |root(G)| = 1, respectively, by removing (p → q)
for some q ∈ root(G) and all p 6= q if |root(G)| > 1.
This yields a graph G ′ with the desired property because
r
′
∞
hC r , G, (S(p))∞
r+1 i ∼p hC , G , (S(p))r+1 i. The applica′
′
bility of G follows because G is rooted and root(G ′ ) 6=
root(G r ) ensures that the resulting subsequence is a
prefix of some sequence of DIAM(D) for any D > 1,
because, for these choices of D, a changing root component trivially satisfies Definition 4.
Hence we can find graphs G0′ , G1′ such that root(G0′ ) 6=
root(G r ), root(G1′ ) 6= root(G r ), and hC r , G0′ i is 0-valent
while hC r , G1′ i is 1-valent. As we assumed D > 2 it follows that n > 2. We can hence apply Lemma 2 to go
from G0′ to G1′ by adding/removing a single edge at a
time, without ever arriving at a graph that has more
than one root component or has the same root component as G r . Somewhere during adding/removing a single edge, we transition from a graph Gi to a graph Gi+1 ,
by modifying an edge (p → q), where the valency of
C = hC r , Gi i differs from the valency of C ′ = hC r , Gi+1 i.
Nevertheless, Gi and Gi+1 , are applicable to C r because
they are rooted and have a different root component
as G r , hence guarantee the membership of the sequence
in DIAM(D) for any D > 1. However, C and C ′ cannot have a different valency because hC, (S(p))∞
r+1 i ∼p
hC ′ , (S(p))∞
i.
This
is
a
contradiction
and
hence
not
r+1
all round r + 1 configurations can be univalent.

5.

SOLVING CONSENSUS WITH
ROUNDS OF STABILITY

D+1

We now present Algorithm 1, which, under the message adversary ♦STABLED (D + 1), solves consensus if
D and a bound N > n is known a priori. It relies on
an underlying graph approximation algorithm used already in [4,21], which provides each process with a local

estimate of past communication graphs. It is easily implemented on top of any full-information protocol5 and
has been omitted for brevity. As stated in Corollaries 1 and 2 below, the local graph estimates allow to
faithfully detect the existence of root components with
a latency of at most D rounds, with some restrictions.
In our consensus algorithm, processes operate in two
alternating states (“not locked”and “locked”). Basically,
in the “not locked” state, process p tries to find a root
component and, if successful, locks on to it, i.e., considers it a potential base for its decision. This is realized
by adapting the local propp value to the value of the
root component (which is the maximum of the proposal
values of its members) and setting lockedp ← true,
thereby entering the “locked” state. Subsequently, p
waits for contradictory evidence for a period of time
that is long enough to guarantee that every process in
the system has adapted to the value of the root component locked-on by p. If p finds contradictory evidence,
it backs off by leaving the “locked” state through setting
lockedp ← false.
In more detail, p changes its state from “not locked”to
“locked” when it detects a root component via Line 10
that was present D rounds before the current round. In
this case, p enters the locked state by setting lockedp ←
true and propp to prop′ , the maximum value known
to any process of the root component in round r − D,
via Lines 13 and 14. It furthermore records the current
round as ℓ, the so-called lock-round, via Line 15. This is
an optimistic mechanism, i.e., the process “hopes” that
this root component was already the stable root component promised by the adversary. In this sense, the
process starts collecting evidence, possibly contradicting its hope, that stems from the lock-round itself or a
more recent round.
If p finds a root component when it is already in
the “locked” state, i.e, when it is already locked-on to
some root component, it proceeds as follows: First,
p checks whether it detected a relevant change in the
members of the root component since its lock-round
and whether the maximum value, known to the processes of the new root component at the time, is different from its current proposal value. If both checks
succeed, there was enough instability for the process to
conclude that the currently locked-on root component
cannot belong to the stable period; it hence locks-on
to the newly detected root component. If the values remained the same, it puts the current round in a queue of
5
Since we are mainly interested in the solvability aspect of consensus, we consider a full-information protocol where processes forward their entire state in every
round. As will become apparent from the correctness
proof of Algorithm 1, however, it would in fact suffice
to exchange the relevant data structures for the last
N (D + 2N ) rounds at most. Hence, the same engineering improvements as outlined in [21] can be used to get
rid of the simplifying full-information-protocol assumption.

candidate lock-rounds in Line 16. Later, if the process
finds evidence that indeed contradicts its hope (as detailed below), it will pick the next lock round from the
candidate queue via Line 19, and tries to find contradictory evidence from this round on, thereby ensuring that
it cannot miss the promised stable root component.
When p is still in a “locked” state after completing
its root component detection, it searches for contradictory evidence. More precisely, contradictory evidence
means that p learned of another process q s.t. q is not
locked-on to a root component with the same value as
p. This is realized via the guard of Line 17. If p finds
such evidence, it leaves its locked state and enters the
“not locked” state again. A decision occurs when p has
received no contradictory evidence for such a long time
that every other process has seen that p might be in
this situation via Line 21. As we prove in Lemma 4
below, it is guaranteed that if p passes the guard in
Line 22, then every other process has p’s decision value
as its local proposal value forever after. Hence, all future decisions will be based on this value, which leads
the system to a safe configuration.

Correctness proof
We now prove the correctness of Algorithm 1 under
♦STABLED (D + 1). As shown in [21, Lemmas 3 and
4], the simple graph approximation algorithm running
underneath our consensus algorithm allows processes
to faithfully detect root components under certain circumstances. Denoting process p’s round r estimate of
root(G s ) as rootrp (s), the following two key features can
be guaranteed algorithmically (we assume that rootrp (s)
returns {⊥} if p is unsure about its estimate):
Corollary 1. If rootrp (s) 6= {⊥}, then root(G s ) =
rootrp (s). Furthermore, in round r, process p knows the
round s state q s for every q ∈ root(G s ).
We note that Corollary 1 relies critically on the fact
that the graph approximation algorithm maintains an
under-approximation of past communication graphs.
Corollary 2. If (G r )s+D
r=s is R-rooted, then we have
roots+D
(s)
=
R
for
every
process p.
p
Note that Corollary 2 is a consequence of the message
adversary respecting the dynamic diameter D: In round
s + D, for each process q ∈ R, every process received a
message containing q s , the round s state of q.
We are now ready to formally analyze Algorithm 1.
For this purpose, we introduce the useful term of vlocked root component to denote a root component where
all members are v-locked for the same v, i.e., have the
proposal v and are in the locked state.
Definition 8. The round r state pr of p is a v-locked
state if lockedrp = true ∧ proprp = v. R = root(G r ) is
a v-locked root component if all q r with q ∈ R are vlocked.

Algorithm 1: Consensus algorithm, code for process p
Let rq∗ be the last round p heard from q in round r, i.e.,
q ∈ CPrp (rq∗ ) and q ∈
/ CPrp (rq∗ + 1).
1
2
3
4

5

6

7

8

9

10
11
12

13
14
15
16
17

18
19
20
21

22

Initialization:
prop ← xp /* initially, p proposes own input
locked ← true /* p starts ‘locked-on’
ℓ ← 1 /* initialize lock-round to start round
queue ← ∅ /* we assume that max(∅) = 0

*/
*/
*/
*/

Round r computation:
R ← rootrp (r − D)
/* Find all roots that were detected since the
(estimated) start of the stability phase */
T ← {rootrp (i) | max(max(queue), ℓ) − D 6 i 6 r − D}
/* For each process, determine its known states
within the last N rounds:
*/
S ← {q s | q ∈ CPrp (r − N ) ∧ s ∈ [r − N, rq∗ ]}
/* Find the proposal values of the locked-on
processes
of S
*/

S ′ ← propsq | q s ∈ S ∧ lockedsq = true
/* Collect all known states of the last
N (D + 2N ) rounds
*/
S′′ ←
q s | q ∈ CPrp (r − N (D + 2N )) ∧ s ∈ [r − (D + 2N )2 , rq∗ ]
if R 6= {⊥} then
prop′ ← maxq∈R propr−D
q
if locked = false or (prop′ 6= prop and |T | > 1)
then
prop ← prop′
locked ← true
ℓ←r
else if prop′ = prop then add r to queue
if r > ℓ + N and q s ∈ S s.t. lockedsq = false or
prop 6= propsq then
remove all r ′ with r ′ 6 s from queue
if queue 6= ∅ then ℓ ← min(queue)
else locked ← false
if r > ℓ + 2N and S ′ contains single element x 6= prop
then prop ← x
if not yet decided, r = ℓ + N (D + 2N ), and, for all q s
of S ′′ , lockedsq = true and propsq = prop then decide
prop

The following technical lemma is key for the proof of
the agreement property of consensus. It assures that if
a sequence of at least D + 2N communication graphs
occurs in which all root components happen to be vlocked by our algorithm, then all the processes’ proposal
values are v in all subsequent rounds.
Lemma 3. Let σ = (G r )cr=a be a sequence of communication graphs such that, for some fixed value v, every
G r ∈ σ has a v-locked root component and |σ| > D+2N .
Then, for any process p and all rounds r > c, we have
proprp = v.
Proof. Let b = a + D + N − 1 and note that c >
a + D + 2N − 1 = b + N . We prove our lemma using
the invariants I, I ′ that are defined as follows: Ip (r) ⇔

lockedrp = false ∨ proprp = v, Ip′ (r) ⇔ proprp = v. We

use I(r), resp. I ′ (r), to denote that Ip (r), resp. Ip′ (r),
holds for every p ∈ Π.
First, we show I(r) for r ∈ [b, c], by proving that for
any process p, Ip (r) holds. We distinguish two cases.
(1) If p’s lockround ℓ, just before executing Line 17
in round r, satisfies ℓ > r − N , we have that propℓp = v,
because of Corollary 1 and because root(G ℓ−D ) is vlocked. If p modified propp in some round s ∈ [ℓ, r], it
must have done so via Line 13 or Line 21. The former
again means that propsp = v, due to Corollary 1 and
since root(G s−D ) is v-locked by assumption. The latter
means that the guard of Line 21 was passed and hence
s > ℓ + 2N > b + N , which contradicts that s ∈ [ℓ, r] ⊆
[b − N + 1, c].
(2) If ℓ 6 r − N , i.e., r > ℓ + N , because we assume that root(G i ) is v-locked for each G i of (G i )ri=a
and r ∈ [b, c] ⇒ r > a + N , it follows from Lemma 1
that there is a process q and a round s ∈ [r − N, r] s.t.
q ∈ root(G s ), q ∈ CPrp (s), and q s is v-locked. Since
root(G s ) is v-locked by assumption, S contains some
state q s with propsq = v and lockedsq = true. Therefore,
v ∈ S ′r . It follows that if S ′r contains a single element
x, we have x = v. Since Line 21 is the only place in
the code, apart from Line 13, where p assigns a value
to proprp , if propr−1
= v, then proprp = v. On the other
p
r−1
hand, if propp 6= v, because r > ℓ + N , p evaluates
the guard of Line 17 to true. If queue = ∅, p executes
Line 20 and sets lockedrp ← false. If queue 6= ∅, let
ℓ′ = min(queue). Due to Line 18, we have ℓ′ > s, and
because s ∈ [r − N, r], it follows that ℓ′ > r − N >
b − N > a + D − 1. Hence ℓ′ − D ∈ [a, c − D] ⊆ [a, c].
This means that during round ℓ′ , directly after executing Line 11, p already had locked = true ∧ prop = prop′ .
But according to′ Corollary 1, this implies that prop = v,
because root(G ℓ −D ) is v-locked by assumption during
the interval [a, c].
We are now ready to complete the proof by using
induction to show that I ′ (r) holds for each r > c. For
the base case, we prove Ip′ (c) for an arbitrary process p:
If the lockround ℓ of p in round c, just before reaching line 15, satisfies ℓ > c − 2N , we can use the same
arguments as in (1) above: It follows from the assumption that root(G i ) for i ∈ [c − 2N − D + 1, c] ⊆ [a, c]
is v-locked and Corollary 1 that whenever p changes its
proposal value in some round s, we have propsp = v.
Consequently, propcp = v as well.
If ℓ 6 c − 2N , we are in a similar situation as in
(2) above as v ∈ Sp′c . Since Ip (s) holds for s ∈ [b, c],
lockedsq = true implies that propsq = v. Hence, there
can be no x 6= v with x ∈ Sp′c . Therefore, p executes
Line 21 in round c and sets prop ← v, hence propcp = v.
For
V the induction step, we show that, for any process
p, ri=c I ′ (i) ⇒ Ip′ (r + 1). We distinguish three cases:
(1) p assigns a value to prop in round r + 1 in Line 13.
Irrespectively of r, we have propr+1
= v: If r < c + D,
p
r+1−D
this holds because the root of G
is v-locked. If

r > c+ D, we get the result from the fact that I ′ (r − D)
holds.
(2) p assigns a value to prop in round r + 1 in Line 21.
This means that S ′ contains only a single value. Clearly,
for arbitrary rounds r′ , I ′ (r′ ) ⇒ I(r′ ). Therefore, if
Sp′r+1 contains propsq for s > r + 1 − N > b, because
lockedsq = true and I(s) holds, we have propsq = v.
(3) p does not assign a new value to propr+1
p . Then,
propr+1 = v, by the hypothesis that Ip′ (r) holds.
With these preparations, we can now prove agreement, validity and termination of our consensus algorithm.
Lemma 4. Algorithm 1 ensures agreement under each
sequence σ ∈ ♦STABLED (D + 1).
Proof. We show that if a process p decides v in
round r, all future decisions are v as well. A decision v
by p can only occur if p executed Line 22, which means
that Sp′′r contains only states q s with lockedsq = true
and propsq = v. We show below that this implies that
r
there was a sequence σ ′′ ⊆ σ ′ = G i i=r−N (D+2N ) ⊂ σ
s.t. each G i ∈ σ ′′ has a v-locked root component and
|σ ′′ | > D + 2N . We can hence directly apply Lemma 3,
which yields that proptq = v for all q ∈ Π, t > r. This
proves our claim because a decision at process q in round
t can only be on proptq .
We show the contrapositive of the above implication.
Assume there is no sequence σ ′′ ⊆ σ ′ with a common
v-locked root component and |σ ′′ | > D + 2N . Thus, every subsequence σ ′′′ ⊆ σ ′ that has a common v-locked
root component may have at most |σ ′′′ | < D + 2N and
is followed immediately by a communication graph G ri
where some process q ∈ root(G ri ) has lockedrqi = false
or proprqi 6= v. Hence, we have a set G of at least
n such communication graphs during σ ′ . More accurately, there is an ordered set of communication graphs
G = {G r1 , . . . , G rn } with r1 > r−N (D+N ), rn 6 r, and
some set X ⊆ Π of processes such that X ∩ root(G ri ) 6=
∅ for every G ri ∈ G. Thus ∃q ∈ X ∩ root(G ri ) s.t.
lockedrqi = false or proprqi 6= v. By Lemma 1, there
is hence some process q ∈ R and a G ri ∈ G s.t. q ∈
root(G ri ) and q ∈ CPrpn (r1 ) where r1 6 ri 6 rn . Consequently, q ri ∈ Sp′′r , but then there is a state q ri in Sp′′r
with lockedrqi = false or proprqi 6= v.
Lemma 5. Algorithm 1 ensures validity.
Proof. Since decisions are only on values of proprp ,
which are modified exclusively by either assigning propsq
from different processes or input values xi , validity follows.
Lemma 6. Algorithm 1 eventually terminates under
any sequence σ of ♦STABLED (D + 1).
Proof. Since σ ∈ ♦STABLED (D + 1), there is an
earliest subsequence σ ′ = (G r )br=a ⊂ σ with |σ ′ | = D +1
that has a common root R. Let v = maxq∈R propaq .

We prove that in any round r > b, all processes are
v-locked and have ℓb 6 b. This implies the lemma, because, by Line 9, in round b+N (D +2N ), S ′′b+N (D+2N )
contains only v-locked states. Hence, any process that
has not decided yet in round b+N (D +2N ) will execute
Line 22 and decide v.
In order to prove this, we introduce the invariants
Jp (r) ⇔ lockedrp = true ∧ proprp = v ∧ (ℓrp = b ∨ b ∈
queuerp ) ∧ ℓrp 6 b and J (r) ⇔ ∀p ∈ Π : Jp (r), which
state that, at the end of round r, p, resp. every process
of Π, is v-locked and either p’s lock-round is b or b is
queued at p. We
Vr use induction to show that for all r > b
it holds that i=b J (r) ⇒ J (r + 1).
For the base case, we show that Jp (b) for any p ∈ Π.
According to Corollary 2, in round b, every process p
has rootbp (a) = R and the guard of Line 10 is evaluated
to true. We distinguish two cases:
(1) p is not v-locked at the beginning of its round b
computation, i.e., lockedb−1
= false or propb−1
6= v.
p
p
b−1
If lockedp = false, clearly Lines 13, 14, and 15 are
executed. If propb−1
6= v, because σ ′ is the first subp
sequence with the desired properties by assumption,
root(G a−1 ) 6= R. According to Corollary 1, R′ = rootbp (a−
1) 6= R, thus, by construction of T , we have R′ , R ∈
T with R′ 6= R and hence |T | > 1. Since we as6= v = prop′p , also in this subcase,
sumed that propb−1
p
Lines 13, 14, and 15 are executed. Before executing
Line 17, we hence have ℓp = b and therefore none of the
subsequent guards can be triggered. Consequently, we
have that p is still v-locked at the end of its round b
computation and ℓbp = b.
(2) If p is already v-locked at the end of round b−1, we
have ℓb−1
< b and p executes Line 16 in round b, thereby
p
adding b to queuep . Since ℓ is not modified later, ℓbp < b.
If p does not enter the guard of Line 17, Jp (b) holds before p executes Line 21. Otherwise, queuep still contains
b. Since now only states q s with s < b are known to p,
Line 18 cannot remove b from queuep . Hence, the guard
of Line 19 is true and Jp (b) still holds before p executes
Line 21.
Since we assume that p was already v-locked at the
end of round r, this continues to hold also in the case
when Line 21 is ever executed: Since v ∈ S ′ , it must be
the case that if S ′ indeed contains a single value x, then
x = v. Therefore, Jp (b) holds at the end of round b as
asserted.
Vr
For the induction step, we assume that i=b J (r) is
true for some r > b and show that then Jp (r + 1) holds
for an arbitrary process p.
We first show that, if p enters Line 10, it cannot pass
the conditional of Line 12. For this, let us distinguish
two cases:
(1) For r ∈ [b, b + D], J (r) implies that either b = ℓrp
or b ∈ queuerp and p is v-locked at the end of round
r. Thus, in round r + 1, Line 12 can only be passed
if |T | > 1. Since obviously max(queue) < r and we
assumed that r ∈ [b, b + D], by the construction of T

in Line 6, T ⊆ {rootrp (i) | a 6 i 6 b}. In fact, T ⊆
{root(G i ) | a 6 i 6 b} ∪ {⊥}, as a consequence of
Corollary 2. By the assumption that σ ′ is R-rooted,
after its construction in round r, T = {R} and Line 12
cannot be entered.
(2) For r > b + D + 1, by the induction hypothesis
J (r + 1 − D) holds. Thus, lockedrp = true and for
any process q, propr−D
= v, which implies prop′p = v.
q
Therefore, the guard of Line 12 cannot be passed.
Note that, by the hypothesis Jp (r), ℓr+1
6 b, since
p
Line 12 was not passed and ℓ is not modified after this
point.
Until now we have shown that Jp (r + 1) holds right
before p executes line Line 17. We again distinguish two
cases:
Vr(1) If ℓ > b, it follows from the induction hypothesis
i=b J (i) that all states from round ℓ to round r are
v-locked and hence S cannot contain any state that is
not v-locked. Consequently, p cannot pass the guard of
Line 17.
(2) If, on the other hand, ℓ < b, the hypothesis J (r)
implies that b ∈ queuep . Therefore, if the guard of
Line 17 is true, Line 19 is executed and Line 20 cannot be entered.
In both cases Jp (r + 1) still holds before p reaches
Line 21.
Observe that, according to the induction hypothesis
J (r), p was v-locked at the end of round r. Hence,
v ∈ S ′ , and if S ′ contains a single element x, it must
be that x = v. Hence Jp (r + 1) also holds if p executed
Line 21. Since Line 22 cannot not invalidate Jp (r + 1)
either, we are done.
Lemmas 4, 5, and 6 yield the correctness of Algorithm 1:
Theorem 3. Algorithm 1 correctly solves consensus
under ♦STABLED (D + 1), provided N > n.

6.

SOLVING CONSENSUS FOR LONG
PERIODS OF EVENTUAL STABILITY

While the ability to solve consensus under short-lived
periods of stability is beneficial in terms of assumption
coverage and fast termination, it comes at the price
of the rather involved Algorithm 1. In this section,
we show that a (considerably) longer period of stability facilitates a (considerably) simpler algorithm. More
specifically, we show that, for ♦STABLED (x) with x >
3n − 3, a simple consensus algorithm can be obtained
by adopting existing algorithmic techniques [8]. Unfortunately, though, this approach does not work for
x < 3n − 3.
With Σ representing all possible communication graph
sequences, let NON-SPLIT be defined as those σ ∈ Σ
for which the following holds: If G r ∈ σ, then for all
p, q ∈ G r , there is some q ′ ∈ G r such that (q ′ → p) ∈ G r
and (q ′ → q) ∈ G r . Furthermore, let ♦UNIFORM represent those sequences where there is a round r and a set

S
P of processes s.t. G r = p∈P S ′ (p), with S ′ (p) denoting the star graph with central node p and no self-loops
in the non-center nodes. Finally, let ♦STAR(y) be the
set of those σ ∈ Σ that contain a subsequence σ ′ ⊆ σ,
|σ ′ | > y, with a stable root component R satisfying
S
′
r
r
′
p∈R S (p) ⊆ G for each G ∈ σ .
Note that the definition of ♦UNIFORM is such that
if (q → q) ∈ G r then q ∈ P , i.e., processes outside of P
cannot have any outgoing edges (including self-loops).
This restriction does not hold for ♦STAR(y), however,
which is hence a strictly stronger adversary for y = 1,
i.e., ♦STAR(1) ⊃ ♦UNIFORM.
Given a sequence σ = (G i )i>0 , let the compound sequence σ̃ = (G̃ i )i>0 be the sequence of graphs G˜r =
G (r−1)(n−1)+1 ◦ · · · ◦ G r(n−1) . We recall from [7, Lemma
4] that if σ ∈ ROOTED then σ̃ ∈ NON-SPLIT.
Since the compound graphs G˜r combine n consecutive
graphs G r in fixed (ascending) order, this construction is
not necessarily aligned with the R-rooted subsequence
provided by ♦STABLED (y). Let σ̃ be the compound
sequence of some σ ∈ ♦STABLED (y). In the worst case,
σ̃ may contain a sequence of only ⌊ y−n+1
n−1 ⌋ compound
S
′
r
˜
graphs G with the property p∈R S (p) ⊆ G˜r , i.e., σ̃ ∈
♦STAR(⌊ y−n+1
n−1 ⌋).
From [8, Theorem 5], we know that consensus can
be solved under NON-SPLIT ∩ ♦UNIFORM. On the
other hand, our impossibility result Theorem 2 (for D =
n − 1), implies that consensus is impossible under the
adversary NON-SPLIT ∩ ♦STAR(1). Note carefully that
we can allow the R-rooted subsequence to be aligned
with the compound graph construction here, hence the
impossibility for ♦STAR(1).
Consequently, for i < 3, using compound graphs does
not provide a solution for ROOTED∩♦STABILITY(i(n−
1)), as σ ∈ ROOTED ∩ ♦STABILITY(i(n − 1)) implies
only σ̃ ∈ ♦STAR(i − 1) ∩ NON-SPLIT according to the
considerations above. For i > 3, however, we have that
σ̃ ∈ ♦STAR(2) ∩ NON-SPLIT, which allows us to derive
a simple consensus algorithm Algorithm 2 by combining the detection of root components with the uniform
voting algorithm from [8, Algorithm 5].
Theorem 4. Algorithm 2 solves Consensus under the
adversary ♦STAR(2) ∩ NON-SPLIT.
Proof. If process q is the first to decide v, at the end
of round r, then every process has propr = v: Since q
received only messages (v, ∗) with v 6= ⊥ and G r is nonsplit, any process p received a message (v, ∗). Moreover
no message with (v ′ , ∗) and v ′ 6= v was sent in round r,
because every message with some m 6= ⊥ was generated
based on the root of round r − 1 which is, if detected by
a process, detected consistently on every process. Hence
during the round r computation, every process sets prop
to v either via line 13 or line 18. As all future decisions
are based on v, this ensures agreement.
Termination occurs at the latest when the two successive graphs G, G′ of ♦STAR(2) occur in rounds r′ ,

Algorithm 2: Compound graph algorithm, code for
process p
1
2

3
4

5
6
7
8
9
10
11
12

13
14
15

16
17
18
19
20
21

Initialization:
prop ← xp
m←⊥
Transmit round r messages:
Send (m, prop) to all q with (p → q) ∈ G r
Receive (mq , propq ) from all q with (q → p) ∈ G r
Perform
S round r computation until decision:
M ← (q→p)∈G r (q, mq , propq )
r
Rr−1
S ← rootp (r − 1)
if (q,mq ,prop )∈M mq = {v} with v 6= ⊥ then
q
prop ← v
m←v
decide v
else if Rr−1 6= ∅ then
if q ∈ Rr−1 with (q, mq , propq ) ∈ M s.t. mq 6= ⊥
then
prop ← mq
else
prop ← max{propq | (q, mq , propq ) ∈ M, q ∈
Rr−1 }
m ← prop
else if (q, mq , propq ) ∈ M with mq 6= ⊥ then
prop ← mq
m←⊥
else
m←⊥

r′ + 1: In round r′ + 1, every process detects R, the root
component of G and sets prop = v, where v is uniquely
determined by R. Subsequently, any process sends and
receives only messages (∗, v).

7.

CONCLUSIONS

We provided tight upper and lower bounds for the
solvability of consensus under message adversaries that
guarantee a stable root component only eventually and
only for a short period of time: We showed that consensus is solvable if and only if each graph has exactly
one root component and, eventually, there is a period
of at least D + 1 consecutive rounds (with D 6 n− 1 denoting the number of rounds required by root members
for broadcasting) where the root component remains
the same. We also provided a matching consensus algorithm, along with its correctness proof. While this kind
of short-lived periods of stability is useful from the perspective of assumption coverage in real systems and fast
termination time, we also demonstrated that longer periods of stability allow the development of less complex
algorithms.

8.

REFERENCES

[1] Ieee 802.11 standard: Wireless lan medium access
control (mac) and physical layer (phy)
specifications, June 2007. IEEE Computer Society
LAN MAN Standards Committee.
[2] Y. Afek and E. Gafni. Asynchrony from
synchrony. In D. Frey, M. Raynal, S. Sarkar,
R. Shyamasundar, and P. Sinha, editors,
Distributed Computing and Networking, volume
7730 of Lecture Notes in Computer Science, pages
225–239. Springer Berlin Heidelberg, 2013.
[3] M. Biely, P. Robinson, and U. Schmid. Agreement
in directed dynamic networks. In Proceedings 19th
International Colloquium on Structural
Information and Communication Complexity
(SIROCCO’12), LNCS 7355, pages 73–84.
Springer-Verlag, 2012.
[4] M. Biely, P. Robinson, U. Schmid, M. Schwarz,
and K. Winkler. Gracefully degrading consensus
and k-set agreement in directed dynamic
networks. In Revised selected papers Third
International Conference on Networked Systems
(NETYS’15), Springer LNCS 9466, pages
109–124, Agadir, Morocco, 2015. Springer
International Publishing.
[5] M. Biely, P. Robinson, U. Schmid, M. Schwarz,
and K. Winkler. Gracefully degrading consensus
and k-set agreement in directed dynamic
networks. Research Report TUW-258404,
Technische Universität Wien, Institut für
Technische Informatik, Treitlstr. 1-3/182-2, 1040
Vienna, Austria, 2016.
http://publik.tuwien.ac.at/files/publik 258404.pdf
(submitted to TCS).
[6] M. Biely, U. Schmid, and B. Weiss. Synchronous
consensus under hybrid process and link failures.
Theoretical Computer Science, 412(40):5602 –
5630, 2011.
http://dx.doi.org/10.1016/j.tcs.2010.09.032.
[7] B. Charron-Bost, M. Függer, and T. Nowak.
Approximate consensus in highly dynamic
networks: The role of averaging algorithms. In
M. M. Halldòrsson, K. Iwama, N. Kobayashi, and
B. Speckmann, editors, Automata, Languages,
and Programming, volume 9135 of Lecture Notes
in Computer Science, pages 528–539. Springer
Berlin Heidelberg, 2015.
[8] B. Charron-Bost and A. Schiper. The Heard-Of
model: computing in distributed systems with
benign faults. Distributed Computing,
22(1):49–71, Apr. 2009.
[9] É. Coulouma, E. Godard, and J. G. Peters. A
characterization of oblivious message adversaries
for which consensus is solvable. Theor. Comput.
Sci., 584:80–90, 2015.
[10] C. Delporte-Gallet, H. Fauconnier, R. Guerraoui,
V. Hadzilacos, P. Kouznetsov, and S. Toueg. The

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

weakest failure detectors to solve certain
fundamental problems in distributed computing.
In Proceedings of the 23rd ACM Symposium on
Principles of Distributed Computing (PODC’04),
pages 338–346. ACM Press, 2004.
M. J. Fischer, N. A. Lynch, and M. S. Paterson.
Impossibility of distributed consensus with one
faulty process. Journal of the ACM,
32(2):374–382, Apr. 1985.
W. Kiess and M. Mauve. A survey on real-world
implementations of mobile ad-hoc networks. Ad
Hoc Netw., 5(3):324–339, Apr. 2007.
F. Kuhn, N. A. Lynch, and R. Oshman.
Distributed computation in dynamic networks. In
STOC, pages 513–522, 2010.
F. Kuhn, R. Oshman, and Y. Moses. Coordinated
consensus in dynamic networks. In Proceedings of
the 30th annual ACM SIGACT-SIGOPS
symposium on Prin ciples of distributed
computing, PODC ’11. ACM, 2011.
F. Legendre, T. Hossmann, F. Sutton, and
B. Plattner. 30 years of wireless ad hoc
networking research: What about humanitarian
and disaster relief solutions? What are we still
missing? In International Conference on Wireless
Technologies for Humanitarian Relief (ACWR
11), Amrita, India, 2011. IEEE.
M. Maróti, B. Kusy, G. Simon, and A. Lé deczi.
The flooding time synchronization protocol. In
Proceedings of the 2Nd International Conference
on Embedded Networ ked Sensor Systems, SenSys
’04, pages 39–49, New York, NY, USA, 2004.
ACM.
D. Pfleger and U. Schmid. A framework for
connectivity monitoring in wireless sensor
networks. In Proceedings 10th International
Conference on Sensor Technlogies and
Applications (SENSORCOMM’16), pages 40–48.
IARIA, 2016.
M. Raynal and J. Stainer. Synchrony weakened by
message adversaries vs asynchrony restricted by
failure detectors. In Proceedings ACM Symposium
on Principles of Distributed Computing
(PODC’13), pages 166–175, 2013.
N. Santoro and P. Widmayer. Time is not a
healer. In Proc. 6th Annual Symposium on Theor.
Aspects of Computer Science (STACS’89), LNCS
349, pages 304–313, Paderborn, Germany, Feb.
1989. Springer-Verlag.
U. Schmid, B. Weiss, and I. Keidar. Impossibility
results and lower bounds for consensus under link
failures. SIAM Journal on Computing,
38(5):1912–1951, 2009.
M. Schwarz, K. Winkler, and U. Schmid. Fast
consensus under eventually stabilizing message
adversaries. arXiv:1508.008516, August 2015. in
Proc. ICDCN’16).

[22] M. Schwarz, K. Winkler, and U. Schmid. Fast
consensus under eventually stabilizing message
adversaries. In Proceedings of the 17th
International Conference on Distributed
Computing and Networking, ICDCN ’16, pages
7:1–7:10, New York, NY, USA, 2016. ACM.
[23] M. Schwarz, K. Winkler, U. Schmid, M. Biely,
and P. Robinson. Brief announcement: Gracefully
degrading consensus and k-set agreement under
dynamic link failures. In Proceedings of the 33th
ACM SIGACT-SIGOPS Symposium on Principles
of Distributed Computing, PODC ’14, pages
341–343, New York, NY, USA, 2014. ACM.
[24] J.-P. Sheu, C.-M. Chao, and C.-W. Sun. A clock
synchronization algorithm for multi-hop wireless
ad hoc networks. In 24th International Conference
on Distributed Computing Systems, 2004.
Proceedings., pages 574–581, 2004.

