# Efficient Distributed Computations in Anonymous Dynamic Congested Systems
with Opportunistic Connectivity ††thanks: This work was partially supported by
Pace University SRC grant and Kenan fund.

Dariusz R. Kowalski
Augusta University,
Augusta, GA, USA,
<EMAIL_ADDRESS>Miguel A. Mosteiro
Pace University,
New York, NY, USA.
<EMAIL_ADDRESS>
###### Abstract

In this work we address the question of efficiency of distributed computing in
anonymous, congested and highly dynamic and not-always-connected
networks/systems. More precisely, the system consists of an unknown number of
anonymous nodes with congestion on links and local computation. Links can
change arbitrarily from round to round, with only limitation that the union of
any $\mathcal{T}$ consecutive networks must form a temporarily connected
(multi-)graph on all nodes (knowledge of $\mathcal{T}$ is the only information
the nodes require, otherwise the communication would not be feasible). Nodes
do not have any IDs, only some number $\ell$ of them have a bit distinguishing
them from nodes without such a bit. In each round a node can send and receive
messages from its current neighbors. Links and nodes are congested, in the
sense that the length of messages and local cache memory for local computation
is (asymptotically) logarithmic.

All-to-all communication is a fundamental principle in distributed computing –
it assumes that each node has an input message to be delivered to all other
nodes. Without loss of generality, the size of each input message is
logarithmic to fit in the link and node congestion assumption; otherwise, they
could be split in logarithmic batches and considered one-by-one. Because of
anonymity, each node needs to receive only a set of all input messages, each
accompanied by a number of initiating nodes (message multiplicity). We prove
that this task can be done in time polynomial in the (initally unknown) number
of nodes $n$ and in the lower bound on the isoperimetric numbers of
dynamically evolving graphs. This allows to efficiently emulate a popular
Congested Clique model on top of Anonymous Dynamic Congested Systems (ADCS)
with Opportunistic Connectivity, even if the number of nodes may arbitrarily
change in the beginning of emulation.

##  1 Introduction

The Congested Clique [40] is a standard synchronous message passing model of
distributed computation. In such model there are $n$ labeled nodes that
synchronously, in _rounds_ , communicate among them. In each round, each node
may send a message of $O(\log n)$ bits to each of the other nodes and perform
some local computations. Performance is measured in rounds of communication.
But can we efficiently run Congested Clique algorithms if the nodes are
anonymous (e.g., for the sake of privacy), of restricted capacity (e.g.,
logarithmic local memory) and their number is unknown? Even more, what if
links may be available only occasionally, depending on an adversarial
schedule, and the only necessary requirement is that the union of any
$\mathcal{T}$ consecutive networks, for some known parameter $\mathcal{T}$,
forms a temporally connected multi-graph? Could deterministic distributed
computing on such Congested Clique be made efficient? In this work we address
and answer this question in the affirmative by presenting an All-to-all
Communication algorithm to emulate one round of Congested Clique under a harsh
Dynamic Network model that includes all those restrictions.

Distributed computations in the Congested Clique model have attracted a lot of
attention recently [4, 8, 9, 16, 17, 21, 23, 27, 28, 29, 30, 32, 39, 48, 50,
22], the reason being that all-to-all communication is becoming a frequent
feature of modern distributed systems. However, algorithms developed for such
environments are not compatible with many systems where not all nodes are
directly connected. Thus, in order to apply the wealth of Congested Clique
research to those systems, protocols to emulate a single round of all-to-all
communication in congested multi-hop networks are needed.

System restrictions may go far beyond multi-hop communication. Indeed, in some
environments network connectivity may be highly dynamic due to mobility or
unreliability (e.g. Dynamic Networks [36, 25, 38]). Also, node identifiers may
not be feasible in massive low-cost platforms, or one may not want to reveal
the identifiers due to privacy concerns (e.g. Anonymous Dynamic Networks [41,
33, 35, 13, 12]). Additionally, in a system where message size is limited (as
in the Congested Clique) it is natural to apply the same limitation to memory
access, specially when nodes are expected to be low-cost devices (e.g. Weak
Sensor Model [18, 19]).

Following up on the CONGEST model [51], in the Congested Clique nodes
initially know their neighbors. Being a clique implies that they know the
total number of nodes. However, when implementing the Congested Clique in a
multi-hop topology, nodes may not be connected to all other nodes. Moreover,
in face of dynamicity and anonymity, each node does not even know the number
of its neighbors before receiving messages from them. Thus, in this work we
assume that neither the exact number, nor even an upper bound on the total
number of nodes, is initially known. Even more, the network does not need to
be connected at all, as long as a union of $\mathcal{T}$ consecutive networks
is temporally connected, for some given parameter $\mathcal{T}$.

To the best of our knowledge, our Anonymous Dynamic Congested Systems model
described above is the most challenging for distributed computing among the
existing models in the Dynamic Networks literature.

Our Contributions and Approach. In this work, we present a deterministic
protocol to emulate a single round of the Congested Clique on Anonymous
Dynamic Congested Systems (ADCS) with Opportunistic Connectivity. That is, on
systems where nodes lack identifiers, message size and memory access are
limited to $O(\log n)$ bits, where $n$ is the number of nodes (initially
unknown), and the communication network is multi-hop and adversarially
dynamic, allowing even disconnection with some limitations. The overhead
introduced by our emulator is a polynomial function of $n$ and, if known, a
lower bound $i_{min}$ on the isoperimetric numbers of dynamic
networks,111Formally, it is a lower bound on an isoperimetric number of the
product of $\mathcal{T}$ consecutive networks, as defined formally in Section
4.2.  making our bounds tighter for networks with good expansion – more
precisely, the $i_{min}$ in the denominator of the time complexity formula
could be as large as $\Theta(n)$ for networks with good expansion. See Table 1
for details and comparison with most closely related work. We also prove that
the knowledge of the connectivity parameter $\mathcal{T}$ and the number
$\ell$ of distinguished nodes (they have additional distinguishing bit, and
are called _supervisors_ throughout the paper) is necessary for All-to-all
Communication in ADCS with Opportunistic Connectivity. Similarly, using
$o(\log n)$ local memory bits are not enough for All-to-all Communication in
the model.

Ref |  | Known
---
$n$
Connected |  | Message
---
size
| Memory
---
access
IDs | Time complexity
| this
---
work
no | no | $O(\log n)$ | $O(\log n)$ | no | $O\left(\frac{n^{1+2\mathcal{T}(1+\epsilon)}}{\ell i_{\min}^{2}}\log n\log\left(\frac{n}{\ell}\right)+\frac{n^{\prime}}{\ln(1+i_{\min})}\log^{2}n\right)$
[37] | no | yes | $O(\log n)$ | no limit | yes |  | $O(n^{2})$
---
(1-Interval connected)
| no | yes | $O(\log n)$ | no limit | yes |  | $\Omega(n\log n)$
---
(1-Interval connected,
centralized algorithm)
[26] |  | upper
---
bound
yes | $b\geq\log n$ | no limit | yes |  | $O(dn^{2}/b^{2})$
---
($b\geq d\geq\log n$)
Table 1:  Comparison of most relevant deterministic All-to-All Communication
results in Dynamic Networks. Message size and memory access are in bits, and
time complexity is in rounds of communication. $n$ denotes the number of nodes
(initially unknown), $n^{\prime}$ – the number of different input messages,
$\ell$ – the number of nodes with distinguishing bit (supervisors),
$\mathcal{T}$ – the connectivity parameter, $\epsilon>0$ – any chosen
constant, $i_{min}$ – the lower bound on the isoperimetric numbers of the ADCS
as defined in Section 4.2 (if unknown, the formula holds after substituting
$2/n$ for $i_{\min}$). $d$ is the size of the input message in [26].

Our algorithmic approach is not a simple classic gossip-based technique, which
is well-known in Distributed Computing [33, 20, 43, 31, 41, 24]. In such
algorithms initially nodes hold some values to be shared with neighboring
nodes repeatedly until some stopping rule is met. In fact, the ADCS model
yields such techniques incorrect, as multiplicities of the same input message
may not be counted correctly due to anonymity and dynamic behavior of the
underlying networks. Therefore, we combine a spreading-with-stopping technique
with coding messages and distribution of potential, c.f., some of their
applications in less-demanding systems [33, 20, 43]. Combining them in a
carefully selected way results in a complex algorithm, which occurs
surprisingly efficient in very demanding systems such as ADCS with
Opportunistic Connectivity.

One of the critical components of our All-to-All Communication algorithm is
based on distribution of potential. We use it when counting all active nodes
or nodes with an identified input message. The main challenge is to show that
the potential distribution process stabilizes (with negligible deviations at
nodes) at a desired value – unlike a typical mass-distribution process, c.f.,
[55, 2, 43, 54], our process has to accommodate (1) lack of connectivity (only
a union of $\mathcal{T}$ consecutive networks needs to be connected), (2)
truncated potentials (we need to truncate the numbers due to congested
links/nodes), and (3) lack of any knowledge of $n$ (in the beginning).

Roadmap. In Section 2 we discuss the related work. Section 3 presents the
model and useful definitions, while Section 4 states preliminary results on
imposibility of all-to-all communication and properties of dynamic networks.
The main All-to-All Communication algorithm is presented and analyzed in
Section 5, while its major components, Multiplicity and Restricted Methodical
Counting, are given and analyzed in Sections 6 and 7, respectively.

##  2 Related Work

To the best of our knowledge, there is no previous study of distributed
computations under a Dynamic Networks model that include all the restrictions
of Anonymous Dynamic Congested Systems. That is, worst-case dynamicity with
connectivity that is only opportunistic, communication limited to $O(\log n)$
bits per round, local memory access also limited to $O(\log n)$ bits per
round, and nodes without ID’s. We overview in this section the Dynamic
Networks extant work on related models.

Two closely related works on All-to-All Communication in Dynamic Networks are
[37, 26]. In both, the model includes node ID’s, continuous connectivity, and
unbounded memory access. Nevertheless, lower bounds under weaker conditions
apply to the ADCS stricter model. For deterministic algorithms, a lower bound
of $\Omega(n\log n)$ rounds was proved in [37], even for centralized
algorithms.

The most frequent model of worst-case dynamicity still assumes continuous
connectivity. That is, even though the set of links may change arbitrarily
from round to round, it is guaranteed that in every round of communication
there is a path between every pair of nodes. For instance, in the population
protocol model in [1] and the continuous connectivity model in [49]. Later on,
in [37], Kuhn, Lynch and Oshman parameterized the continuous connectivity
assumption in the $T$-interval connectivity model where the topology may
change, but changes are restricted to maintain an underlying connected static
graph over each sequence of $T$ rounds. Instantiating $T=1$ the model is
equivalent to continuous connectivity.

In none of the above models disconnection is allowed, not even temporarily. In
a more recent work [42], Michail, Chatzigiannakis, and Spirakis do consider
disconnections, with limitations that yield opportunistic connectivity.
Specifically, in at most $k$ rounds every node _influences_ at least one other
node that has not been influenced yet (meaning for example that the status of
a node is learned by some other node in at most $k$ rounds). Since the
limitation holds for every node, the model is more restrictive than simply
parameterizing the overhead on dissemination of one message to a factor of
$k\geq 1$. In fact the authors show that for $k=1$ it is not possible to
influence only one node in every round. In the same paper, the authors study a
second model of opportunistic connectivity where communication between
neighboring nodes must be allowed within some time window, but the underlying
topology is fixed. The All-to-all Communication problem is not studied in that
work.

Communication congestion has been thoroughly studied in the Congested Clique
model and others [4, 8, 9, 16, 17, 21, 23, 27, 28, 29, 30, 32, 39, 48, 50,
22], but to the best of our knowledge ours is the first model to combine
communication and memory access congestion.

Finally, with respect to Dynamic Networks with anonymous nodes, the Anonymous
Dynamic Networks (ADN) model has attracted also a lot of attention recently
[41, 33, 35, 13, 14, 15, 12, 44, 10, 34]. A comprehensive overview of work
related to ADNs can be found in a survey by Casteigts, Flocchini,
Quattrociocchi, and Santoro [7]. In all these works continuous connectivity is
assumed.

Other studies also dealing with the time complexity of information gathering
exist [11, 3, 52, 5, 46, 53], but include in their model additional
assumptions, such as the network having the same topology frequently enough or
node identifiers.

##  3 Problem and Model

To emulate a single round of communication in the Congested Clique, we study
the All-to-all Communication problem defined as follows. Initially all nodes
hold an input message, and to solve the problem all nodes must receive the
input message of all other nodes. For each input message initially held by
more than one node, nodes must receive the number of copies of that input
message as well.

We study All-to-all Communication in Anonymous Dynamic Congested Systems
(ADCS) formed by $n$ processing _nodes_. Nodes lack identifiers and the set of
communication links among nodes is adversarially dynamic, with some limits on
disconnection as specified below. When two nodes are able to communicate (that
is, they are the endpoints of a communication link), we say that they are
_neighbors_. We assume that $n$ is initially unknown. Moreover, due to
dynamicity, each ADCS node does not know even the number of its neighbors
before receiving messages from them. That is, a node knows the number of its
neighbors in any one round after receiving messages, but it does not who they
are. Nonetheless, although we refer to the set of neighbors of a node and we
label nodes in the presentation of algorithms and the analysis, we do it only
for the sake of clarity – the nodes have only access to the messages sent by
neighbors. Throughout the paper, references to algorithms lines are given as
$\langle algorithm\\#\rangle.\langle line\\#\rangle$ for succinctness.

Time is discretized in communication _rounds_. In each round of communication,
each node may send a _message_ to all its neighbors (the same to
all222Dynamicity and anonimity prevent the nodes from sending destination-
oriented messages. ), receive messages from all its neighbors, access local
memory, and perform local computations. We evaluate time complexity in rounds
of communication, given that in comparison local memory access and local
computations take negligible time.

Each message is limited to $O(\log n)$ bits, as in the Congested Clique [40]
and CONGEST [51] models. Additionally, each memory access is limited to
$O(\log n)$ bits as well – this is the reason we call nodes congested as well.
Specifically, in each side of a communication link there is an input buffer
and an output buffer, both limited to $O(\log n)$ bits. The additional
internal memory for local computation also holds $O(\log n)$ bits. It implies,
in particular, that a local computation algorithm may process a constant
number of received messages (in their buffers) at a time, aggregating them
somehow in local memory, and continuing with other buffers. (In other words,
in a single round the algorithm may check all messages, but cannot upload them
from the buffers all at once but instead needs to process them in constant
batches). At the end of the round, the algorithm may store some $O(\log
n)$-bit information in external memory, e.g., the learned input message
together with its multiplicity. We show below that this restriction is tight.
That is, if memory access is restricted to $o(\log n)$ bits, some instances of
All-to-all Communication cannot be solved.

We assume the presence of $\ell$ distinguished nodes, called
${{{supervisor}}s}$, where $0<\ell<n$. That is, the set of nodes is
partitioned in two classes: supervisors and supervised nodes. The number of
supervisors $\ell$ is known to all nodes. As we show later, these assumptions
are necessary to solve All-to-all Communication deterministically without
knowing $n$. Within each class, nodes are indistinguishable.

The communication network topology model is a $\mathcal{T}$-connected time-
evolving graph, defined as follows333There are many formalisms in the
literature to specify graphs that change with time. Names include temporal
graphs, dynamic graphs, evolving graphs, time-varying graphs, and others. We
adopt the notation that provides more clarity to our analysis..

Given a fixed set $V$ of $n$ nodes, let a _time-evolving graph_ (or _evolving
graph_ for short) be an infinite sequence of graphs
$\mathcal{G}=\\{G^{(t)}\\}_{t\in\mathbb{N}}$ such that
$G^{(t)}=\left(V,E^{(t)}\right)$, where each $E^{(t)}$ is the (possibly
different) set of links of the graph $G^{(t)}$. We call each $G^{(t)}$ a
_constituent graph_.

For any pair of nodes $u,v\in V$ in an evolving graph $\mathcal{G}$, let an
_opportunistic path_ of length $k>0$ from $u$ to $v$ be a sequence of links
$(x_{1},x_{2}),(x_{2},x_{3}),\dots,(x_{k-1},x_{k})$ where $x_{i}\in V$ for
every $i\in[k]$, $x_{1}=u$, $x_{k}=v$, and for every consecutive pair of links
$(x_{i-1},x_{i}),(x_{i},x_{i+1})$ in the sequence, such that $1<i<k$, if
$(x_{i-1},x_{i})\in E^{(t)}$ and $(x_{i},x_{i+1})\in E^{(s)}$, then it is
$t\leq s$. In words, an opportunistic path from $u$ to $v$ is a path that may
not exist in its entirety at any round, but it can be traversed from $u$ to
$v$ throughout time (sometimes called a _journey_ in the literature).

We say that an evolving graph $\mathcal{G}$ is _$\mathcal{T}$ -connected_ if,
for each $t\geq 0$, for each pair of nodes $u,v\in V$, and for each
consecutive sequence of $\mathcal{T}$ constituent graphs
$G^{(t+1)},\dots,G^{(t+\mathcal{T})}$, there is an opportunistic path from $u$
to $v$. Note that each $G^{(t)}$ may be disconnected, and that we do not
restrict the length of the opportunistic path. As we show later, All-to-all
Communication is not possible in ADCS without knowledge of $\mathcal{T}$.
Thus, we assume that nodes know $\mathcal{T}$.

With respect to the expansion properties of the ADCS network, we consider
three scenarios: no knowledge, knowledge of minimum conductance, and knowledge
of minimum isoperimetric number. The definitions of these expansion
characteristics are given in Section 4.2.

##  4 Preliminaries

###  4.1 Impossibility Results

We start this section establishing some impossibility facts that validate the
assumptions of our model.

######  Observation 1.

For each All-to-all Communication deterministic algorithm $\mathcal{A}$, there
exists an ADCS with $\mathcal{T}$-connected evolving graph topology such that,
if $\mathcal{A}$ does not use $\mathcal{T}$, the problem cannot be solved.

###### Proof.

For the sake of contradiction, assume there exists such algorithm
$\mathcal{A}$. Let $T$ be the worst-case running time of $\mathcal{A}$ on a
$1$-connected ADCS of $n$ nodes. Consider an ADCS with $n+1$ nodes that during
the first $T$ rounds of execution of $\mathcal{A}$ is formed by a clique of
$n$ nodes and an isolated node $v$, which connects to the clique for round
$T+1$. The nodes in the clique are not able to communicate with $v$ during the
$T$ execution steps of $\mathcal{A}$. Hence they stop, but then the All-to-all
Communication problem was not solved (as nodes in the clique do not know the
message of the other node), and the described execution is feasible for
$\mathcal{T}$-connected ADCS, where $\mathcal{T}=T+1$ is unknown to the
algorithm. ∎

######  Observation 2.

There is no deterministic algorithm to solve All-to-all Communication in an
ADCS without at least one distinguished node, and without knowledge of the
total number of nodes $n$ and the number of distinguished nodes $\ell$.

###### Proof.

For the sake of contradiction, assume there exists such algorithm, call it
$\mathcal{A}$. Then, we can use $\mathcal{A}$ to compute $n$ by simply
assigning a message $1$ to each node and counting how many $1$’s are received.
However, this is a contradiction because, even for Anonymous Dynamic Networks
without node and edge congestion it has been shown in [41] that counting the
number of nodes deterministically is not possible without some distinguished
node. It was also shown in [35] that the number of distinguished nodes needs
to be known. ∎

######  Observation 3.

There exist applications of All-to-all Communication where, if memory access
is limited to $o(\log n)$ bits, the problem cannot be solved.

###### Proof.

Consider an All-to-all Communication algorithm used to compute the number of
nodes $n$ in an ADCS, where $n$ is unknown (i.e., each node has initially the
same message $1$). For each $n$ there should be at least one final state of a
node in which the node stops and outputs $n$. On the other hand, nodes with
internal memory $\mu=o(\log n)$ may result in only $2^{\mu}=o(n)$ states;
hence, for some $n$ there will be no terminating state outputting $n$ and the
All-to-all Communication fails. ∎

###  4.2 Expansion in Evolving Graphs with Opportunistic Connectivity

The relevant property that $\mathcal{T}$-connectivity provides to our analysis
is the following.

######  Observation 4.

Given a $\mathcal{T}$-connected evolving graph $\mathcal{G}$, for any sequence
of constituent graphs of $G^{(t+1)},G^{(t+2)},\dots,G^{(t+\mathcal{T})}$,
$t\geq 0$, the union graph
$G_{\cup_{t}}=\left(V,\cup_{i=1}^{\mathcal{T}}E^{(t\mathcal{T}+i)}\right)$ is
connected. 444Notice that the one or more paths between each pair of nodes
$u,v\in V$ in $G_{\cup_{t}}$ are derived from the opportunistic path from $u$
to $v$ and the opportunistic path from $v$ to $u$, which exist due to
$\mathcal{T}$-connectivity.

Consider a $\mathcal{T}$-connected evolving graph $\mathcal{G}$ conceptually
divided in subsequences of $\mathcal{T}$ consecutive constituent graphs. That
is, $\mathcal{G}=\\{\mathcal{G}_{i}\\}_{i=0}^{\infty}$, where
$\mathcal{G}_{i}=\\{G_{i\mathcal{T}+t}\\}_{t=1}^{\mathcal{T}}$. By Observation
4, for each $i\geq 0$, the union graph $G_{\cup_{i}}$ defined on
$\mathcal{G}_{i}$ is connected, whereas each constituent graph of
$\mathcal{G}$ may be not connected. Thus, rather than analyzing the potential
distribution process as a Markov chain on the evolving graph $\mathcal{G}$, we
study the process on the evolving graph
$\mathcal{G^{*}}=\\{G_{\cup_{i}}\\}_{i=0}^{\infty}$, where each constituent
union graph $G_{\cup_{i}}$ is connected. We do so taking into account that, in
fact, each union graph corresponds to a sequence of graphs from $\mathcal{G}$.

The potential distribution process can be seen as a multiplication of a vector
of values, one component for each node, by a matrix of shares, where component
$(u,v)$ corresponds to the fraction of potential shared by node $u$ with
neighboring node $v$. Let $P^{(t)}$ be the matrix of shares used by a gossip-
based algorithm in round $t$ (corresponding to a constituent graph $G^{(t)}$).
Then, for each $i\geq 0$, the matrix of shares corresponding to the potential
distribution on the evolving graph $\mathcal{G}_{i}$ is
$P_{i}=\prod_{t=1}^{\mathcal{T}}P^{(i\mathcal{T}+t)}$. Each $P^{(t)}$ is
doubly stochastic, hence, $P_{i}$ is also doubly-stochastic.

For each $i\geq 0$, consider a time-homogeneous Markov chain $\mathbf{X}_{i}$
with state space $V$ and transition matrix $P_{i}$. $\mathbf{X}_{i}$ is
finite, irreducible and aperiodic, and given that each $G_{\cup_{i}}$ is
connected, it is ergodic. Thus, the stationary distribution of
$\mathbf{X}_{i}$ is unique [47]. The uniform distribution, that is,
$\pi_{v}=1/n$ for all $v\in V$, is a solution of
$\mathbf{\pi}P_{i}=\mathbf{\pi}$ because $P_{i}$ is doubly stochastic. Thus,
the stationary distribution of $\mathbf{X_{i}}$ is uniform.

Classic bounds on mixing time of Markov chains require the transition matrix
to be symmetric [55], but the $P_{i}$’s above may not be. Thus, we apply
instead a bound by Mihail [43] that is applicable to arbitrary irreducible
Markov chains, as long as they are strongly aperiodic (as in our case where
nodes keep at least half of the potential), and it is a function of transition
matrix conductance.

The _conductance_ of a transition matrix $P=\big{(}p_{uv}\big{)}$ of a Markov
chain over state space $V$ with stationary distribution $\mathbf{\pi}$ is
defined as follows:

$\displaystyle\phi(P)=\min_{S\subset V:\sum_{v\in S}\mathbf{\pi}_{v}\leq
1/2}\phi_{P}(S)\ ,\ \ \ \ \ \ \ \ where\ \ \ \ \ \ \ \ \
\phi_{P}(S)=\frac{\sum_{u_{j}\in S}\sum_{u_{h}\in V\setminus
S}w_{u_{j}u_{h}}}{\sum_{v\in S}\mathbf{\pi}_{v}}\ \ \ \ \ \ \ and\ \ \ \ \ \ \
w_{u_{j}u_{h}}=\pi_{u_{j}}p_{u_{j}u_{h}}\ .$

We instantiate this definition on $P_{i}=\big{(}p_{uv}\big{)}$ and
$\mathbf{\pi}=\frac{\mathbf{I}}{n}$ as follows:

$\displaystyle\phi(P_{i})=\min_{S\subset V:|S|\leq n/2}\phi_{P_{i}}(S)\ ,\ \ \
\ \ \ \ \ \ \ \ where\ \ \ \ \ \ \ \ \ \ \ \ \
\phi_{P_{i}}(S)=\frac{1}{|S|}\sum_{u_{j}\in S}\sum_{u_{h}\in V\setminus
S}p_{u_{j}u_{h}}\ .$

######  Theorem 1.

(derived from Theorem 3.1 in [43].) For an irreducible strongly aperiodic
Markov chain $\mathbf{X}_{i}$ with state space $V$, such that $|V|=n$, with a
unique uniform stationary distribution and transition matrix $P_{i}$, it is

$\displaystyle\left|\left|\mathbf{\Pi}_{t+1}-\frac{\mathbf{I}}{n}\right|\right|_{2}^{2}$
$\displaystyle\leq\left(1-\phi(P_{i})^{2}\right)\left|\left|\mathbf{\Pi}_{t}-\frac{\mathbf{I}}{n}\right|\right|_{2}^{2}\
.$

Where $\mathbf{\Pi}_{t}$ is the distribution after $t\geq 0$ steps of
$\mathbf{X}_{i}$.

Notice that the above analysis applies to each $i\geq 0$. That is, each
$P_{i}$ may be different for each $\mathcal{G}_{i}$, but all of the
$\mathbf{X_{i}}$ converge to a uniform stationary distribution and the bounds
in Theorem 1 apply to each $\mathbf{X_{i}}$. Thus, by application of these
bounds to each sequence of $\mathcal{T}$ rounds, the convergence time for the
evolving graph $\mathcal{G}$ can be obtained.

We define the minimum conductance $\phi_{\min}$ corresponding to the
transition matrices $P_{i}=\prod_{t=1}^{\mathcal{T}}P^{(i\mathcal{T}+t)}$ used
by our algorithms on the evolving graph topology $\mathcal{G}$ as follows:

$\phi_{\min}=\min_{i=0,1,2,\dots}\phi(P_{i})\ .$

Conductance is a useful expansion characteristic to provide tighter time
bounds, but being a function of the probabilities of transition it is specific
for each algorithm. To obtain bounds that depend on network characteristics
only, we will use the isoperimetric number.555The isoperimetric number of a
graph (a.k.a. graph Cheeger constant) is the discrete analogue of the Cheeger
isoperimetric constant, c.f., [6]. The isoperimetric number of a static graph
$G=(V,E)$ is defined as follows:

$\displaystyle i(G)=\min_{X:|X|\leq|V|/2}\frac{|\partial X|}{|X|}\ ,$

where $\partial X$ denotes the set of links of $G$ that have one end in $X$
and the other end in $V\setminus X$. We apply this definition to each
constituent union graph $G_{\cup_{j}}$ of the evolving graph
$\mathcal{G^{*}}=\\{G_{\cup_{j}}\\}_{j=0}^{\infty}$, and obtain:

$\displaystyle i(G_{\cup_{j}})=\min_{X:|X|\leq|V|/2}\frac{|\partial
X|}{|X|}\text{\ \ for each }j=0,1,\dots\ \ \ \ \ \ \ \ \ \ \ \ \text{ and then
}\ \ \ \ \ \ \ \ \ \ \ \ \ i_{\min}=\min_{j=0,1,2,\dots}i(G_{\cup_{j}})\ .$

The following relation between conductance and isoperimetric number will be
used. For each $P^{(t)}$, let each non-zero entry be at least $1/d$ for some
$d>0$. Given that $P_{j}=\prod_{t=1}^{\mathcal{T}}P^{(j\mathcal{T}+t)}$, we
have that each non-zero entry of $P_{j}$ is at least $1/d^{\mathcal{T}}$.
Thus, for each $j=0,1,\dots$ we have

$\displaystyle\phi(P_{j})$ $\displaystyle\geq\min_{X\subset
V:|X|\leq|V|/2}\frac{1}{|X|}\sum_{u_{i}\in X}\sum_{u_{j}\in V\setminus
X}\frac{1}{d^{\mathcal{T}}}=\frac{1}{d^{\mathcal{T}}}\min_{X\subset
V:|X|\leq|V|/2}\frac{|\partial
X|}{|X|}=\frac{i(G_{\cup_{j}})}{d^{\mathcal{T}}}\ .$ (1)

##  5 All-to-all Communication

Assume each node $v\in V$ has an input message to send to every other node
consisting of at most $\ell_{v}\leq\lceil\log n\rceil$ bits (recall that $n$
is unknown to nodes, but this is only an upper bound on the input message
length). This length could be scaled by any constant $c>0$ w.l.o.g. The set of
neighbors $N$ and nodes are labeled only for presentation, but nodes do not
have and do not use such knowledge; instead, they can only send and receive
messages to/from them, see the pseudo-codes.

Our All-to-All Communication Algorithm 1 starts with counting the number of
participants $n$ using the Restricted Methodical Counting algorithm (refer to
Section 7), and then proceeds in subsequent epochs. Each epoch is dedicated to
finding a new input message (see the Discovery Part) and counting how many
copies of this input message are at nodes (see the Processing Part). The
Discovery Part proceeds in phases. Each phase parameterized by $index$
corresponds to the discovery of the $index$ bit of some input message, whose
first $index-1$ bits have been discovered in preceding phases (but of an input
message not been discovered and counted in previous epochs). This discovery is
done by spreading and updating variables $match1$ at each node, and if no node
is discovered, then spreading and updating variables $match0$. The phases’
parameter $index$ is numbered from $1$ to $\lceil\log n\rceil$ (the latter
being an upper bound on the input message’s length). In each phase, a
sufficiently long broadcast is run to update information on whether the
$index$ bit being matched is 1 or 0. The length of the broadcast
$r^{\prime}=\lceil\mathcal{T}\ln n/\ln(1+i_{\min})\rceil$ is a bound on
temporal diameter of the evolving graph $\mathcal{G^{*}}$ based on the
initially computed $n$, the connectivity parameter $\mathcal{T}$, and, if
known, a bound $i_{\min}$ on the isoperimetric number, which otherwise can be
lower bounded by a function of $n$ (refer to the first line in Algorithm 1 and
Section 4.2). Nodes whose input messages have been discovered in previous
epochs, or whose input message does not match the bits already discovered in
the current epoch (which is encoded by setting the variable $match$ to
$false$) only forward the received information in the main algorithm and the
procedure Multiplicity (see Algorithm 2 in Section 6) run in the Processing
Part. All nodes whose input message has been discovered (and so, also
delivered to all nodes) in the Discovery Part of the current epoch (which is
encoded by setting the variable $delivered$ to $true$) are counted using the
procedure Multiplicity by all nodes. The output – the discovered input message
and its multiplicity – is stored in external storage at the end of the epoch.
The algorithm finishes when no new input message is discovered.

$n\leftarrow$ Restricted Methodical Counting ()

// Counting n

$delivered\leftarrow false$

// Own input message not delivered yet

1 while  _true_ do // Iterating Epochs -- as long as there are undelivered
input messages

$match\leftarrow\lnot delivered$

// $match$ will indicate if discovered bits match own input message

// Discovery Part

2 $new\ {input\ message}\leftarrow$ empty string of bits

3 for  _$index\leftarrow 1$ to $\lceil\log n\rceil$_ do // Iterating Phases --
from most to least significant bit

4 $bit\leftarrow$ extract bit $index$ from ${input\ message}$

$match0\leftarrow match\land(bit=0)$

// Indicates matching so far, with 0 in $index$ bit

$match1\leftarrow match\land(bit=1)$

// Indicates matching so far, with 1 in $index$ bit

5 for  _$round\leftarrow 1$ to $r^{\prime}$_ do // Broadcasting $match1$

Send $\langle match1\rangle$ and Receive $\langle match1_{v}\rangle,\forall
v\in N$

// To/from neighbors in $N$

$match1\leftarrow\bigvee_{v\in N}match1_{v}\lor match1$

// Incorporating neighbors’ knowledge about $match1$

6

7 if  _$match1=true$_ then // Discovered $index$ bit 1

8 append ${}^{\prime}1^{\prime}$ to $new\ {input\ message}$

9 if  _$bit=0$_ then $match\leftarrow false$

10

11 else

12 for  _$round\leftarrow 1$ to $r^{\prime}$_ do // Broadcasting $match0$

Send $\langle match0\rangle$ and Receive $\langle match0_{v}\rangle,\forall
v\in N$

// To/from neighbors in $N$

$match0\leftarrow\bigvee_{v\in N}match0_{v}\lor match0$

// Incorporating neighbors’ knowledge on $match0$

13

14 if  _$match0=true$_ then // Discovered $index$ bit 0

15 append ${}^{\prime}0^{\prime}$ to $new\ {input\ message}$

16 if  _$bit=1$_ then $match\leftarrow false$

17

18 else return

19 // No more matches, all input messages delivered

20

// Processing Part

21 if  _$match=true$_ then $delivered\leftarrow true$

22 // Own input message was delivered in this epoch $count\leftarrow$
Multiplicity ($new\ {input\ message}$)

output $\langle new\ {input\ message},count\rangle$

// Move newly discovered info to external storage

23

Algorithm 1 All-to-All Communication algorithm for each node. ${input\
message}$ is the input message initially held by this node. $N$ is the set of
neighbors of this node in the current round – the node does not know them, but
can send and receive short messages to/from them.
$r^{\prime}=\lceil\mathcal{T}\ln n/\ln(1+i_{\min})\rceil$ as in Lemma 1, where
$i_{\min}$ is the minimum isoperimetric number of the evolving graph topology
as defined in Section 4.2.

###  5.1 Analysis of All-to-All Communication

In this section we present the main theorem of this work, showing the
correctness and running time of our All-to-All Communication algorithm. For
the purpose of the analysis, we conceptually divide time into blocks of
$\mathcal{T}$ rounds. The analysis of Restricted Methodical Counting ( ) and
Multiplicity ( ) is included in the sections that follow. The following lemma
will be used.

######  Lemma 1.

Consider an ADCS with a $\mathcal{T}$-connected evolving graph topology with
$n$ nodes, each holding a true/false value. Then, if all nodes broadcast true
values (initially held or received from others) for at least
$r^{\prime}=\mathcal{T}\ln n/\ln(1+i_{\min})$ rounds, all nodes know whether
there was initially some true value in the system or not.

###### Proof.

Let $\\{S_{i},V\setminus S_{i}\\}$ be a partition of the set of nodes at the
beginning of some block $i$ with transition matrix
$P_{i}=\prod_{t=1}^{\mathcal{T}}P^{(i\mathcal{T}+t)}$. By definition of
isoperimetric number (refer to Section 4.2) we know that
$i_{\min}\leq|\partial S_{i}|/|S_{i}|$. That is, the number of links crossing
the partition $\\{S_{i},V\setminus S_{i}\\}$ is larger than $|S_{i}|i_{\min}$.
Hence, adding a 1-hop neighbourhood to any initial subset of nodes $|S_{i}|$,
the new subset at the beginning of block $i+1$ is such that
$|S_{i+1}|\geq(1+i_{\min})|S_{i}|$.

Consider any node that did not receive true yet, call it $x$, and let
$S_{i}=\\{x\\}$. The question of how many blocks are needed for $x$ to receive
a true (if there is any) is equivalent to ask what is the minimum $t$ such
that the $t$-hop neighbourhood of $x$ (in the evolving graph) includes all
nodes. That is, we want to find what is the minimum $r^{\prime}$ such that
$(1+i_{\min})^{r^{\prime}}\geq n$. Manipulating the latter equation, and
taking into account that each block has $\mathcal{T}$ rounds, the claimed
$r^{\prime}=\mathcal{T}\ln n/\ln(1+i_{\min})$ follows. ∎

######  Theorem 2.

Consider an ADCS with a $\mathcal{T}$-connected evolving graph topology,
$\mathcal{T}\in O(1)$, with minimum isoperimetric number $i_{\min}$, formed by
$\ell\geq 1$ supervisor nodes and $n-\ell$ supervised nodes, $n\geq 2$, each
holding an input message, running the All-to-All Communication algorithm.
Then, the All-to-all Communication problem is solved in

$O\left(\frac{n^{1+2\mathcal{T}(1+\epsilon)}}{\ell i_{\min}^{2}}\log
n\log\left(\frac{n}{\ell}\right)+\frac{n^{\prime}}{\ln(1+i_{\min})}\log^{2}n\right)\textrm{
rounds,}$

where $n^{\prime}\leq n$ is the number of different input messages.

###### Proof.

The correctness of Restricted Methodical Counting ( ) and Multiplicity ( ) is
proved in Theorems 4 and 3, respectively. Thus, to complete the proof of
correctness, it is enough to prove that all input messages are discovered,
that every discovered input message is an input message held by some node, and
that the algorithm runs under the restrictions of the ADCS model. Refer to
Algorithm 1.

Assume first for the sake of contradiction that there is some node $v$ with
input message $m$ that is not discovered. Each bit of each newly discovered
input message $m^{\prime}$ is matched to the input messages of all other nodes
holding $m^{\prime}$ in Lines 1.1 (for a 1 bit) or 1.1 (for a 0 bit). Thus,
$m$ will be discovered as long as the number of rounds $r^{\prime}$ is enough
to broadcast the match status of $v$ to all other nodes. Lemma 1 proves that
$r^{\prime}$ is large enough for $v$ to disseminate its match. Therefore $m$
is discovered, which is a contradiction.

Assume now, again for the sake of contradiction, that there is some input
message $m$ that is discovered but it is not an input message of any node in
the system. However, an input message is discovered when there is a $match$
with the input message of some node (or nodes). Therefore, if $m$ is not the
input message of any node it cannot be discovered.

Restricted Methodical Counting ( ) and Multiplicity ( ) are proved to run
under the restrictions of the ADCS model in Theorems 4 and 3, respectively,
and the rest of the messages and calculations in the rest of the algorithm are
on Boolean variables. Thus, Restricted Methodical Counting does not violate
the $O(\log n)$ bits limit on message size and local computation All the
analysis of the various parts of the algorithm apply to
$\mathcal{T}$-connected evolving graph topologies. Therefore, the proof of
correctness is complete.

Regarding the running time complexity, recall that performance is measured in
rounds of communication. Theorems 4 and 3 prove the time complexity of
Restricted Methodical Counting ( ) and Multiplicity ( ) respectively. The
running time of the remaining parts can be obtained by simple inspection.
Namely, communication is carried out in Lines 1.1 and 1.1, each inside a loop
of $r^{\prime}$ iterations, each nested in another loop of $\lceil\log
n\rceil$ iterations (Line 1.1), and the latter nested in a loop of
$n^{\prime}$ iterations (Line 1.1), where $n^{\prime}$ is the number of
different input messages. Thus, the total number of rounds excluding
Restricted Methodical Counting ( ) and Multiplicity ( ) is

$2r^{\prime}\lceil\log n\rceil n^{\prime}=\frac{2\mathcal{T}\ln n\lceil\log
n\rceil n^{\prime}}{\ln(1+i_{\min})}.$

Combining the latter with the running times $O(\ln n/\phi_{\min}^{2})$ proved
in Theorem 3 and $O(n\ln
n\log(n/\ell)/(\ell\min\left\\{{\phi_{\min}}^{2},\ln(1+i_{\min})\right\\}))$
in Corollary 1 (to Theorem 4), the total time complexity is

$O\left(\frac{n\ln
n\log(n/\ell)}{\ell\min\left\\{{\phi_{\min}}^{2},\ln(1+i_{\min})\right\\}}+\frac{n^{\prime}\ln
n\log n}{\ln(1+i_{\min})}\right)\ .$

Using the bound in Equation 1 to replace $\phi_{\min}$, we obtain the claimed
time complexity. ∎

##  6 Counting the Number of Copies of an input message

In the main All-to-All Communication Algorithm 1, at the end of each epoch we
count the number of nodes that have a discovered input message as its own
input message. We do counting using the following procedure Multiplicity
(refer to Algorithm 2). It tries to locally balance potential truncated to
$c\log d$ bits for a sufficiently long time, and once it (almost) stabilizes,
returns it after scaling by the number of all nodes $n$ (recall that in the
main algorithm All-to-All Communication all nodes compute $n$ in the very
beginning).

1 if  _${input\ message}=new\ {input\ message}$_ then $\Phi\leftarrow 1$ else
$\Phi\leftarrow 0$

2 // Assign initial potential for  _$round=1$ to $r^{\prime\prime}$_ do

Send $\langle\Phi\rangle$ and Receive $\langle\Phi_{v}\rangle,\forall v\in N$

// To/from neighbors in $N$

$\Phi\leftarrow\Phi+\sum_{v\in N}\lfloor
d^{c-1}\Phi_{v}\rfloor/d^{c}-|N|\lfloor d^{c-1}\Phi\rfloor/d^{c}$

// Share potential truncated to $c\log d$ bits

3

4 return $\Phi\cdot n$ rounded to the closest integer (up or down)

Algorithm 2 Multiplicity algorithm for each node. ${input\ message}$ is the
input message initially held by this node and $new\ {input\ message}$ is the
input message whose multiplicity has to be counted. $N$ is the set of
neighbors of this node in the current round – the node does not know them, but
can send and receive short messages to/from them. Parameters $d$,
$r^{\prime\prime}$, and $c$ are as defined in Theorem 3.

###  6.1 Analysis of Multiplicity

We analyze the evolution of potentials in the Multiplicity algorithm as a
Markov chain on the $\mathcal{T}$-connected evolving graph
$\mathcal{G}=\\{\mathcal{G}_{j}\\}_{j=0}^{\infty}$, where
$\mathcal{G}_{j}=\\{G_{j\mathcal{T}+t}\\}_{t=1}^{\mathcal{T}}$, as defined in
Section 4.2. We adjust the potentials distribution after each $\mathcal{T}$
rounds by the error produced by the truncation of potentials. In different
nodes such error may delay the convergence to the stationary distribution. To
upper bound the total time, we upper bound the delay (that is, the additional
error with respect to the stationary distribution due to truncation). As a
worst case we assume that the convergence may be delayed at all nodes.

For the purpose of the analysis, we conceptually divide time into blocks of
$\mathcal{T}$ rounds. Let $b=r^{\prime\prime}/\mathcal{T}$ be the number of
blocks in Multiplicity. We denote the vector of potentials at the beginning of
round $i$ of block $j$ as $\mathbf{\Phi}_{i,j}$. For clarity, we will
sometimes refer to round $i$ of block $j$ as round $\langle i,j\rangle$. For
inductive arguments we may refer to the round that follows (resp. preceeds) as
$\langle i+1,j\rangle$ (resp. $\langle i-1,j\rangle$), omitting the fact that
such round may correspond to a different block (i.e., $\langle 1,j+1\rangle$
and $\langle\mathcal{T},j-1\rangle$, resp.) – this is only for notation and
will not influence technical arguments. Also, we denote the potential right
after the potential distribution is stopped (i.e. after the loop in Line 2.2)
as $\mathbf{\Phi}_{1,b+1}$, meaning the potential after the last block of
rounds $b$.

######  Theorem 3.

Consider an ADCS with a $\mathcal{T}$-connected evolving graph topology with
$n\geq 2$ nodes running the Multiplicity algorithm with parameters $d\geq 2n$,
$c\geq 5\alpha+2\mathcal{T}+4$, and $r^{\prime\prime}=\mathcal{T}b$, where
$b\geq 4\alpha\ln n/\phi_{\min}^{2}$,
$\alpha\geq\max\\{\log_{n}(3\mathcal{T}),3\\}$. Let $1\leq\delta\leq n$ be the
number of copies being counted. Then, all nodes return the correct count
$\delta$.

###### Proof.

The algorithm runs under the ADCS restrictions because the potentials are
truncated to $O(\log n)$ bits.

Consider the initial distribution $\mathbf{\Pi}_{1}$ on the overall potential
$||\mathbf{\Phi}_{1,1}||_{1}=\delta$. Given that $d\geq 2n$, the transition
matrix is strongly aperiodic. Then, using Theorem 1, we know that after after
$\mathcal{T}$ rounds the distribution $\mathbf{\Pi}_{\mathcal{T}+1}$ at the
beginning of round $\mathcal{T}+1$ would be such that

$\displaystyle\left|\left|\mathbf{\Pi}_{\mathcal{T}+1}-\frac{\mathbf{I}}{n}\right|\right|_{2}^{2}$
$\displaystyle\leq\left(1-\phi(P_{0})^{2}\right)\left|\left|\mathbf{\Pi}_{1}-\frac{\mathbf{I}}{n}\right|\right|_{2}^{2}\
.$ (2)

Where $\phi(P_{0})$ is the conductance of
$P_{0}=\prod_{t=1}^{\mathcal{T}}P^{(t)}$, and $P^{(t)}$ is the matrix of
shares used by the algorithm in round $t$.

On the other hand, due to truncation, the vector of potentials is such that

$\displaystyle\left|\left|\frac{\mathbf{\Phi}_{1,2}}{||\mathbf{\Phi}_{1,1}||_{1}}-\frac{\mathbf{I}}{n}\right|\right|_{2}^{2}$
$\displaystyle\leq\sum_{v\in
V}\left(\left|\Pi_{\mathcal{T}+1}(v)-\frac{1}{n}\right|+\xi(v)\right)^{2},$

where $\xi(v)$ is the error introduced by the truncation at node $v$ during
the $\mathcal{T}$ rounds. As a worst case we have assumed that $\xi(v)$
contributes to the deviation with respect to the stationary distribution.
Then, we have that

$\displaystyle\left|\left|\frac{\mathbf{\Phi}_{1,2}}{||\mathbf{\Phi}_{1,1}||_{1}}-\frac{\mathbf{I}}{n}\right|\right|_{2}^{2}$
$\displaystyle\leq\sum_{v\in
V}\left(\left(\Pi_{\mathcal{T}+1}(v)-\frac{1}{n}\right)^{2}+2\xi(v)\left|\Pi_{\mathcal{T}+1}(v)-\frac{1}{n}\right|+\xi(v)^{2}\right)$
$\displaystyle=\left|\left|\mathbf{\Pi}_{\mathcal{T}+1}-\frac{\mathbf{I}}{n}\right|\right|_{2}^{2}+\sum_{v\in
V}\left(2\xi(v)\left|\Pi_{\mathcal{T}+1}(v)-\frac{1}{n}\right|+\xi(v)^{2}\right)$
$\displaystyle\leq\left|\left|\mathbf{\Pi}_{\mathcal{T}+1}-\frac{\mathbf{I}}{n}\right|\right|_{2}^{2}+\sum_{v\in
V}\left(2\xi(v)+\xi(v)^{2}\right).$ (3)

The potential received from each neighboring node is truncated to $c\log d$
bits after dividing by $d$. Thus, the error introduced in the calculation of
its new potential in each round is at most $(n-1)/d^{c}\leq 1/d^{c-1}$.
Therefore, we have that after $\mathcal{T}$ rounds it is
$\xi(v)\leq\mathcal{T}/d^{c-1}$, which given that $c\geq
5\alpha+2\mathcal{T}+4\geq\log_{d}\mathcal{T}+1$ it is $\xi(v)\leq 1$. Then,

$\displaystyle\sum_{v\in V}\left(2\xi(v)+\xi(v)^{2}\right)$
$\displaystyle\leq\sum_{v\in V}3\xi(v)\leq\sum_{v\in
V}\frac{3\mathcal{T}}{d^{c-1}}=\frac{3\mathcal{T}n}{d^{c-1}}\leq\frac{3\mathcal{T}}{d^{c-2}}\
.$ (4)

Replacing Eqs. 2 and 4 in 3, we have that

$\displaystyle\left|\left|\frac{\mathbf{\Phi}_{1,2}}{||\mathbf{\Phi}_{1,1}||_{1}}-\frac{\mathbf{I}}{n}\right|\right|_{2}^{2}$
$\displaystyle\leq\left(1-\phi(P_{0})^{2}\right)\left|\left|\mathbf{\Pi}_{1}-\frac{\mathbf{I}}{n}\right|\right|_{2}^{2}+\frac{3\mathcal{T}}{d^{c-2}}\
\leq\
\left(1-\phi(P_{0})^{2}\right)\left|\left|\frac{\mathbf{\Phi}_{1,1}}{||\mathbf{\Phi}_{1,1}||_{1}}-\frac{\mathbf{I}}{n}\right|\right|_{2}^{2}+\frac{3\mathcal{T}}{d^{c-2}}\
.$

The distribution of normalized potential at the beginning of round
$\mathcal{T}+1$ (which is the same as round $\langle 1,2\rangle$) is also a
probability distribution. Thus, the above analysis applies inductively to
every subsequent block of $\mathcal{T}$ rounds.

Then, the vector of potentials after $b$ blocks is such that

$\displaystyle\left|\left|\frac{\mathbf{\Phi}_{1,b+1}}{||\mathbf{\Phi}_{1,1}||_{1}}-\frac{\mathbf{I}}{n}\right|\right|_{2}^{2}$
$\displaystyle\leq\left(1-\phi_{\min}^{2}\right)^{b}\left|\left|\frac{\mathbf{\Phi}_{1,1}}{||\mathbf{\Phi}_{1,1}||_{1}}-\frac{\mathbf{I}}{n}\right|\right|_{2}^{2}+\frac{3\mathcal{T}}{d^{c-2}}\sum_{i=1}^{b-1}\left(1-\phi_{\min}^{2}\right)^{i}$
$\displaystyle\leq\left(1-\phi_{\min}^{2}\right)^{b}\left|\left|\frac{\mathbf{\Phi}_{1,1}}{||\mathbf{\Phi}_{1,1}||_{1}}-\frac{\mathbf{I}}{n}\right|\right|_{2}^{2}+\frac{3\mathcal{T}}{d^{c-2}}\frac{1}{\phi_{\min}^{2}}\
\leq\
\exp\left(-b\phi_{\min}^{2}\right)+\frac{3\mathcal{T}}{d^{c-2}\phi_{\min}^{2}}\
.$

In potential distribution algorithms where each non-zero entry of
$P^{(j\mathcal{T}+i)}$ is at least $1/d$, for any $j>0$,
$i\in[1,\mathcal{T}]$, and some $d\geq 1$, as it is the case in the
Multiplicity algorithm, it is $\phi_{\min}\geq 2/(nd^{\mathcal{T}})\geq
2/d^{\mathcal{T}+1}$. Then, it is

$\displaystyle\left|\left|\frac{\mathbf{\Phi}_{1,b+1}}{||\mathbf{\Phi}_{1,1}||_{1}}-\frac{\mathbf{I}}{n}\right|\right|_{2}^{2}$
$\displaystyle\leq\exp\left(-b\phi_{\min}^{2}\right)+\frac{3\mathcal{T}}{4d^{c-2\mathcal{T}-4}}\
.$ (5)

Given that $b\geq 4\alpha\ln n/\phi_{\min}^{2}$, it is

$\displaystyle\left|\left|\frac{\mathbf{\Phi}_{1,b+1}}{||\mathbf{\Phi}_{1,1}||_{1}}-\frac{\mathbf{I}}{n}\right|\right|_{2}^{2}$
$\displaystyle\leq\frac{1}{n^{4\alpha}}+\frac{3\mathcal{T}}{4d^{c-2\mathcal{T}-4}}\
.$

Replacing $\alpha\geq\log_{n}(3\mathcal{T})$ and $d\geq n$, it is

$\displaystyle\left|\left|\frac{\mathbf{\Phi}_{1,b+1}}{||\mathbf{\Phi}_{1,1}||_{1}}-\frac{\mathbf{I}}{n}\right|\right|_{2}^{2}$
$\displaystyle\leq\frac{1}{n^{4\alpha}}+\frac{1}{4n^{c-2\mathcal{T}-4-\alpha}}\
.$

And for $c\geq 5\alpha+2\mathcal{T}+4$ we have that

$\displaystyle\left|\left|\frac{\mathbf{\Phi}_{1,b+1}}{||\mathbf{\Phi}_{1,1}||_{1}}-\frac{\mathbf{I}}{n}\right|\right|_{2}^{2}$
$\displaystyle\leq\frac{5}{4n^{4\alpha}}\leq\frac{1}{n^{2\alpha}},\textrm{ for
$\alpha\geq 1/2$ and $n\geq 5/4$}\ .$

Given that
$({\Phi}_{1,b+1}[v]/||\mathbf{\Phi}_{1,1}||_{1}-1/n)^{2}\leq\left|\left|\mathbf{\Phi}_{1,b+1}/||\mathbf{\Phi}_{1,1}||_{1}-\frac{\mathbf{I}}{n}\right|\right|_{2}^{2}$
for any node $v$, we have that
$({\Phi}_{1,b+1}[v]/||\mathbf{\Phi}_{1,1}||_{1}-1/n)^{2}\leq 1/n^{2\alpha}$
and hence
$1/n-1/n^{\alpha}\leq{\Phi}_{1,b+1}[v]/||\mathbf{\Phi}_{1,1}||_{1}\leq
1/n+1/n^{\alpha}$.

Then, we have
$(\delta/n-1/n^{\alpha-1})\leq{\Phi}_{1,b+1}[v]\leq(\delta/n+1/n^{\alpha-1})$
and so $\delta-1/n^{\alpha-2}\leq{\Phi}_{1,b+1}[v]n\leq\delta+1/n^{\alpha-2}$.
Replacing $\alpha\geq 3$ and $n\geq 2$ we have that
$\delta-1/2\leq{\Phi}_{1,b+1}[v]n\leq\delta+1/2$. Thus, after rounding to the
closest integer in Line 2.2 the returned value is $\delta$ as claimed. ∎

##  7 Counting the Number of Nodes in the System

The first step of our All-to-All Communication algorithm is to compute the
unknown number of nodes $n$. Counting the number of nodes in Anonymous Dynamic
Networks has attracted a lot of attention recently [41, 33, 35, 13, 12]. Most
notably, the Methodical Counting (MC) protocol [33] was the first one to
achieve polynomial time after a flurry of papers improving bounds that started
with doubly-exponential time [41]. The ADN model is challenging due to lack of
node identifiers and arbitrary topology changes, but still lags behind real-
world constraints such as limited bandwidth, disconnection of the network,
and/or limited computational resources.

In this work, as an integral part of our All-to-All Communication algorithm,
but also of independent interest, we present the Restricted Methodical
Counting (RMC) algorithm which computes the number of nodes under the harsh
restrictions of Anonymous Dynamic Congested Systems with opportunistic
$\mathcal{T}$-connectivity. RMC is inspired on an extension of MC called
Methodical Multi-Counting (MMC) [35], but carefully adapted to cope with
limited messages, memory accesses, and connectivity. Our analysis relies on a
bound on mixing time for $\mathcal{T}$-connected evolving graphs. The analysis
and design of the algorithm handle the errors produced by truncation of the
calculations, purposely introduced to stay within the limits on message size
and memory access. We describe RMC in the following section and analyze its
properties afterwards. The pseudocode of RMC can be found in Algorithms 3 and
4.

###  7.1 The Restricted Methodical Counting Algorithm

RMC is executed synchronously by all nodes. Given that no preliminary
knowledge of the network size is available, nodes maintain a running estimate
of $n$ that starts with the minimum possible, that is, one more than the
number of supervisors $\ell$. By means of various alarms, the estimate is
detected to be either low, high, or correct. Starting with the initial value,
the estimate is updated by exponential search until it is correct. If the
estimate becomes high (that is, if the correct value is skipped) the correct
estimate is found by binary search in the last range between low and high
detection.

The evaluation of each estimate is implemented as follows. In each round of
communication nodes share some potential values with neighbors in a gossip-
based fashion. The fraction of potential shared, as well as the truncation of
messages and calculations to adapt to the limits in communication and memory
access, are functions of the running estimate, given that $n$ is not known.
This gossiping continues for a number of rounds after which supervisors move
their potential to a separate accumulator completing what is called
conceptually a phase. The process repeats for a number of phases to complete
the evaluation of the current estimate. The number of rounds and phases are
functions of the running estimate, the errors produced by truncation, and the
disconnection characteristic $\mathcal{T}$.

If the estimate is correct, the number of rounds and phases are such that
supervisors have moved almost all the initial potential to their accumulators.
Then, supervisors univocally decide that the estimate is correct comparing the
value in their accumulators with some carefully designed range, and they
disseminate the news to all other nodes by simple broadcast.

If on the other hand the estimate is incorrect, that is, if it is either low
or high, the algorithm detects by one or more of the following alarms. If
nodes receive messages from more neighbors than the running estimate, the
estimate is obviously low. If early in the execution potentials are above some
carefully calculated threshold, the estimate is low as our analysis shows.
Finally, if the supervisors accumulated potential is outside the
abovementioned range, or a node receives a notification of wrong estimate from
other nodes, the estimate is either low or high (whatever corresponds).

A crucial difference between RMC and MMC is the way that potentials are shared
and updated in each round to cope with limits in communication and memory
access. Specifically, in MMC the potential $\Phi$ of each node $u$ is updated
in round $r$ of phase $p$ of an epoch with estimate $k$ as

$\Phi_{p,r+1}[u]=\Phi_{p,r}[u]+\sum_{v\in
N_{p,r}[u]}\frac{\Phi_{p,r}[v]}{d}-|N_{p,r}[u]|\frac{\Phi_{p,r}[u]}{d},$

where $N_{p,r}[u]$ is the set of neighbors of $u$ in round $r$ of phase $p$,
$d=2k^{1+\epsilon}$ and $\epsilon>0$ is an arbitrarily small constant
666Notice that nodes do not know $N_{p,r}[u]$, but they know $|N_{p,r}[u]|$
after receiving messages. Also, recall that nodes are labeled only for the
presentation, but nodes do not have identifiers..

In words, each node shares a fraction $1/d$ with its neighbors. So, node $u$
adds to its current potential a $1/d$ fraction of the potential of each
neighbor, and subtracts a $1/d$ fraction of its own potential for each
neighbor. The potential $\Phi$ is transmitted as a whole rather than the
fraction since all nodes know $d=2k^{1+\epsilon}$ because the algorithm is
synchronous. However, after successive rounds of dividing by $d$, the
potential of some nodes may require $\omega(\log d)$ bits of precision. That
is, for $k\in\omega(\sqrt[1+\epsilon]{n})$, they would require $\omega(\log
n)$ bits of precision, violating the limits on communication and memory
access. To avoid it, in RMC shared potentials are truncated to the most
significant $c\log d$ bits, for some constant $c$ defined later. More
precisely, in RMC the potential $\Phi$ of each node $u$ is updated in round
$r$ of phase $p$ of an epoch with estimate $k$ as

$\displaystyle\Phi_{p,r+1}[u]$ $\displaystyle=\Phi_{p,r}[u]+\sum_{v\in
N_{p,r}[u]}\frac{\lfloor
d^{c-1}\Phi_{p,r}[v]\rfloor}{d^{c}}-|N_{p,r}[u]|\frac{\lfloor
d^{c-1}\Phi_{p,r}[u]\rfloor}{d^{c}}\ .$

Also, to attain strong aperiodicity as required by Theorem 1, we set
$d=2k^{1+\epsilon}$. Given that throughout the execution $k<2n$, RMC does not
violate the limits on communication and memory access.

$k\leftarrow\ell+1,min\leftarrow k,max\leftarrow\infty$

// initial size estimate and range

1 repeat // iterating epochs

$status\leftarrow probing$

// status$=$probing$|$low$|$high$|$done

$\Phi\leftarrow 0$

// current potential

$\rho\leftarrow 0$

// potential accumulator

2 for  _$phase=1$ to $p$_ do // iterating phases

3 for  _$round=1$ to $r$_ do // iterating rounds

Send $\langle\Phi,status\rangle$ and Receive
$\langle\Phi_{i},status_{i}\rangle,\forall i\in N$

// To/from neighbors in $N$

4 if  _$status=probing$ and $|N|<d/2$ and $\forall i\in N:status_{i}=probing$_
then

$\Phi\leftarrow\Phi+\sum_{v\in N}\lfloor
d^{c-1}\Phi_{v}\rfloor/d^{c}-|N|\lfloor d^{c-1}\Phi\rfloor/d^{c}$

// Share potential truncated to $c\log d$ bits

5

6 else // $k<n$

7 $status\leftarrow low$, $\Phi\leftarrow\ell$

8

9

10 if  _$phase=1$ and $\Phi>\tau$_ then $status\leftarrow low$,
$\Phi\leftarrow\ell$

11 // $k<n$ if  _$status=probing$_ then // prepare for next phase

$\rho\leftarrow\rho+\Phi$

// consume potential

12 $\Phi\leftarrow 0$

13

14

15 if  _$status=probing$_ then

16 if  _$(k-\ell)(1-k^{-\gamma})\leq\rho\leq(k-\ell)(1+k^{-\gamma})$_ then //
$k=n$

17 $status\leftarrow done$

18 if  _$\rho <(k-\ell)(1-k^{-\gamma})$_ then $status\leftarrow high$

19 // $k>n$ if  _$\rho >(k-\ell)(1+k^{-\gamma})$_ then $status\leftarrow low$

20 // $k<n$

21 for  _$round=1$ to $d$_ do // disseminate status

22 Broadcast $\langle status\rangle$ and Receive $\langle
status_{i}\rangle,\forall i\in N$

23

24 if  _$status=low$_ then // prepare for next epoch

25 $min\leftarrow k+1$

26 if  _$max=\infty$_ then $k\leftarrow 2k$ else
$k\leftarrow\lfloor(min+max)/2\rfloor$

27

28 else

29 if  _$status=high$_ then

30 $max\leftarrow k-1$

31 $k\leftarrow\lfloor(min+max)/2\rfloor$

32

33

34

35until  _$status=done$_

36return $k$

37

Algorithm 3 Restricted Methodical Counting algorithm for each _supervisor
node_. $N$ is the set of neighbors of this node in the current round – the
node does not know them, but can send and receive short messages to/from them.
$\ell$ is the number of supervisor nodes. The parameters $d,p,r,\tau$ and $c$
are as defined in Theorem 4.

$k\leftarrow\ell+1,min\leftarrow k,max\leftarrow\infty$

// initial size estimate and range

1 repeat // iterating epochs

$status\leftarrow probing$

// status$=$probing$|$low$|$high$|$done

$\Phi\leftarrow\ell$

// current potential

2 for  _$phase=1$ to $p$_ do // iterating phases

3 for  _$round=1$ to $r$_ do // iterating rounds

Send $\langle\Phi,status\rangle$ and Receive
$\langle\Phi_{i},status_{i}\rangle,\forall i\in N$

// To/from neighbors in $N$

4 if  _$status=probing$ and $|N|<d/2$ and $\forall i\in N:status_{i}=probing$_
then

$\Phi\leftarrow\Phi+\sum_{v\in N}\lfloor
d^{c-1}\Phi_{v}\rfloor/d^{c}-|N|\lfloor d^{c-1}\Phi\rfloor/d^{c}$

// Share potential truncated to $c\log d$ bits

5

6 else // $k<n$

7 $status\leftarrow low$, $\Phi\leftarrow\ell$

8

9

10 if  _$phase=1$ and $\Phi>\tau$_ then $status\leftarrow low$,
$\Phi\leftarrow\ell$

11 // $k<n$

12 for  _$round=1$ to $d$_ do // disseminate status

13 Broadcast $\langle status\rangle$ and Receive $\langle
status_{i}\rangle,\forall i\in N$

14 if  _$\exists i\in N:status_{i}\neq probing$_ then $status\leftarrow
status_{i}$

15

16 if  _$status=low$_ then // prepare for next epoch

17 $min\leftarrow k+1$

18 if  _$max=\infty$_ then $k\leftarrow 2k$ else
$k\leftarrow\lfloor(min+max)/2\rfloor$

19

20 else

21 if  _$status=high$_ then

22 $max\leftarrow k-1$

23 $k\leftarrow\lfloor(min+max)/2\rfloor$

24

25

26

27until  _$status=done$_

28return $k$

29

Algorithm 4 Restricted Methodical Counting algorithm for each _supervised
node_. $N$ is the set of neighbors of this node in the current round – the
node does not know them, but can send and receive short messages to/from them.
$\ell$ is the number of supervisor nodes. The parameters $d,p,r,\tau$ and $c$
are as defined in Theorem 4.

###  7.2 Analysis of Restricted Methodical Counting

We analyze the evolution of potentials as a Markov chain on the
$\mathcal{T}$-connected evolving graph
$\mathcal{G}=\\{\mathcal{G}_{j}\\}_{j=0}^{\infty}$, where
$\mathcal{G}_{j}=\\{G_{j\mathcal{T}+t}\\}_{t=1}^{\mathcal{T}}$, as defined in
Section 4.2. We adjust the potentials distribution after each $\mathcal{T}$
rounds by the error produced by the truncation of potentials. In different
nodes such error may delay the convergence to the stationary distribution. To
upper bound the total time, we upper bound the delay (that is, the additional
error with respect to the stationary due to truncation). As a worst case we
assume that the convergence is delayed at all nodes.

For the purpose of the analysis, we conceptually divide each phase in blocks
of $\mathcal{T}$ rounds. (The number of rounds in each phase will be a
multiple of $\mathcal{T}$.) We denote the vector of potentials at the
beginning of round $i$ of block $j$ of phase $h$ as $\mathbf{\Phi}_{i,j,h}$.
For clarity, we will sometimes refer to round $i$ of block $j$ of phase $h$ as
round $\langle i,j,h\rangle$, and for inductive arguments we may refer to the
round that follows (resp. preceeds) as $\langle i+1,j,h\rangle$ (resp.
$\langle i-1,j,h\rangle$), omitting the fact that such round may correspond to
a different block. Also, we refer to the potential right before the beginning
of phase $h>1$, denoted as $\mathbf{\Phi}_{0,0,h}$, meaning the potential
after the last round of phase $h-1$, before the potential is reset at the
beginning of phase $h$.

First, we prove the following two claims about properties of the potential
during the execution of RMC, for later use.

######  Claim 1.

Given an ADCS of $n$ nodes running RMC with parameter $d$, for any round
$\langle i,j,h\rangle$ of phase $h$, if $d$ was larger than the number of
neighbors of each node $x$ for every round $\langle
i^{\prime},j^{\prime},h\rangle$ before round $\langle i,j,h\rangle$, then
$||\mathbf{\Phi}_{i,j,h}||_{1}=||\mathbf{\Phi}_{1,1,h}||_{1}$.

###### Proof.

For any given round $\langle i,j,h\rangle$ and any given node $u$, if $d/2$ is
larger than the number of neighbors of $u$, the potential is updated as (refer
to Lines 3.3 and 4.4)

$\displaystyle\Phi_{i+1,j,h}[u]$ $\displaystyle=\Phi_{i,j,h}[u]+\sum_{v\in
N_{i,j,h}[u]}\frac{\lfloor
d^{c-1}\Phi_{i,j,h}[v]\rfloor}{d^{c}}-|N_{i,j,h}[u]|\frac{\lfloor
d^{c-1}\Phi_{i,j,h}[u]\rfloor}{d^{c}}\ ,$

where $N_{i,j,h}[u]$ is the set of neighbors of $u$ in round $\langle
i,j,h\rangle$. Inductively, assume that the claimed overall potential holds
for some round $\langle i,j,h\rangle$, we want to show that consequently it
holds for $\langle i+1,j,h\rangle$. The potential for round $\langle
i+1,j,h\rangle$ is

$\displaystyle||\mathbf{\Phi}_{i+1,j,h}||_{1}$
$\displaystyle=||\mathbf{\Phi}_{i,j,h}||_{1}+\frac{1}{d^{c}}\sum_{u\in
V}\left(\sum_{v\in N_{i,j,h}[u]}\lfloor
d^{c-1}\Phi_{i,j,h}[v]\rfloor-|N_{i,j,h}[u]|\lfloor
d^{c-1}\Phi_{i,j,h}[u]\rfloor\right)\ .$ (6)

In the ADCS model, communication is symmetric. That is, for every pair of
nodes $x,y\in V$, and round $\langle i,j,h\rangle$ it is $x\in
N_{i,j,h}[y]\iff y\in N_{i,j,h}[x]$. Fix a pair of nodes
$x^{\prime},y^{\prime}\in V$ such that in round $\langle i,j,h\rangle$ it is
$y^{\prime}\in N_{i,j,h}[x^{\prime}]$ and hence $x^{\prime}\in
N_{i,j,h}[y^{\prime}]$. Consider the summations in Equation 6. Due to
symmetric communication, we have that the potential $\Phi_{i,j,h}[y^{\prime}]$
appears with positive sign when the indices of the summations are
$x=x^{\prime}$ and $y=y^{\prime}$, and with negative sign when the indices are
$x=y^{\prime}$ and $y=x^{\prime}$. (Notice that it is truncated the same way
at both nodes.) This observation applies to all pairs of nodes that
communicate in any round. Therefore, we can re-write Equation 6 as

$\displaystyle||\mathbf{\Phi}_{i+1,j,h}||_{1}$
$\displaystyle=||\mathbf{\Phi}_{i,j,h}||_{1}+\frac{1}{d^{c}}\\!\\!\sum_{\begin{subarray}{c}u,v\in
V:\\\ v\in N_{i,j,h}[u]\\\ \end{subarray}}\bigg{(}\lfloor
d^{c-1}\Phi_{i,j,h}[u]\rfloor-\lfloor d^{c-1}\Phi_{i,j,h}[v]\rfloor+\lfloor
d^{c-1}\Phi_{i,j,h}[v]\rfloor-\lfloor
d^{c-1}\Phi_{i,j,h}[u]\rfloor\bigg{)}=||\mathbf{\Phi}_{i,j,h}||_{1}\ .$

Thus, the claim follows. ∎

######  Claim 2.

Given an ADCS with $\ell>0$ supervisors and $n-\ell>0$ supervised nodes
running RMC with parameter $c\geq 2$, for any round $\langle i,j,h\rangle$ and
any node $u\in V$, it is $\Phi_{i,j,h}[u]\geq 0$.

###### Proof.

At the beginning of the first round the potential of the supervisor nodes is
$0$ and the potential of any supervised node $x$ is $\ell$. Thus, the claim
follows.

Inductively, for any round $\langle i,j,h\rangle$ after the first round, we
consider two cases according to node status. If a node $x$ is in alarm status
“low” at the beginning of the round, then it is $\Phi_{i,j,h}[x]=\ell$
because, whenever the status of a node is updated to “low”, its potential is
set to $\ell$ and will not change until the next epoch (refer to Algorithms 3
and 4)

In the second case, if a node $u$ is in “probing” status at the beginning of
round $\langle i,j,h\rangle$, it means that it had its potential updated in
all previous rounds $\langle i^{\prime},j^{\prime},h^{\prime}\rangle$ as
(refer to Lines 3.3 or 4.4)

$\displaystyle\Phi_{i^{\prime}+1,j^{\prime},h^{\prime}}[u]$
$\displaystyle=\Phi_{i^{\prime},j^{\prime},h^{\prime}}[u]+\sum_{v\in
N_{i^{\prime},j^{\prime},h^{\prime}}[u]}\frac{\lfloor
d^{c-1}\Phi_{i^{\prime},j^{\prime},h^{\prime}}[v]\rfloor}{d^{c}}-|N_{i^{\prime},j^{\prime},h^{\prime}}[u]|\frac{\lfloor
d^{c-1}\Phi_{i^{\prime},j^{\prime},h^{\prime}}[u]\rfloor}{d^{c}}$
$\displaystyle\leq\Phi_{i^{\prime},j^{\prime},h^{\prime}}[u]+\sum_{v\in
N_{i^{\prime},j^{\prime},h^{\prime}}[u]}\frac{\Phi_{i^{\prime},j^{\prime},h^{\prime}}[v]}{d}-|N_{i^{\prime},j^{\prime},h^{\prime}}[u]|\frac{\Phi_{i^{\prime},j^{\prime},h^{\prime}}[u]}{d}+|N_{i^{\prime},j^{\prime},h^{\prime}}[u]|\frac{1}{d^{c}}\
.$ (7)

Where the last term is the maximum extra potential kept by node $u$ due to
truncation to $c\log d$ bits by nodes in $N_{i,j,h}[u]$. For all rounds
$\langle i^{\prime},j^{\prime},h^{\prime}\rangle$, node $u$ exchanged
potential with less than $d/2$ neighbors, because otherwise it would have been
changed to alarm status (refer to Lines 3.3 and 4.4). Therefore it is
$|N_{i^{\prime},j^{\prime},h^{\prime}}[u]|\Phi_{i^{\prime},j^{\prime},h^{\prime}}[u]/d<\Phi_{i^{\prime},j^{\prime},h^{\prime}}[u]$
which implies $\Phi_{i,j,h}[u]\geq 0$. ∎

The general structure of the rest of the proof is the following. We divide the
analysis in 4 cases according to the relation between the estimate $k$ and the
network size $n$.

if | then | proved in
---|---|---
$k^{1+\epsilon}<n$ | All nodes receive alarm | Lemma 6 & auxiliary 4 and 5.
$k<n\leq k^{1+\epsilon}$ | $\rho>(k-\ell)\left(1+\frac{1}{k^{\gamma}}\right)$ | Lemma 3.
$k=n$ | $(k-\ell)\left(1-\frac{1}{k^{\gamma}}\right)\leq\rho\leq(k-\ell)\left(1+\frac{1}{k^{\gamma}}\right)$ | Lemma 2.
$k>n$ | $\rho<(k-\ell)\left(1-\frac{1}{k^{\gamma}}\right)$ | Lemma 7.

We begin the analysis considering the case $k=n$, as follows.

######  Lemma 2.

Consider an ADCS with a $\mathcal{T}$-connected evolving graph topology with
$\ell>0$ supervisors and $n-\ell>0$ supervised nodes running the RMC protocol
with parameters $d\geq 2k$, $p\geq(2\gamma\ln
k)/\left(\ell\left(\frac{1}{k}+\frac{1}{k^{\alpha}}\right)\right)$, $r\geq
4\mathcal{T}\alpha\ln k/\phi_{\min}^{2}$, and $c\geq 5\alpha+2\mathcal{T}+4$,
where $\gamma>0$ and
$\alpha\geq\max\\{2,1+\gamma+\log_{k}3,\log_{k}(3\mathcal{T})\\}$. Then, if
$k=n$, the potential $\rho$ consumed by each of the $\ell$ supervisor nodes is
such that

$(k-\ell)\left(1-\frac{1}{k^{\gamma}}\right)\leq\rho\leq(k-\ell)\left(1+\frac{1}{k^{\gamma}}\right).$

###### Proof.

Given that $d\geq 2n$ and $c>\log_{d}\mathcal{T}+1$, we have from Eq. 5 in the
proof of Theorem 3 (changing the notation appropriately) that right before the
beginning of any phase $h>1$ it is

$\displaystyle\left|\left|\frac{\mathbf{\Phi}_{0,0,2}}{||\mathbf{\Phi}_{1,1,1}||_{1}}-\frac{\mathbf{I}}{n}\right|\right|_{2}^{2}$
$\displaystyle\leq\exp\left(-b\phi_{\min}^{2}\right)+\frac{3\mathcal{T}}{4d^{c-2\mathcal{T}-4}}\
.$

The above applies to any phase as long as $d\geq n$. Thus, we have that right
before the beginning of any phase $h>1$:

$\displaystyle\left|\left|\frac{\mathbf{\Phi}_{0,0,h}}{||\mathbf{\Phi}_{1,1,h-1}||_{1}}-\frac{\mathbf{I}}{n}\right|\right|_{2}^{2}$
$\displaystyle\leq\exp\left(-b\phi_{\min}^{2}\right)+\frac{3\mathcal{T}}{4d^{c-2\mathcal{T}-4}}\
.$ (8)

Given that $r\geq 4\mathcal{T}\alpha\ln k/\phi_{\min}^{2}$ and each block has
$\mathcal{T}$ rounds, it is $b\geq 4\alpha\ln k/\phi_{\min}^{2}$. Thus,

$\displaystyle\left|\left|\frac{\mathbf{\Phi}_{0,0,h}}{||\mathbf{\Phi}_{1,1,h-1}||_{1}}-\frac{\mathbf{I}}{n}\right|\right|_{2}^{2}$
$\displaystyle\leq\frac{1}{k^{4\alpha}}+\frac{3\mathcal{T}}{4d^{c-2\mathcal{T}-4}}\
.$

Replacing $\alpha\geq\log_{k}(3\mathcal{T})$ and $d\geq k$, it is

$\displaystyle\left|\left|\frac{\mathbf{\Phi}_{0,0,h}}{||\mathbf{\Phi}_{1,1,h-1}||_{1}}-\frac{\mathbf{I}}{n}\right|\right|_{2}^{2}$
$\displaystyle\leq\frac{1}{k^{4\alpha}}+\frac{1}{4d^{c-2\mathcal{T}-4-\alpha}}\
.$

And for $c\geq 5\alpha+2\mathcal{T}+4$ we have that

$\displaystyle\left|\left|\frac{\mathbf{\Phi}_{0,0,h}}{||\mathbf{\Phi}_{1,1,h-1}||_{1}}-\frac{\mathbf{I}}{n}\right|\right|_{2}^{2}$
$\displaystyle\leq\frac{5}{4k^{4\alpha}}\leq\frac{1}{k^{2\alpha}}\ ,\textrm{
for $\alpha\geq 1/2$ and $k\geq 2$}\ .$

Given that
$({\Phi}_{0,0,h}[v]/||\mathbf{\Phi}_{1,1,h-1}||_{1}-1/n)^{2}\leq\left|\left|\mathbf{\Phi}_{0,0,h}/||\mathbf{\Phi}_{1,1,h-1}||_{1}-\frac{\mathbf{I}}{n}\right|\right|_{2}^{2}$
for any node $v$ and phase $h>1$, we have that
$({\Phi}_{0,0,,h}[v]/||\mathbf{\Phi}_{1,1,h-1}||_{1}-1/n)^{2}=({\Phi}_{0,0,,h}[v]/||\mathbf{\Phi}_{1,1,h-1}||_{1}-1/k)^{2}\leq
1/k^{2\alpha}$ and hence
${\Phi}_{0,0,h}[v]\geq(1/k-1/k^{\alpha})||\mathbf{\Phi}_{1,1,h-1}||_{1}$.
Notice that the latter is true for any initial distribution. Therefore, after
each phase a supervisor node consumes between $1/k-1/k^{\alpha}$ and
$1/k+1/k^{\alpha}$ fraction of the total potential in the system, and the
total potential in the system drops by at least $\ell(1/k-1/k^{\alpha})$ and
by at most $\ell(1/k+1/k^{\alpha})$ fraction. Recall that the initial overall
potential in the system is $\ell(n-\ell)=\ell(k-\ell)$, and that by Claim 1,
if $d>n$, the overall potential in the system is the same throughout each
phase.

Using the latter observations, we first find conditions on the number of
phases $p$ to obtain the desired bounds on $\rho$, as follows. After $p$
phases a supervisor node consumes at least

$\displaystyle\rho$
$\displaystyle\geq\ell(k-\ell)\left(\frac{1}{k}-\frac{1}{k^{\alpha}}\right)\sum_{i=0}^{p-1}\left(1-\ell\left(\frac{1}{k}+\frac{1}{k^{\alpha}}\right)\right)^{i}\
,$ (9)

and at most

$\displaystyle\rho$
$\displaystyle\leq\ell(k-\ell)\left(\frac{1}{k}+\frac{1}{k^{\alpha}}\right)\sum_{i=0}^{p-1}\left(1-\ell\left(\frac{1}{k}-\frac{1}{k^{\alpha}}\right)\right)^{i}\
.$ (10)

Given that $0<\ell\left(\frac{1}{k}+\frac{1}{k^{\alpha}}\right)<1$ for
$\alpha\geq 2$ and $k>\ell$, Equation 9 is

$\displaystyle\rho$
$\displaystyle\geq\ell(k-\ell)\left(\frac{1}{k}-\frac{1}{k^{\alpha}}\right)\frac{1-\left(1-\ell\left(\frac{1}{k}+\frac{1}{k^{\alpha}}\right)\right)^{p}}{1-\left(1-\ell\left(\frac{1}{k}+\frac{1}{k^{\alpha}}\right)\right)}\
=\
(k-\ell)\frac{k^{\alpha}-k}{k^{\alpha}+k}\left(1-\left(1-\ell\left(\frac{1}{k}+\frac{1}{k^{\alpha}}\right)\right)^{p}\right)\
.$

Given that $0<\ell\left(\frac{1}{k}+\frac{1}{k^{\alpha}}\right)<1$ for
$\ell<k$ and $\alpha\geq 2$, it is

$\displaystyle\rho$
$\displaystyle\geq(k-\ell)\frac{k^{\alpha}-k}{k^{\alpha}+k}\left(1-\exp\left(-p\ell\left(\frac{1}{k}+\frac{1}{k^{\alpha}}\right)\right)\right)\
.$

Thus, to prove the lower bound on $\rho$, it is enough to find values of $p$
and $\alpha$ such that

$\displaystyle\frac{k^{\alpha}-k}{k^{\alpha}+k}\left(1-\exp\left(-p\ell\left(\frac{1}{k}+\frac{1}{k^{\alpha}}\right)\right)\right)$
$\displaystyle\geq 1-\frac{1}{k^{\gamma}}\ .$

We note first that for

$p\geq\frac{2\gamma\ln k}{\ell\left(\frac{1}{k}+\frac{1}{k^{\alpha}}\right)}\
,$

it is

$1-\exp\left(-p\ell\left(\frac{1}{k}+\frac{1}{k^{\alpha}}\right)\right)\geq
1-\frac{1}{k^{2\gamma}}\ .$

Replacing, it is enough to prove

$\displaystyle\frac{k^{\alpha}-k}{k^{\alpha}+k}\left(1+\frac{1}{k^{\gamma}}\right)$
$\displaystyle\geq 1$ (11) $\displaystyle k^{\alpha-\gamma}$
$\displaystyle\geq 2k+k^{1-\gamma}\ .$

Thus, for $\gamma>0$ it is enough to prove $k^{\alpha-\gamma}\geq 3k$, which
is true for $\alpha\geq 1+\gamma+\log_{k}3$. We show now the upper bound on
$\rho$ starting from Equation 10:

$\displaystyle\rho$
$\displaystyle\leq\ell(k-\ell)\left(\frac{1}{k}+\frac{1}{k^{\alpha}}\right)\sum_{i=0}^{p-1}\left(1-\ell\left(\frac{1}{k}-\frac{1}{k^{\alpha}}\right)\right)^{i}.$

Given that $1-\ell\left(\frac{1}{k}-\frac{1}{k^{\alpha}}\right)<1$ for
$\alpha\geq 2>1$, it is

$\displaystyle\rho$
$\displaystyle\leq\ell(k-\ell)\left(\frac{1}{k}+\frac{1}{k^{\alpha}}\right)\frac{1-\left(1-\ell\left(\frac{1}{k}-\frac{1}{k^{\alpha}}\right)\right)^{p}}{1-\left(1-\ell\left(\frac{1}{k}-\frac{1}{k^{\alpha}}\right)\right)}\
=\
(k-\ell)\frac{k^{\alpha}+k}{k^{\alpha}-k}\left(1-\left(1-\ell\left(\frac{1}{k}-\frac{1}{k^{\alpha}}\right)\right)^{p}\right).$

Given that $0<\ell\left(\frac{1}{k}-\frac{1}{k^{\alpha}}\right)<1$ and $p>0$,
it is
$\left(1-\left(1-\ell\left(\frac{1}{k}-\frac{1}{k^{\alpha}}\right)\right)^{p}\right)<1$.
Then, replacing, we get

$\displaystyle\rho$
$\displaystyle\leq(k-\ell)\frac{k^{\alpha}+k}{k^{\alpha}-k}\ .$

Thus, to prove the upper bound on $\rho$, it is enough to show that

$\displaystyle\frac{k^{\alpha}+k}{k^{\alpha}-k}$ $\displaystyle\leq
1+\frac{1}{k^{\gamma}}\ .$

This is the same as Equation 11 and hence the claim follows. ∎

The previous lemma shows that, after running RMC enough time, if for some
supervisor node it is $\rho>(k-\ell)\left(1+\frac{1}{k^{\gamma}}\right)$ or
$\rho<(k-\ell)\left(1-\frac{1}{k^{\gamma}}\right)$, for some $\gamma>0$, we
know that the estimate $k$ is wrong. However, the complementary case, that is,
$(k-\ell)\left(1-\frac{1}{k^{\gamma}}\right)\leq\rho\leq(k-\ell)\left(1+\frac{1}{k^{\gamma}}\right)$,
may occur even if the estimate is $k\neq n$ and hence the error has to be
detected by other means. To prove correctness in that case we further separate
the range of $k$ in three cases. The first one, when $k<n\leq k^{1+\epsilon}$,
for some $\epsilon>0$, in the following lemma, which is based on upper
bounding the potential left in the system after running RMC long enough.

######  Lemma 3.

Consider an ADCS with a $\mathcal{T}$-connected evolving graph topology with
$\ell>0$ supervisors and $n-\ell>0$ supervised nodes running the RMC protocol
with parameters $d\geq k^{1+\epsilon}$, $p\geq 2\delta(\ln
k)/(\ell\left(1/n+1/k^{\beta}\right))$, $r\geq 4\mathcal{T}\beta\ln
k/\phi_{\min}^{2}$, and $c\geq 5\beta+2\mathcal{T}+4$, where
$\beta\geq\log_{k}\max\\{(n(2k^{\delta}+1)),3\mathcal{T}\\}$, $\beta>2$,
$\delta>\log_{k}(nk^{\gamma}/(nk^{\gamma}-(n-1)(k^{\gamma}+1)))$,
$\gamma>\log_{k}(n-1)$, and $\epsilon>0$. Then, if $k<n\leq k^{1+\epsilon}$,
the potential $\rho$ consumed by any supervisor node is
$\rho>(k-\ell)\left(1+1/k^{\gamma}\right)$.

###### Proof.

Given that $d\geq n$ and $c>\log_{d}\mathcal{T}+1$, we have from Eq. 8 that
right before the beginning of any phase $h>1$

$\displaystyle\left|\left|\frac{\mathbf{\Phi}_{0,0,h}}{||\mathbf{\Phi}_{1,1,h-1}||_{1}}-\frac{\mathbf{I}}{n}\right|\right|_{2}^{2}$
$\displaystyle\leq\exp\left(-b\phi_{\min}^{2}\right)+\frac{3\mathcal{T}}{4d^{c-2\mathcal{T}-4}}\
.$

Given that $r\geq 4\mathcal{T}\beta\ln k/\phi_{\min}^{2}$ and each block has
$\mathcal{T}$ rounds, it is $b\geq 4\beta\ln k/\phi_{\min}^{2}$. Thus,

$\displaystyle\left|\left|\frac{\mathbf{\Phi}_{0,0,h}}{||\mathbf{\Phi}_{1,1,h-1}||_{1}}-\frac{\mathbf{I}}{n}\right|\right|_{2}^{2}$
$\displaystyle\leq\exp\left(-4\beta\ln
k\right)+\frac{3\mathcal{T}}{4d^{c-2\mathcal{T}-4}}\ =\
\frac{1}{k^{4\beta}}+\frac{3\mathcal{T}}{4d^{c-2\mathcal{T}-4}}\ .$

Given that $c\geq 5\beta+2\mathcal{T}+4$ and $d>k$ we have that

$\displaystyle\left|\left|\frac{\mathbf{\Phi}_{0,0,h}}{||\mathbf{\Phi}_{1,1,h-1}||_{1}}-\frac{\mathbf{I}}{n}\right|\right|_{2}^{2}$
$\displaystyle\leq\frac{1}{k^{4\beta}}+\frac{3\mathcal{T}}{4d^{5\beta}}\ .$

And for $d\geq k$ and $\beta\geq\log_{k}(3\mathcal{T})$, it is

$\displaystyle\left|\left|\frac{\mathbf{\Phi}_{0,0,h}}{||\mathbf{\Phi}_{1,1,h-1}||_{1}}-\frac{\mathbf{I}}{n}\right|\right|_{2}^{2}$
$\displaystyle\leq\frac{5}{4k^{4\beta}}\leq\frac{1}{k^{2\beta}}\ ,\textrm{ for
$\beta\geq 1/2$ and $k\geq 2$}\ .$

Given that
$(\Phi_{0,0,h}[v]/||\mathbf{\Phi}_{1,1,h-1}||_{1}-1/n)^{2}\leq\left|\left|\frac{\mathbf{\Phi}_{0,0,h}}{||\mathbf{\Phi}_{1,1,h-1}||_{1}}-\frac{\mathbf{I}}{n}\right|\right|_{2}^{2}$
for any node $v$, we have that
$(\Phi_{0,0,h}[v]/||\mathbf{\Phi}_{1,1,h-1}||_{1}-1/n)^{2}\leq 1/k^{2\beta}$
and hence
$\Phi_{0,0,h}[v]\geq(1/n-1/k^{\beta})||\mathbf{\Phi}_{1,1,h-1}||_{1}$. The
latter is true for any initial distribution and any phase $h$. Therefore,
after each phase a supervisor node consumes at least $1/n-1/k^{\beta}$
fraction of the total potential in the system, and the total potential in the
system drops by at most $\ell(1/n+1/k^{\beta})$ fraction. Recall that the
initial overall potential in the system is $\ell(n-\ell)$, and that by Claim
1, if $d>n$, the overall potential in the system does not change during each
phase.

Using the latter observations, after $p$ phases, any given supervisor node
consumes at least

$\displaystyle\rho$
$\displaystyle\geq\ell(n-\ell)\left(\frac{1}{n}-\frac{1}{k^{\beta}}\right)\sum_{i=0}^{p-1}\left(1-\ell\left(\frac{1}{n}+\frac{1}{k^{\beta}}\right)\right)^{i}.$

Given that $0<\ell\left(\frac{1}{n}+\frac{1}{k^{\beta}}\right)<1$ for
$\beta\geq 2$ and $k>\ell$, we have that

$\displaystyle\rho$
$\displaystyle\geq\ell(n-\ell)\left(\frac{1}{n}-\frac{1}{k^{\beta}}\right)\frac{1-\left(1-\ell\left(\frac{1}{n}+\frac{1}{k^{\beta}}\right)\right)^{p}}{1-\left(1-\ell\left(\frac{1}{n}+\frac{1}{k^{\beta}}\right)\right)}\
=\
(n-\ell)\frac{k^{\beta}-n}{k^{\beta}+n}\left(1-\left(1-\ell\left(\frac{1}{n}+\frac{1}{k^{\beta}}\right)\right)^{p}\right)\
.$

Again using that $0<\ell\left(\frac{1}{n}+\frac{1}{k^{\beta}}\right)<1$ for
$\beta\geq 2$ and $k>\ell$, and given that $1-x\leq e^{-x}$ for any $0<x<1$
[45], we have

$\displaystyle\rho$
$\displaystyle\geq(n-\ell)\frac{k^{\beta}-n}{k^{\beta}+n}\left(1-\exp\left(-p\ell\left(\frac{1}{n}+\frac{1}{k^{\beta}}\right)\right)\right)\
,\textrm{ replacing }p\geq\frac{2\delta\ln
k}{\ell\left(\frac{1}{n}+\frac{1}{k^{\beta}}\right)}\ ,$
$\displaystyle\geq(n-\ell)\frac{k^{\beta}-n}{k^{\beta}+n}\left(1-\frac{1}{k^{2\delta}}\right)\
\geq\
(n-\ell)\frac{k^{\beta}-n}{k^{\beta}+n}\left(1+\frac{1}{k^{\delta}}\right)\left(1-\frac{1}{k^{\delta}}\right)\
\geq\ (n-\ell)\left(1-\frac{1}{k^{\delta}}\right)\ .$

The latter inequality holds for $\beta\geq\log_{k}(n(2k^{\delta}+1))$. Then,
to complete the proof, it is enough to show that

$\displaystyle(n-\ell)\left(1-\frac{1}{k^{\delta}}\right)$
$\displaystyle>(k-\ell)\left(1+\frac{1}{k^{\gamma}}\right)\ .$

Which is true for $k<n$,
$\delta>\log_{k}(nk^{\gamma}/(nk^{\gamma}-(n-1)(k^{\gamma}+1)))$ and
$\gamma>\log_{k}(n-1)$. ∎

We now consider the case $k^{1+\epsilon}<n$. We focus on the first phase. We
define a threshold $\tau$ and a number of rounds $r$ such that, after the
phase is completed, all nodes that have potential above $\tau$ can send an
alarm to the leader, as such potential indicates that the estimate is low.

In order to do that, we first establish an upper bound of at most
$k^{1+\epsilon}$ nodes with potential at most $\tau$ at the end of the first
phase (Lemma 4). Given that $k^{1+\epsilon}<n$, using this lemma we know that
there is at least one node with potential above $\tau$ at the end of the first
phase. Second, we show that if the estimate is not low, that is $k\geq n$,
then all nodes have potential at most $\tau$ at the end of the first phase
(Lemma 5). That is, a potential above $\tau$ can only happen when indeed the
estimate is low. Finally, we show that if $k^{1+\epsilon}<n$ an alarm “low”
initiated by nodes with potential above $\tau$ must be received after
$k^{1+\epsilon}$ further rounds of communication (Lemma 6).

######  Lemma 4.

Consider an ADCS with a $\mathcal{T}$-connected evolving graph topology with
$\ell>0$ supervisors and $n-\ell>0$ supervised nodes running the RMC protocol.
For $\epsilon>0$, after running the first phase, there are at most
$k^{1+\epsilon}$ nodes that have potential at most
$\tau=\ell(1-\ell/k^{1+\epsilon})$.

###### Proof.

We define the _slack_ of node $x$ at the beginning of round $\langle
i,j,h\rangle$ as $s_{i,j,h}[x]=\ell-\Phi_{i,j,h}[x]$ and the vector of slacks
at the beginning of round $\langle i,j,h\rangle$ as $\mathbf{s}_{i,j,h}$. In
words, the slack of a node is the “room” for additional potential up to
$\ell$. Recall that the overall potential at the beginning of round $\langle
1,1,1\rangle$ is $||\mathbf{\Phi}_{1,1,1}||_{1}=(n-\ell)\ell$. Also notice
that for any round and any node $x$ the potential of $x$ is non-negative as
shown in Claim 2. Therefore, the overall slack at the beginning of round
$\langle 1,1,1\rangle$ with respect to $\ell$ is
$||\mathbf{s}_{1,1,1}||_{1}=\ell^{2}$.

Consider a partition of the set of nodes $\\{L,H\\}$, where $L$ is the set of
nodes with potential at most $\tau$ at the end of the first phase, before the
supervisor nodes consume their own potential in Line 3.3. That is,
$\Phi_{0,0,2}[x]\leq\tau$ for all $x\in L$ (and $\Phi_{0,0,2}[y]>\tau$ for all
$y\in H$). Assume that the slack held by nodes in $L$ at the end of the first
phase is at most the overall slack at the beginning of the phase. That is,
$\sum_{x\in L}s_{0,0,2}[x]\leq\ell^{2}$. By definition of $L$, we have that
for each node $x\in L$ it is $s_{0,0,2}[x]=\ell-\Phi_{0,0,2}[x]\geq\ell-\tau$.
Therefore, $|L|(\ell-\tau)\leq\sum_{x\in L}s_{0,0,2}[x]\leq\ell^{2}$. Thus,
$|L|\leq\ell^{2}/(\ell-\tau)=k^{1+\epsilon}$ (because
$\tau=\ell(1-\ell/k^{1+\epsilon})$) and the claim follows.

Then, to complete the proof, it remains to show that $\sum_{x\in
L}s_{0,0,2}[x]\leq\ell^{2}$. Let the scenario where $d/2$ is larger than the
number of neighbors that each node has in each round of the first phase be
called “case 1”, and “case 2” otherwise. Claim 1 shows that in case 1 at the
end of the first phase it is
$||\mathbf{\Phi}_{0,0,2}||_{1}=||\mathbf{\Phi}_{1,1,1}||_{1}=\ell(n-\ell)$.
Therefore, the slack held by all nodes is
$||\mathbf{s}_{0,0,2}||_{1}=\ell^{2}$ and thus the slack held by nodes in
$L\subseteq V$ is $\sum_{x\in L}s_{0,0,2}[x]\leq\ell^{2}$, proving the claim
for case 1. We show now that, in fact, case 1 is a worst-case scenario. That
is, in the complementary case 2 where some nodes have $d/2$ neighbors or more
in one or more rounds, the slack is even smaller. To compare both scenarios we
denote the slack for each round $\langle i,j,h\rangle$, each node $x$, and
each case $i$ as $s^{(i)}_{i,j,h}[x]$.

Assume that some node $x\in L$ is the first one to have $d^{\prime}\geq d/2$
neighbors. Let round $\langle i,j,1\rangle$ be the first one in the first
phase when this event happened. We claim that $\sum_{x\in
L}s^{(2)}_{i+1,j,1}[x]\leq\sum_{x\in L}s^{(1)}_{i+1,j,1}[x]$. The reason is
the following. Given that at least $d/2$ potentials are received, node $x$
changes its potential to $\ell$ for the rest of the epoch (refer to Lines 3.3
and 4.4). And given that $x\in L$, its potential before changing was at most
$\tau<\ell$. That is, the slack of $x$ is $s_{i+1,j,1}^{(2)}[x]\leq
s_{i,j,1}^{(2)}[x]=s_{i,j,1}^{(1)}[x]$. Additionally, given that
$d^{\prime}\geq d/2$ the potential shared by $x$ with _all_ neighbors during
round $\langle i,j,1\rangle$ in case 2 is not less than the potential that $x$
would have shared in case 1 when $|N|<d/2$ (refer to Lines 3.3 and 4.4). Then,
combining both effects (the relative increase in potential of $x$ and its
neighbors’) it is $s_{i+1,j,1}^{(2)}[x]\leq
s_{i,j,1}^{(2)}[x]=s_{i,j,1}^{(1)}[x]$. The same argument applies to all other
nodes in $L$ with $d/2$ or more neighbors in round $i,j,1$. Thus, it is
$\sum_{x\in L}s^{(2)}_{i+1,j,1}[x]\leq\sum_{x\in L}s^{(1)}_{i+1,j,1}[x]$.

Additionally, for any round $\langle i^{\prime}j^{\prime},1\rangle$ after
round $\langle i,j,1\rangle$, we have to also consider the case of a node
$y\in L$ that, although it does not receive at least $d/2$ potentials, it
moves to alarm status “low” because it has received such status in round
$\langle i^{\prime}j^{\prime},1\rangle$. Then, notice that the potential of
$y$ is
$\Phi_{i^{\prime}+1,j^{\prime},1}[y]=\ell>\tau\geq\Phi_{i^{\prime},j^{\prime},1}[y]$
because $y\in L$, and it will stay in $\ell$ for the rest of the epoch (refer
to Lines 3.3 and 4.4). Therefore, the slack of $y$ is
$s_{i^{\prime}+1,j^{\prime},1}^{(2)}[y]\leq
s_{i^{\prime}+1,j^{\prime},1}^{(1)}[y]$, and $\sum_{y\in
L}s^{(2)}_{i^{\prime}+1,j^{\prime},1}[y]\leq\sum_{y\in
L}s^{(1)}_{i^{\prime}+1,j^{\prime},1}[y]$.

Combining all the effects studied over all rounds, we get the sought
$\sum_{x\in L}s_{0,0,2}[x]\leq\sum_{x\in L}s_{1,1,1}[x]\leq\ell^{2}$.

∎

######  Lemma 5.

Consider an ADCS with a $\mathcal{T}$-connected evolving graph topology with
$\ell>0$ supervisors and $n-\ell>0$ supervised nodes running the RMC protocol
with parameters $d>k$, $p>0$, $r\geq\mathcal{T}b$,
$b\geq\left(5+2\epsilon-2\log_{k}(k^{\epsilon}-1)\right)\ln
k/\phi_{\min}^{2}$, and $c\geq
5+2\epsilon-2\log_{k}(k^{\epsilon}-1)+2\mathcal{T}+4+\alpha$, where
$\epsilon>0$, and $\alpha\geq\log_{k}(3\mathcal{T})$. Then, if $k\geq n$, at
the end of the first phase no individual node has potential larger than
$\tau=\ell(1-\ell/k^{1+\epsilon})$.

###### Proof.

Given that $d\geq n$ and $c>\log_{d}\mathcal{T}+1$, we have from Eq. 8 that
right before the beginning of phase $2$ it is

$\displaystyle\left|\left|\frac{\mathbf{\Phi}_{0,0,2}}{||\mathbf{\Phi}_{1,1,1}||_{1}}-\frac{\mathbf{I}}{n}\right|\right|_{2}^{2}$
$\displaystyle\leq\exp\left(-b\phi_{\min}^{2}\right)+\frac{3\mathcal{T}}{4d^{c-2\mathcal{T}-4}}\
.$

Given that $b\geq\left(5+2\epsilon-2\log_{k}(k^{\epsilon}-1)\right)\ln
k/\phi_{\min}^{2}$, it is

$\displaystyle\left|\left|\frac{\mathbf{\Phi}_{0,0,2}}{||\mathbf{\Phi}_{1,1,1}||_{1}}-\frac{\mathbf{I}}{n}\right|\right|_{2}^{2}$
$\displaystyle\leq\frac{1}{k^{5+2\epsilon-2\log_{k}(k^{\epsilon}-1)}}+\frac{3\mathcal{T}}{4d^{c-2\mathcal{T}-4}}\
.$

Replacing $\alpha\geq\log_{k}(3\mathcal{T})$ and $d\geq k$ we have that

$\displaystyle\left|\left|\frac{\mathbf{\Phi}_{0,0,2}}{||\mathbf{\Phi}_{1,1,1}||_{1}}-\frac{\mathbf{I}}{n}\right|\right|_{2}^{2}$
$\displaystyle\leq\frac{1}{k^{5+2\epsilon-2\log_{k}(k^{\epsilon}-1)}}+\frac{1}{4k^{c-2\mathcal{T}-4-\alpha}}\
.$

For $c\geq 5+2\epsilon-2\log_{k}(k^{\epsilon}-1)+2\mathcal{T}+4+\alpha$ we
have that

$\displaystyle\left|\left|\frac{\mathbf{\Phi}_{0,0,2}}{||\mathbf{\Phi}_{1,1,1}||_{1}}-\frac{\mathbf{I}}{n}\right|\right|_{2}^{2}$
$\displaystyle\leq\frac{5}{4k^{5+2\epsilon-2\log_{k}(k^{\epsilon}-1)}}\leq\frac{1}{k^{4+2\epsilon-2\log_{k}(k^{\epsilon}-1)}}\
.$

The latter is true because $k\geq 2$.

Given that for any node $j$, it is
$(\Phi_{0,0,2}[j]/||\mathbf{\Phi}_{1,1,1}||_{1}-1/n)^{2}\leq\left|\left|\frac{\mathbf{\Phi}_{0,0,2}}{||\mathbf{\Phi}_{1,1,1}||_{1}}-\frac{\mathbf{I}}{n}\right|\right|_{2}^{2}$,
we have that $(\Phi_{0,0,2}[j]/||\mathbf{\Phi}_{1,1,1}||_{1}-1/n)^{2}\leq
1/k^{4+2\epsilon-2\ln(k^{\epsilon}-1)/\ln k}$. Hence, it is
$\Phi_{0,0,2}[j]\leq(1/n+1/k^{2+\epsilon-\log_{k}(k^{\epsilon}-1)})||\mathbf{\Phi}_{1,1,1}||_{1}$
for any node $j$. Moreover, given that $d>k\geq n$ the total potential in the
network is $\ell(n-\ell)$ (Claim 1). Thus, no individual node should have
potential larger than
$\ell(n-\ell)(1/n+1/k^{2+\epsilon-\log_{k}(k^{\epsilon}-1)})$. We show that
the latter is at most $\tau=\ell(1-\ell/k^{1+\epsilon})$ as follows. We want
to prove

$\displaystyle\ell(n-\ell)\left(\frac{1}{n}+\frac{1}{k^{2+\epsilon-\log_{k}(k^{\epsilon}-1)}}\right)$
$\displaystyle\leq\ell\left(1-\frac{\ell}{k^{1+\epsilon}}\right)$
$\displaystyle\frac{n-\ell}{k^{2+\epsilon-\log_{k}(k^{\epsilon}-1)}}$
$\displaystyle\leq\frac{\ell}{n}-\frac{\ell}{k^{1+\epsilon}}.$

Given that $k\geq n$, it is enough to show that

$\displaystyle\frac{k-\ell}{k^{2+\epsilon-\log_{k}(k^{\epsilon}-1)}}$
$\displaystyle\leq\frac{\ell}{k}-\frac{\ell}{k^{1+\epsilon}}$ $\displaystyle
k-\ell$ $\displaystyle\leq\ell(k^{\epsilon}-1)k^{1-\log_{k}(k^{\epsilon}-1)}$
$\displaystyle k-\ell$ $\displaystyle\leq\ell k\ .$

And the latter is true because $\ell\geq 1$. ∎

The previous lemma shows that, if the estimate is “not-low” ($k\geq n$), at
the end of the first phase all nodes must have “low” potential
($\Phi_{0,0,2}\leq\tau$). (Notice the inverse relation between estimate and
potential.) So, to complete the proof of the case $k^{1+\epsilon}<n$ (i.e. low
estimate) we show in the following lemma that if $k^{1+\epsilon}<n$ (i.e. low
estimate) there are some nodes with $\Phi_{0,0,2}>\tau$ (i.e. high potential),
and that all the other nodes will know this within the following phase.

######  Lemma 6.

Consider an ADCS with a $\mathcal{T}$-connected evolving graph topology with
$\ell>0$ supervisors and $n-\ell>0$ supervised nodes running the RMC protocol
with parameters $d>k$, $p>1$ and $r\geq\mathcal{T}b$, where
$b\geq\left(5+2\epsilon-2\log_{k}(k^{\epsilon}-1)\right)\ln
k/\min\left\\{{\phi_{\min}}^{2},\ln(1+i_{\min})\right\\}$, and $\epsilon>0$.
Then, if $k^{1+\epsilon}<n$, within the second phase all nodes receive an
alarm status “low”.

###### Proof.

Consider a partition $\\{L,H\\}$ of the set of nodes, where $L$ is the set of
nodes with potential at most $\tau$ at the end of the first phase. As shown in
Lemma 4 the size of $L$ is at most $k^{1+\epsilon}$, and because
$k^{1+\epsilon}<n$ the size of $H$ is at least $1$.

Based on their “high” potential (above $\tau$), and the property proved in
Lemma 5 that in case of not-low estimate, $k\geq n$ there would not be any
node like them (notice that $b$ fulfills the condition of such lemma), all
nodes in $H$ move to alarm status “low” at the end of phase $1$ (refer to
Lines 3.3 or 4.4). (Notice the inverse relation between potential and status,
which in turn indicates whether the estimate is low or not.) We want to
compute the number of blocks until every node $L$ has received the low alarm.

Using the same argument used in Lemma 1, it can be proved that $\ln
d/\ln(1+i_{\min})$ blocks are enough to disseminate the alarm throughout the
network. Therefore, within the following $(1+\epsilon)\ln k/\ln(1+i_{\min})$
blocks after the beginning of the second phase any $x\in L$ receives the
alarm. Given that $b$ is larger, the claim follows. ∎

Finally, to complete the proof of correctness, we show in the following lemma
that if $k>n$, supervisor nodes detect that the potential consumed is too low
for the estimate $k$ to be correct.

######  Lemma 7.

Consider an ADCS with a $\mathcal{T}$-connected evolving graph topology with
$\ell>0$ supervisors and $n-\ell>0$ supervised nodes running the RMC protocol
with parameters $d>k$,

$p\leq 2\delta\ln
k\frac{1-\ell\left(\frac{1}{n}-\frac{1}{k^{\beta}}\right)}{\ell\left(\frac{1}{n}-\frac{1}{k^{\beta}}\right)}\
,$

$r\geq\mathcal{T}b,\ b\geq 4\beta\ln k/\phi_{\min}^{2}$, and $c\geq
5\beta+2\mathcal{T}+4$, where $\beta\geq\log_{k}(n(2k^{\delta}-1))$,
$\gamma>\log_{k}(n-\ell+1)$, and

$\delta>\log_{k}\frac{k^{\gamma}(n-\ell)}{k^{\gamma}-(n-\ell)-1}\ .$

Then, if $k>n$, the potential $\rho$ consumed by any supervisor node is
$\rho<(k-\ell)\left(1-1/k^{\gamma}\right)$.

###### Proof.

Given that $d>k>n$ and $c\geq 5\beta+4\mathcal{T}+2>\log_{d}2\mathcal{T}+1$,
we have from Eq. 8 that right before the beginning of any phase $h>1$ it is

$\displaystyle\left|\left|\frac{\mathbf{\Phi}_{0,0,h}}{||\mathbf{\Phi}_{1,1,h-1}||_{1}}-\frac{\mathbf{I}}{n}\right|\right|_{2}^{2}$
$\displaystyle\leq\exp\left(-b\phi_{\min}^{2}\right)+\frac{3\mathcal{T}}{4d^{c-2\mathcal{T}-4}}.$

For a number of blocks $b\geq 4\beta\ln k/\phi_{\min}^{2}$, it is

$\displaystyle\left|\left|\frac{\mathbf{\Phi}_{0,0,h}}{||\mathbf{\Phi}_{1,1,h-1}||_{1}}-\frac{\mathbf{I}}{n}\right|\right|_{2}^{2}$
$\displaystyle\leq\exp\left(-4\beta\ln
k\right)+\frac{3\mathcal{T}}{4d^{c-2\mathcal{T}-4}}\ =\
\frac{1}{k^{4\beta}}+\frac{3\mathcal{T}}{4d^{c-2\mathcal{T}-4}}\ .$

Given that $c\geq 5\beta+2\mathcal{T}+4$ and $d>k$ we have that

$\displaystyle\left|\left|\frac{\mathbf{\Phi}_{0,0,h}}{||\mathbf{\Phi}_{1,1,h-1}||_{1}}-\frac{\mathbf{I}}{n}\right|\right|_{2}^{2}$
$\displaystyle\leq\frac{1}{k^{4\beta}}+\frac{3\mathcal{T}}{4d^{5\beta}}\ .$

And for $d\geq k$ and $\beta\geq\log_{k}(3\mathcal{T})$, it is

$\displaystyle\left|\left|\frac{\mathbf{\Phi}_{0,0,h}}{||\mathbf{\Phi}_{1,1,h-1}||_{1}}-\frac{\mathbf{I}}{n}\right|\right|_{2}^{2}$
$\displaystyle\leq\frac{5}{4k^{4\beta}}\leq\frac{1}{k^{2\beta}}\ ,\textrm{ for
$\beta\geq 1/2$ and $k\geq 2$}\ .$

For any node $j$, given that
$(\Phi_{0,0,h}[j]/||\mathbf{\Phi}_{1,1,h-1}||_{1}-1/n)^{2}\leq\left|\left|\frac{\mathbf{\Phi}_{0,0,h}}{||\mathbf{\Phi}_{1,1,h-1}||_{1}}-\frac{\mathbf{I}}{n}\right|\right|_{2}^{2}$
we have that $(\Phi_{0,0,h}[j]/||\mathbf{\Phi}_{1,1,h-1}||_{1}-1/n)^{2}\leq
1/k^{2\beta}$ and hence
$\Phi_{0,0,h}[j]\geq(1/n-1/k^{\beta})||\mathbf{\Phi}_{1,1,h-1}||_{1}$. The
latter is true for any initial distribution. Therefore, after each phase a
supervisor node consumes at most $1/n+1/k^{\beta}$ fraction of the total
potential in the system, and the total potential in the system drops by at
least $\ell(1/n-1/k^{\beta})$ fraction. Recall that the initial overall
potential in the system is $\ell(n-\ell)$, and that by Claim 1, if $d>n$, the
overall potential in the system does not change during each phase.

Using the latter observations, after $p$ phases, any given supervisor node
consumes at most

$\displaystyle\rho$
$\displaystyle\leq\ell(n-\ell)\left(\frac{1}{n}+\frac{1}{k^{\beta}}\right)\sum_{i=0}^{p-1}\left(1-\ell\left(\frac{1}{n}-\frac{1}{k^{\beta}}\right)\right)^{i}.$

Given that $0<\ell\left(\frac{1}{n}-\frac{1}{k^{\beta}}\right)<1$ for
$\beta\geq 1$ and $k>n>\ell$, we have that

$\displaystyle\rho$
$\displaystyle\leq\ell(n-\ell)\left(\frac{1}{n}+\frac{1}{k^{\beta}}\right)\frac{1-\left(1-\ell\left(\frac{1}{n}-\frac{1}{k^{\beta}}\right)\right)^{p}}{1-\left(1-\ell\left(\frac{1}{n}-\frac{1}{k^{\beta}}\right)\right)}(n-\ell)\frac{k^{\beta}+n}{k^{\beta}-n}\left(1-\left(1-\ell\left(\frac{1}{n}-\frac{1}{k^{\beta}}\right)\right)^{p}\right)\
.$

Again using that $0<\ell\left(\frac{1}{n}-\frac{1}{k^{\beta}}\right)<1$ for
$\beta\geq 1$ and $k>n>\ell$, we have that

$\displaystyle\rho$
$\displaystyle\leq(n-\ell)\frac{k^{\beta}+n}{k^{\beta}-n}\left(1-\exp\left(-p\frac{\ell\left(\frac{1}{n}-\frac{1}{k^{\beta}}\right)}{1-\ell\left(\frac{1}{n}-\frac{1}{k^{\beta}}\right)}\right)\right)\
,\textrm{ replacing }p\leq 2\delta\ln
k\frac{1-\ell\left(\frac{1}{n}-\frac{1}{k^{\beta}}\right)}{\ell\left(\frac{1}{n}-\frac{1}{k^{\beta}}\right)}\
,$
$\displaystyle\leq(n-\ell)\frac{k^{\beta}+n}{k^{\beta}-n}\left(1-\frac{1}{k^{2\delta}}\right)\
=\
(n-\ell)\frac{k^{\beta}+n}{k^{\beta}-n}\left(1+\frac{1}{k^{\delta}}\right)\left(1-\frac{1}{k^{\delta}}\right)\
\leq\ (n-\ell)\left(1+\frac{1}{k^{\delta}}\right)\ .$

The latter inequality holds for $\beta\geq\log_{k}(n(2k^{\delta}-1))$ and
$\delta\geq\log_{k}(3/2)$, The second inequality is true because
$\log_{k}\frac{k^{\gamma}(n-\ell)}{k^{\gamma}-(n-\ell)-1}>\log_{k}(3/2)$ for
$k>n>\ell>0$. Then, to complete the proof, it is enough to show that

$\displaystyle(n-\ell)\left(1+\frac{1}{k^{\delta}}\right)$
$\displaystyle<(k-\ell)\left(1-\frac{1}{k^{\gamma}}\right)\ ,$

which is true for $k>n$,
$\delta>\log_{k}\frac{k^{\gamma}(n-\ell)}{k^{\gamma}-(n-\ell)-1}$ and
$\gamma>\log_{k}(n-\ell+1)$. Hence, the claim follows. ∎

We establish the correctness and running time of RMC in the following theorem.

######  Theorem 4.

Consider an ADCS with a $\mathcal{T}$-connected evolving graph topology with
$\ell>0$ supervisors and $n-\ell>0$ supervised nodes running the RMC protocol
with parameters:

$\displaystyle d$ $\displaystyle=2k^{1+\epsilon}\ ,$ $\displaystyle p$
$\displaystyle=\left\lceil\frac{2\ln
k}{\ell}\max\left\\{\frac{\gamma}{1/k+1/k^{\alpha}},\frac{\delta}{1/d+1/k^{\beta}}\right\\}\right\rceil\
,$ $\displaystyle r$ $\displaystyle=\lceil\mathcal{T}b\rceil\ ,$
$\displaystyle\tau$ $\displaystyle=\ell(1-\ell/k^{1+\epsilon})\ ,$
$\displaystyle c$ $\displaystyle\geq
2\mathcal{T}+4+\max\\{5\beta,5+\alpha+2\epsilon-2\log_{k}(k^{\epsilon}-1)\\}\
,$

where the number of blocks $b$ is the following.

_(i)_ If the isoperimetric number $i_{\min}$ is known:

$\displaystyle
b=\max\left\\{\alpha,\beta,5+2\epsilon-2\log_{k}(k^{\epsilon}-1)\right\\}2^{2\mathcal{T}(2+\epsilon)}\frac{n^{2\mathcal{T}(1+\epsilon)}}{i_{\min}^{2}}\ln
k.$ (12)

_(ii)_ Otherwise:

$\displaystyle
b=\max\left\\{\alpha,\beta,5+2\epsilon-2\log_{k}(k^{\epsilon}-1)\right\\}2^{2\mathcal{T}(2+\epsilon)-2}n^{2+2\mathcal{T}(1+\epsilon)}\ln
k.$

Then, under the following conditions:

$\displaystyle\alpha$
$\displaystyle\geq\max\\{1+\gamma+\log_{k}3,\log_{k}(3\mathcal{T})\\}\ ,$
$\displaystyle\beta$
$\displaystyle\geq\log_{k}\max\\{d(2k^{\delta}+1),3\mathcal{T}\\}\ ,$
$\displaystyle\gamma$ $\displaystyle>\log_{k}(d-1)\ ,$ $\displaystyle\delta$
$\displaystyle>\log_{k}\frac{dk^{\gamma}}{k^{\gamma}+1-d}\ ,$
$\displaystyle\epsilon$ $\displaystyle>0\ ,$ $\displaystyle\mathcal{T}$
$\displaystyle\in O(1),$

all nodes stop after at most $\sum_{k\in E\cup B}(pr+d)$ rounds of
communication and output $n$, for $E=\\{2^{i}(\ell+1):i=0,1,\dots,\log\lceil
n/(\ell+1)\rceil\\}$, and $B=\\{(2^{\log\lceil
n/(\ell+1)\rceil}-2^{i})(\ell+1):i=0,1,\dots,\log\lceil
n/(\ell+1)\rceil-2\\}$.

###### Proof.

The proof of correctness of the computation and running time for Part _(i)_ is
similar to [35], adapted to our parameters and applying the bound on
conductance in Eq. 1, and Part _(ii)_ is obtained applying the lower bound
$i_{\min}\geq 2/n$ to Equation 12.

About the ADCS limitations, messages sent by nodes are only their status and
potential. The status requires only 4 bits. Potentials are truncated to $c\log
d\leq c(1+(1+\epsilon)\log(2n))$ bits (refer to Lines 3.3 and 4.4) fulfilling
the restrictions on message size and memory access at the same time as long as
there exists a $c\in O(1)$, which can be seen replacing tight bounds on the
conditions above. ∎

In the following corollary we relate the knowledge of network characteristics
to the asymptotic running time of RMC.

######  Corollary 1.

The time complexity of RMC on an ADCS with $\ell>0$ supervisor nodes and
$n-\ell>0$ supervised nodes is the following.

_(i)_ If the isoperimetric number $i_{\min}$ is known:

$\displaystyle\widetilde{O}\left(\frac{n^{1+2\mathcal{T}(1+\epsilon)}}{\ell
i_{\min}^{2}}\right).$

_(ii)_ Otherwise:

$\displaystyle\widetilde{O}\left(\frac{n^{3+2\mathcal{T}(1+\epsilon)}}{\ell}\right).$

###### Proof.

Fixing $\gamma=\log_{k}d$ it would be
$\log_{k}\frac{dk^{\gamma}}{k^{\gamma}+1-d}=\log_{k}d^{2}=2(\log_{k}2+1+\epsilon)$.
That is, it is enough to set $\gamma=\log_{k}d$ and $\delta=2(2+\epsilon)$ to
meet the conditions on those parameters in Theorem 4. Replacing these and
$d=2k^{1+\epsilon}<2(2n)^{1+\epsilon}$,

$\displaystyle p$ $\displaystyle<\left\lceil\frac{2d\ln
d}{\ell}\right\rceil\in O\left(\frac{n\ln n}{\ell}\right)\ .$

Replacing $\gamma$ and $\delta$ in $\alpha$ and $\beta$, and $\mathcal{T}\in
O(1)$ it is

$\displaystyle r$ $\displaystyle\in
O\left(\frac{1}{\min\left\\{{\phi_{\min}}^{2},\ln(1+i_{\min})\right\\}}\right)\
.$

Then, it is

$\displaystyle pr+d$ $\displaystyle\in O\left(\frac{n\ln
n}{\ell\min\left\\{{\phi_{\min}}^{2},\ln(1+i_{\min})\right\\}}\right)\ .$

The total number of terms in the summation of the running time in Theorem 4 is
$O(\log\frac{n}{\ell})$, hence the claim follows. ∎

##  8 Discussion and Open Problems

Although the presented algorithm is the first that guarantees a polynomial
emulation of All-to-All Communication on the top of anonymous congested
highly-dynamic (and not necessarily always connected) systems, the main
challenges are to further shrink the polynomials and/or provide lower bounds
better than long-time known $\Omega(D+n\log n)$, where $D$ stands for temporal
diameter. We hypothesize that shrinking this complexity gap may depend on
computational power, for instance, being able to process history trees may
allow provably faster All-to-All Communication.

## References

  * [1] Dana Angluin, James Aspnes, Zoë Diamadi, Michael J. Fischer, and René Peralta.  Computation in networks of passively mobile finite-state sensors.  Distributed Computing, 18(4):235–253, March 2006.
  * [2] Chen Avin, Michal Kouckỳ, and Zvi Lotker.  How to explore a fast-changing world (cover time of a simple random walk on evolving graphs).  In Automata, languages and programming, pages 121–132. Springer, 2008.
  * [3] Siddhartha Banerjee, Aditya Gopalan, Abhik Kumar Das, and Sanjay Shakkottai.  Epidemic spreading with external agents.  IEEE Transactions on Information Theory, 60(7):4125–4138, 2014\.
  * [4] Florent Becker, Antonio Fernández Anta, Ivan Rapaport, and Eric Reémila.  Brief announcement: A hierarchy of congested clique models, from broadcast to unicast.  In Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, pages 167–169, 2015.
  * [5] Stephen Boyd, Arpita Ghosh, Balaji Prabhakar, and Devavrat Shah.  Randomized gossip algorithms.  IEEE Transactions on Information Theory, 52(6):2508–2530, 2006\.
  * [6] Peter Buser.  On the bipartition of graphs.  Discrete applied mathematics, 9(1):105–109, 1984.
  * [7] Arnaud Casteigts, Paola Flocchini, Walter Quattrociocchi, and Nicola Santoro.  Time-varying graphs and dynamic networks.  International Journal of Parallel, Emergent and Distributed Systems, 27(5):387–408, 2012.
  * [8] Keren Censor-Hillel, Petteri Kaski, Janne H Korhonen, Christoph Lenzen, Ami Paz, and Jukka Suomela.  Algebraic methods in the congested clique.  Distributed Computing, 32(6):461–478, 2019.
  * [9] Keren Censor-Hillel, Merav Parter, and Gregory Schwartzman.  Derandomizing local distributed algorithms under bandwidth restrictions.  Distributed Computing, 33(3):349–366, 2020.
  * [10] Maitri Chakraborty, Alessia Milani, and Miguel A. Mosteiro.  Counting in practical anonymous dynamic networks is polynomial.  In Proceedings of the 4th International Conference on Networked Systems, volume 9944 of Lecture Notes in Computer Science, pages 131–136, 2016.
  * [11] Yuxin Chen, Sanjay Shakkottai, and Jeffrey G Andrews.  On the role of mobility for multimessage gossip.  IEEE Transactions on Information Theory, 59(6):3953–3970, 2013\.
  * [12] Giuseppe Antonio Di Luna and Roberto Baldoni.  Non Trivial Computations in Anonymous Dynamic Networks.  In Emmanuelle Anceaume, Christian Cachin, and Maria Potop-Butucaru, editors, Proceedings of the 19th International Conference on Principles of Distributed Systems, volume 46 of Leibniz International Proceedings in Informatics (LIPIcs), pages 1–16, Dagstuhl, Germany, 2016. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
  * [13] Giuseppe Antonio Di Luna, Roberto Baldoni, Silvia Bonomi, and Ioannis Chatzigiannakis.  Conscious and unconscious counting on anonymous dynamic networks.  In Proceedings of the 15th International Conference on Distributed Computing and Networking, volume 8314 of Lecture Notes in Computer Science, pages 257–271. Springer Berlin Heidelberg, 2014.
  * [14] Giuseppe Antonio Di Luna, Roberto Baldoni, Silvia Bonomi, and Ioannis Chatzigiannakis.  Counting in anonymous dynamic networks under worst-case adversary.  In Proceedings of the 34th International Conference on Distributed Computing Systems, pages 338–347. IEEE, 2014.
  * [15] Giuseppe Antonio Di Luna, Silvia Bonomi, Ioannis Chatzigiannakis, and Roberto Baldoni.  Counting in anonymous dynamic networks: An experimental perspective.  In Proceedings of the 9th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics, volume 8243 of Lecture Notes in Computer Science, pages 139–154. Springer Berlin Heidelberg, 2014.
  * [16] Danny Dolev, Christoph Lenzen, and Shir Peled.  “tri, tri again”: Finding triangles and small subgraphs in a distributed setting.  In International Symposium on Distributed Computing, pages 195–209. Springer, 2012.
  * [17] Andrew Drucker, Fabian Kuhn, and Rotem Oshman.  On the power of the congested clique model.  In Proceedings of the 2014 ACM symposium on Principles of distributed computing, pages 367–376, 2014.
  * [18] Martin Farach-Colton, Rohan J. Fernandes, and Miguel A. Mosteiro.  Bootstrapping a hop-optimal network in the weak sensor model.  ACM Trans. Algorithms, 5(4), nov 2009.
  * [19] A. Fernández Anta, M. A. Mosteiro, and C. Thraves.  Deterministic communication in the weak sensor model.  In Proc. of the 11th International Conference On Principles Of Distributed Systems, volume 4878 of Lecture Notes in Computer Science, pages 119–131. Springer-Verlag, Berlin, 2007.
  * [20] Antonio Fernández Anta, Miguel A. Mosteiro, and Christopher Thraves.  An early-stopping protocol for computing aggregate functions in sensor networks.  J. Parallel Distrib. Comput., 73(2):111–121, 2013.
  * [21] Mohsen Ghaffari.  An improved distributed algorithm for maximal independent set.  In Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms, pages 270–277. SIAM, 2016.
  * [22] Mohsen Ghaffari.  Distributed mis via all-to-all communication.  In Proceedings of the ACM symposium on principles of distributed computing, pages 141–149, 2017.
  * [23] Mohsen Ghaffari and Merav Parter.  Mst in log-star rounds of congested clique.  In Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, pages 19–28, 2016.
  * [24] George Giakkoupis.  Tight bounds for rumor spreading in graphs of a given conductance.  In Symposium on Theoretical Aspects of Computer Science (STACS2011), volume 9, pages 57–68, 2011.
  * [25] Seth Gilbert, Nancy A Lynch, and Alexander A Shvartsman.  R ambo: a robust, reconfigurable atomic memory service for dynamic networks.  Distributed Computing, 23(4):225–272, 2010.
  * [26] Bernhard Haeupler and David Karger.  Faster information dissemination in dynamic networks via network coding.  In Proceedings of the 30th annual ACM SIGACT-SIGOPS symposium on Principles of distributed computing, pages 381–390, 2011.
  * [27] James W Hegeman, Gopal Pandurangan, Sriram V Pemmaraju, Vivek B Sardeshmukh, and Michele Scquizzato.  Toward optimal bounds in the congested clique: Graph connectivity and mst.  In Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, pages 91–100, 2015.
  * [28] James W Hegeman and Sriram V Pemmaraju.  Lessons from the congested clique applied to mapreduce.  Theoretical Computer Science, 608:268–281, 2015.
  * [29] James W Hegeman, Sriram V Pemmaraju, and Vivek B Sardeshmukh.  Near-constant-time distributed algorithms on a congested clique.  In International Symposium on Distributed Computing, pages 514–530. Springer, 2014.
  * [30] Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai.  A deterministic almost-tight distributed algorithm for approximating single-source shortest paths.  SIAM Journal on Computing, 50(3):STOC16–98, 2019.
  * [31] D. Kempe, A. Dobra, and J. Gehrke.  Gossip-based computation of aggregate information.  In Proc. of the 44th IEEE Ann. Symp. on Foundations of Computer Science, pages 482–491, 2003.
  * [32] Janne H. Korhonen.  Deterministic MST sparsification in the congested clique.  CoRR, abs/1605.02022, 2016.
  * [33] Dariusz R Kowalski and Miguel A Mosteiro.  Polynomial counting in anonymous dynamic networks with applications to anonymous dynamic algebraic computations.  Journal of the ACM (JACM), 67(2):1–17, 2020.
  * [34] Dariusz R. Kowalski and Miguel A. Mosteiro.  Supervised average consensus in anonymous dynamic networks.  In Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures, SPAA ’21, page 307–317, New York, NY, USA, 2021\. Association for Computing Machinery.
  * [35] Dariusz R. Kowalski and Miguel A. Mosteiro.  Polynomial anonymous dynamic distributed computing without a unique leader.  J. Comput. Syst. Sci., 123:37–63, 2022.
  * [36] Fabian Kuhn, Nancy Lynch, and Rotem Oshman.  Distributed computation in dynamic networks.  In Proceedings of the forty-second ACM symposium on Theory of computing, pages 513–522, 2010.
  * [37] Fabian Kuhn, Nancy Lynch, and Rotem Oshman.  Distributed computation in dynamic networks.  In Proceedings of the 42nd ACM Symposium on Theory of Computing, pages 513–522. ACM, 2010.
  * [38] Fabian Kuhn and Rotem Oshman.  Dynamic networks: models and algorithms.  ACM SIGACT News, 42(1):82–96, 2011.
  * [39] Christoph Lenzen.  Optimal deterministic routing and sorting on the congested clique.  In Proceedings of the 2013 ACM symposium on Principles of distributed computing, pages 42–50, 2013.
  * [40] Zvi Lotker, Boaz Patt-Shamir, Elan Pavlov, and David Peleg.  Minimum-weight spanning tree construction in o (log log n) communication rounds.  SIAM Journal on Computing, 35(1):120–131, 2005.
  * [41] Othon Michail, Ioannis Chatzigiannakis, and Paul G Spirakis.  Naming and counting in anonymous unknown dynamic networks.  In Stabilization, Safety, and Security of Distributed Systems, pages 281–295. Springer, 2013.
  * [42] Othon Michail, Ioannis Chatzigiannakis, and Paul G Spirakis.  Causality, influence, and computation in possibly disconnected synchronous dynamic networks.  Journal of Parallel and Distributed Computing, 74(1):2016–2026, 2014.
  * [43] Milena Mihail.  Conductance and convergence of markov chains-a combinatorial treatment of expanders.  In FOCS, volume 89, pages 526–531, 1989.
  * [44] Alessia Milani and Miguel A. Mosteiro.  A faster counting protocol for anonymous dynamic networks.  In Proceedings of the 19th International Conference on Principles of Distributed Systems, volume 46 of Leibniz International Proceedings in Informatics, pages 1–13, 2015.
  * [45] D. S. Mitrinović.  Elementary Inequalities.  P. Noordhoff Ltd. - Groningen, 1964.
  * [46] Damon Mosk-Aoyama and Devavrat Shah.  Fast distributed algorithms for computing separable functions.  IEEE Transactions on Information Theory, 54(7):2997–3007, 2008\.
  * [47] R. Motwani and P. Raghavan.  Randomized Algorithms.  Cambridge University Press, 1995.
  * [48] Danupon Nanongkai.  Distributed approximation algorithms for weighted shortest paths.  In Proceedings of the forty-sixth annual ACM symposium on Theory of computing, pages 565–573, 2014.
  * [49] Regina O’Dell and Rogert Wattenhofer.  Information dissemination in highly dynamic graphs.  In Proceedings of the 2005 Joint Workshop on Foundations of Mobile Computing, DIALM-POMC ’05, page 104–110, New York, NY, USA, 2005. Association for Computing Machinery.
  * [50] Boaz Patt-Shamir and Marat Teplitsky.  The round complexity of distributed sorting.  In Proceedings of the 30th annual ACM SIGACT-SIGOPS symposium on Principles of distributed computing, pages 249–256, 2011.
  * [51] David Peleg.  Distributed computing: a locality-sensitive approach.  SIAM, Philadelphia, PA, USA, 2000.
  * [52] Sujay Sanghavi, Bruce Hajek, and Laurent Massoulié.  Gossiping with multiple messages.  IEEE Transactions on Information Theory, 53(12):4640–4654, 2007\.
  * [53] Atish Das Sarma, Anisur Rahaman Molla, and Gopal Pandurangan.  Distributed computation in dynamic networks via random walks.  Theoretical Computer Science, 581:45–66, 2015.
  * [54] Thomas Sauerwald and Luca Zanetti.  Random Walks on Dynamic Graphs: Mixing Times, Hitting Times, and Return Probabilities.  In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), volume 132 of Leibniz International Proceedings in Informatics (LIPIcs), pages 93:1–93:15. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2019.
  * [55] Alistair Sinclair and Mark Jerrum.  Approximate counting, uniform generation and rapidly mixing markov chains.  Information and Computation, 82(1):93–133, 1989.