# Polynomial Anonymous Dynamic Distributed Computing
without a Unique Leader††thanks: An extended abstract of this work has been
presented in [17].

Dariusz R. Kowalski School of Computer and Cyber Sciences, Augusta University,
GA, USA; SWPS University of Social Sciences and Humanities, Warsaw, Poland;
<EMAIL_ADDRESS>Miguel A. Mosteiro Computer Science Department, Pace
University, New York, NY, USA<EMAIL_ADDRESS>
###### Abstract

Counting the number of nodes in Anonymous Dynamic Networks is enticing from an
algorithmic perspective: an important computation in a restricted platform
with promising applications. Starting with Michail, Chatzigiannakis, and
Spirakis [19], a flurry of papers sped up the running time guarantees from
doubly-exponential to polynomial [16]. There is a common theme across all
those works: a distinguished node is assumed to be present, because Counting
cannot be solved deterministically without at least one.

In the present work we study challenging questions that naturally follow: how
to efficiently count with more than one distinguished node, or how to count
without any distinguished node. More importantly, what is the minimal
information needed about these distinguished nodes and what is the best we can
aim for (count precision, stochastic guarantees, etc.) without any. We present
negative and positive results to answer these questions. To the best of our
knowledge, this is the first work that addresses them.

##  1 Introduction

In the Anonymous Dynamic Network (ADN) model, network nodes lack any form of
identifiers, that is, they cannot be distinguished among themselves, and
communication links between nodes may change arbitrarily and continuously over
time.

The recent excitement around the problem of _Counting_ , i.e., computing the
number of nodes of an Anonymous Dynamic Networks comes as no surprise. On one
hand, knowing the number of computational entities is a fundamental
requirement to decide termination in a myriad of distributed algorithms. On
the other hand, ADN is a very restrictive scenario from an algorithmic
perspective. The combination of an important problem with harsh computational
conditions is any algorithmist’s delight.

Node anonymity in ADNs is motivated by expected applications of such
communication infrastructure. For instance, in ad-hoc networks embedded in the
Internet of Things, nodes may have to be deployed in a massive scale, and
having unique identifiers may simply be impractical or inconvenient. Moreover,
low node-cost expectations may introduce uncertainty about the number of nodes
that will effectively startup. Hence, the need of Counting.

Strikingly, the progress on deterministic Counting speed-ups over various
works ranged over a broad spectrum: from unbounded [11, 12] to polynomial time
[16], going through doubly-exponential [11] and exponential time [10, 7]. In
all that fruitful work, the ADN model has been equipped with one
distinguishable node111Exactly one, usually called _leader_. We refrain from
using the name leader to avoid confusion: in our model we may have more than
one, and in our algorithm they are not going to select a single one among
them. Moreover, they cannot even be local leaders, because due to ADN’s
dynamicity they may all be connected being their own (local) leaders.. The
assumption is well motivated: in a seminal paper [19], it was shown that,
without at least one such node, Counting cannot be solved deterministically.
But what if we have more than one special node? In what sense these nodes need
to be special? Is it enough to put one of two different programs on each of
the nodes, that otherwise are all identical? Moreover, can we let the nodes
choose at random which program to run and have no special nodes? To the best
of our knowledge, this is the first work that considers these questions.

As the more general case where all nodes are identical, only differentiated by
the program they run, let the set of $n$ network nodes be formed by $\ell$
_black_ nodes (the “special” ones) and $n-\ell$ _white_ nodes (the “regular”
ones). Our first contribution is negative results. On one hand, if $\ell$ is
unknown, Counting cannot be solved deterministically. On the other hand, we
show that there exist ADNs such that, if $\ell=0$ or $\ell$ is unknown to the
nodes, there is no Counting randomized algorithm such that, with constant
probability, each node outputs the correct count when it stops.

Even knowing how many black nodes are in the network, straightforward
application of previous ideas for Counting is not clear. Indeed, each black
node may carry its own count, but how do we combine or compare final counts?
Even passing messages among black nodes is challenging, because black nodes
are also indistinguishable among them and communication links change
arbitrarily. For instance, a black node is not able to tell whether a received
message is even its own, coming back after being previously sent for
dissemination.

Our second contribution is a deterministic Counting protocol that computes
exactly the number of network nodes. Our protocol uses no information about
the network, except the number of black nodes $\ell\geq 1$. After completing
its execution, all nodes obtain the exact size of the network and stop.
Moreover, they stop all at the same time, allowing the algorithm to be
concatenated with other computations.

This protocol resembles our Methodical Counting protocol presented in [16].
So, we call it Methodical multi-Counting (MMC). However, it is not a simple
combination of multiple instances of Methodical Counting to handle multiple
black nodes. We overcome the challenge of how to combine the actions of
multiple indistinguishable black nodes by careful design of a set of alarms,
so that _all_ black nodes can simultaneously detect when a running estimate of
the size is correct. Moreover, the asymptotic performance of MMC is
$O(n^{4+\epsilon}(\log^{3}n)/\ell)$, for an arbitrarily small $\epsilon>0$.
This is a speed-up by a factor arbitrarily close to $n\ell/\log n$ with
respect to Methodical Counting. That is, even for $\ell=1$, MMC is faster than
the best previous work (cf. Table 1).

In face of the impossibility of deterministic Counting without a distinguished
node [19], a natural question is what is possible introducing randomness. Our
impossibility results show that if $\ell=0$ or $\ell$ is unknown it is not
possible to solve Counting with a constant probability. Thus, we focus on a
weaker version of the problem called _Unconscious Counting_ [11]. In
Unconscious Counting nodes still compute the network size, but may not know
whether the number they have at the moment is precise or will be corrected
later (by additional communication received).

Our third contribution is an Unconscious Counting protocol that computes
exactly the number of nodes in an ADN where $\ell=0$ (no special nodes). That
is, for the first time it is possible to consider an ADN model where _all_
nodes are identical, indistinguishable, and run the same program. Our
protocol, called Leaderless Methodical Counting (LLMC), is Monte Carlo. That
is, there is a small probability at most $\zeta>0$ of obtaining the wrong
size, and the time of $O(\eta^{4+\epsilon}\log^{3}\eta)$, for
$\eta=\max\\{n,\lceil\lceil 12/\epsilon\rceil\rceil\\}$ and $\epsilon>0$, to
obtain the correct network size holds with probability at least $1-\zeta$ (cf.
Table 1).

To the best of our knowledge, this is the first comprehensive study of
Counting in ADNs where $\ell$ may be different than one.

Roadmap. The rest of the paper is organized as follows. We specify the model
and notation details in Section 2. The directly related work overviewed in
comparison with our results is summarized in Table 1. Further details on
previous work are included in Section 3. We present impossibility results in
Section 4. Sections 5 and 6 include the details of MMC and LLMC. References to
algorithms lines are given as $\langle algorithm\\#\rangle.\langle
line\\#\rangle$. We conclude this study with some open problems in Section 7.

##  2 Model, Problem, and Notation

#### Anonymous Dynamic Networks.

The following model is customary in the Anonymous Dynamic Networks literature.

We consider a network composed by a set $V$ of $n>1$ network _nodes_ with
processing and communication capabilities. Each pair of nodes that are able to
communicate defines a communication _link_ , and the set of links is called
the _topology_ of the network. The nodes in a communication link are called
_neighbors_.

Without loss of generality, we discretize time in _communication rounds_ or
_time slots_ indistinctively (or _rounds_ or _slots_ for short). In any given
round, a node may send a _message_ through all its communication links,
receive all messages from all sending neighbors, and carry out some (local)
computations, in that order. The time needed for computations is assumed
negligible with respect to the time needed for communication, and the size of
messages is not bounded.

The set of links among nodes may change from round to round222This dynamicity
is the reason for the term ”Dynamic” in Anonymous Dynamic Network.. These
topology changes are arbitrary, limited only to maintain the connectedness of
the network in each round. That is, at any given round the topology is such
that there is a _path_ , i.e., a sequence of links, between each pair of
nodes, but the set of links may change arbitrarily from round to round. This
adversarial model of dynamics is known as _$1$ -interval connectivity_ in
[18].

The event of sending a message to neighbors is called a _broadcast_ or
_transmission_. Nodes and links are reliable, in the sense that no link or
node failures occur. Hence, a broadcasted message is received by all current
neighbors. Moreover, links are _symmetric_ , that is, if node $a$ is able to
send a message to node $b$, then $b$ is able to send a message to $a$ in the
same round.

Nodes in the ADN model lack any form of identifiers333The lack of identifiers
is the reason for the term ”Anonymous” in the model’s name “Anonymous Dynamic
Network”.. That is, they are indistinguishable from any other node. However,
it was shown in [19] that the Counting Problem (defined below) cannot be
solved deterministically in Anonymous Networks without the availability of at
least one distinguished node in the network. Hence, all previous studies of
Counting in ADNs included in the model the presence of such node called the
_leader_. However, to the best of our knowledge, nothing is known about
deterministic Counting in presence of _multiple_ distinguished nodes. In this
work, we generalize the ADN model assuming that the number of distinguished
nodes is $\ell\geq 1$. Aside from the distinction between distinguished and
not-distinguished, all nodes are indistinguishable within their group.
Therefore, here we call them black nodes and white nodes, respectively. All
black nodes execute exactly the same program, and all white nodes execute
exactly the same program. That is, there are no identifiers that allow to
distinguish one black (resp. white) node from another black (resp. white)
node444Nodes are labeled throughout the paper only for the sake of
presentation and analysis..

#### The Counting Problem.

We define the Counting problem as follows.

###### Definition 1

An algorithm $\mathcal{A}$ solves the _Counting Problem_ if, after completing
its execution, all network nodes running $\mathcal{A}$ have obtained the size
of the network and stop (not necessarily concurrently).

Following up on [11], we also define a weaker version of Counting, as follows.

###### Definition 2

An algorithm $\mathcal{A}$ solves the _Unconscious Counting Problem_ if all
network nodes running $\mathcal{A}$ eventually obtain the size of the network
in finite time.

Notice that the definition of Unconscious Counting does not require the nodes
to know that they have obtained the correct count by the current round.
Consequently, Unconscious Counting algorithms may not satisfy a termination
condition.

Notice also that we focus on _exact_ Counting. That is, all nodes obtain the
exact size of the network $n$, rather than an approximation as other works.

We define now a class of Counting algorithms.

###### Definition 3

For a given algorithm $\mathcal{A}$, let an _execution_ of $\mathcal{A}$ be a
sequence of steps of $\mathcal{A}$ followed in one of the possible sequence of
choices made by $\mathcal{A}$. Let $\mathcal{X}(\mathcal{A})$ be the set of
all possible executions of $\mathcal{A}$. An algorithm $\mathcal{A}$ is called
_eventually stopping_ if, for all $X\in\mathcal{X}(\mathcal{A})$, $X$ has
finite length.

We will model worst case scenarios assuming the presence of an adversary that
controls the topology of the network. In particular, we consider the following
adversaries.

###### Definition 4

Let the sequence $\mathcal{E}=\langle E_{1},E_{2},\dots\rangle$ be the sets of
communication links of an ADN for time slots $t_{1},t_{2},\dots$. Consider the
execution of an algorithm $\mathcal{A}$. We say that an adversary is
_oblivious_ if it determines the sequence $\mathcal{E}$ completely before the
execution of $\mathcal{A}$ begins. On the other hand, we say that an adversary
is _adaptive_ if it determines the sequence $\mathcal{E}$ during the execution
of $\mathcal{A}$, according to the actions of $\mathcal{A}$.

Notice that the distinction between oblivious and adaptive makes sense only
for randomized algorithms, given that for deterministic algorithms the actions
of the algorithm are defined before the execution.

#### Notation.

The following notation will be used. In this work, the maximum number of
neighbors that any node may have at any given time, called the _dynamic
maximum degree_ , is denoted as $d_{\max}$.555Previous literature on ADNs
denotes the dynamic maximum degree as $\Delta$, which is classically used in
static networks to denote the maximum degree. We have chosen $d_{\max}$ to
avoid confusion with static networks notation. This choice is additionally
consistent with previous work on lazy random walks, where the degree is
denoted by $d$. The maximum length of a path between any pair of nodes at any
given time is called the _dynamic diameter_ and it is denoted as $D$. The
maximum length of an opportunistic path between any pair of nodes over many
time slots (i.e., a path that may not exist in its entirety at any given time,
but that it can be followed by a message along time as new links appear while
links already traversed may disappear) is called the _chronopath_ [14] and it
is denoted as $\mathcal{D}$.

Table 1: Statement of results and comparison with previous work.

algorithm | needs | computes | stops? | complexity
---|---|---|---|---
|  | distinguished
---
nodes
| size
---
upper
bound
$N$
| dynamic
---
maximum
degree u.b.
$d_{\max}$
time | space
| _Degree_
---
_Counting_ [19]
$1$ |  | ✓ | $O(d_{\max}^{n})$ | ✓ | $O(n)$ |
_Conscious_ [11] | $1$ | ✓ | ✓ | $n$ | ✓ |  | $O(e^{N^{2}}N^{3})\Rightarrow$
---
$O(e^{d_{\max}^{2n}}d_{\max}^{3n})$ using [19]
_Unconscious_ [11] | $1$ |  |  | $n$ | No |  | No theoretical
---
bounds
$\mathcal{A}_{\mathcal{O}^{P}}$ [12] | $1$ |  |  | Oracle
---
for each
node
$n$ | Eventually | Unknown |
EXT [10] | $1$ |  |  | $n$ | ✓ | $O(n^{n+4})$ | EXPSPACE
| Incremental
---
Counting [20]
$1$ |  | ✓ | $n$ | ✓ | $O\left(n\left(2d_{\max}\right)^{n+1}\frac{\ln n}{\ln d_{\max}}\right)$ |
| Methodical
---
Counting
[16]
$1$ |  |  | $n$ | ✓ | $O(n^{5}\ln^{2}n)$ | PSPACE
| Methodical
---
multi-Counting
$[$This work$]$
$\ell\geq 1$ |  |  | $n$ | ✓ |  | $O((n^{4+\epsilon}/\ell)\log^{3}n)$
---
for any $\epsilon>0$
PSPACE
| LLMC
---
$[$This work$]$
$0$ |  |  |  | $n$
---
prob. $\geq 1-\zeta$
No |  | $O((n+1/\zeta)^{4+\epsilon}\log^{3}(n+1/\zeta))$
---
for any $\epsilon>0$ and $\zeta>0$
PSPACE

##  3 Previous Work

A comprehensive overview of work related to ADNs can be found in a survey by
Casteigts et al. [5] and references in the papers cited here.

With respect to lower bounds, it was proved in [9] that at least $\Omega(\log
n)$ rounds are needed, even if $D$ is constant. Also, $\Omega(\mathcal{D})$ is
a lower bound since at least one node needs to hear about all other nodes to
obtain the right count.

Counting and _Naming_ was already studied in [19] for dynamic and static
networks, showing that it is impossible to solve Counting without the presence
of a distinguished node, even if nodes do not move. The Counting protocol
requires knowledge of an upper bound on the dynamic maximum degree of the
network $d_{\max}$, and obtains only an upper bound, which may be as bad as
exponential.

Conscious Counting [11] computes the exact count, but it needs to start from
an upper bound on the size, and it takes exponential time only if such upper
bound is tight up to constants. In the same work and follow-up papers [12,
13], more challenging scenarios where $d_{\max}$ is unknown are studied, but
protocols either do not terminate [11], or the protocol is terminated
heuristically [13]. In experiments [13], such heuristic was found to perform
well on dense topologies, but for other topologies the error rate was high.
Another protocol in [12] is shown to terminate eventually, without running-
time guarantees and under the assumption of having for each node an estimate
of the number of neighbors in each round. In [19] it was conjectured that some
knowledge of the network such as the latter would be necessary, but the
conjecture was disproved later in [10]. On the other hand the protocol in [10]
requires exponential space.

Incremental Counting, presented recently in [20], reduced exponentially the
best-known running time guarantees. The protocol obtains the exact count, all
nodes terminate simultaneously, the topology dynamics is only limited to
$1$-interval connectivity, it only requires polynomial space, and it only
requires knowledge of $d_{\max}$. The running time is still exponential, but
reducing from doubly-exponential was an important step towards understanding
the complexity of Counting.

In a follow-up paper [6], Incremental Counting was tested experimentally
showing a promising polynomial behavior. The study was conducted on
pessimistic inputs designed to slow the convergence, such as bounded-degree
trees rooted at the leader uniformly chosen at random for each round, and a
single path starting at the leader with non-leader nodes permuted uniformly at
random for each round. The protocol was also tested on static versions of the
inputs mentioned, classic random graphs, and networks where some disconnection
is allowed. The results showed that, even for topologies that stretch the
dynamic diameter, the running times obtained are below $d_{\max}n^{3}$. It was
also observed that random graphs, as used in previous experimental studies
[13], reduce the convergence time, and therefore are not a good choice to
indicate worst-case behavior. These experiments showed good behavior even for
networks that sometimes are disconnected, indicating that more relaxed models
of dynamics (e.g. [14, 15]) are worth studying.

All in all, the experiments in [6] showed that Incremental Counting behaves
well in a variety of pessimistic inputs, but not having a proof of what a
worst-case input looks like, and because the experiments were restricted to a
range of values of $n$ far from the expected massive size of an ADN, a
theoretical proof of polynomial time remained an open problem even from a
practical perspective.

A polynomial Counting algorithm was presented in a manuscript [2], relying on
the availability of an algorithm to compute the average of input values, one
at each node. Such average computation is modeled as a Markov chain with
underlying doubly-stochastic matrix, which requires topology information
within two hops (cf. [23]). In the pure model of ADN, such information is not
available, and gathering it may not be possible due to possible topology
changes from round to round.

Recently, we presented the first polynomial-time deterministic Counting
algorithm for ADNs in [16], called Methodical Counting. Unlike previous works,
Methodical Counting does not require any knowledge of network characteristics,
such as dynamic maximum degree or an upper bound on the size. That is, it
works in the pure model of ADN. Like previous works, Methodical Counting
requires the presence of a distinguished node. In the present work, we
generalize that assumption assuming the presence of $\ell\geq 1$ distinguished
nodes. As in [16], we leverage previous work on lazy random walks to analyze
MMC, but the alarms to detect wrong computations have been completely re-
designed to deal with multiple distinguished nodes. Moreover, with respect to
Methodical Counting, MMC achieves a $\Omega((\log^{2}n)/(n\ell))$ speed-up
(cf. Table 1). That is, even for $\ell=1$, MMC also provides a speed-up with
respect to previous work.

In the same paper [16], we also presented extensions of Methodical Counting to
compute more complex functions, such as the sum of input values held by nodes
and other algebraic and Boolean functions.

With respect to randomized Counting, a linear Counting algorithm for dynamic
networks was presented in [18]. The algorithm requires unique identifiers
(i.e., it is not applicable to ADNs), knowledge of an upper bound on the size
of the network, and only guarantees an approximation to the network size. To
the best of our knowledge, no randomized Counting algorithms for ADNs have
been studied before.

Other studies also dealing with the time complexity of information gathering
exist [8, 3, 24, 4, 22, 25], but include in their model additional
assumptions, such as the network having the same topology frequently enough or
node identifiers.

##  4 Impossibility of Counting

In this section, we show impossibility results for Counting in Anonymous
Dynamic Networks. After showing the existence of adversarial networks in a
technical lemma, we establish that deterministic Counting is not possible in
Anonymous Dynamic Networks without knowing the number of distinguished nodes.
For randomized algorithms, we show that for any $\ell\geq 0$, there exists an
ADN such that, if $\ell=0$ or $\ell$ is unknown to the nodes, there is no
randomized algorithm that with constant probability solves Counting. These
results complement the previously known impossibility for deterministic
algorithms without distinguished nodes [19]. Note that our impossibility
results hold even for static anonymous networks.

###  4.1 Deterministic Algorithms

###### Lemma 1

For every positive integer $\lambda$ there are two networks of $n=\lambda+4$
and $n=2(\lambda+4)$ nodes, respectively, such that: no deterministic
algorithm could successfully accomplish Counting on both of them in finite
time, even if some $\ell=\lambda$ nodes are black in the former and
$\ell=2\lambda$ nodes are black in the latter network.

Proof. We prove the claim showing two different networks of different size
such that any algorithm executed in these two networks cannot distinguish
between these two executions. Hence, it cannot obtain the correct count in
both.

Throughout the proof, solely for the purpose of definition of networks and
analysis of executions of the algorithms considered, we distinguish between
nodes; this obviously is not possible for the algorithms due to the definition
of the ADN communication model and the deterministic nature of the algorithms,
in the sense that when receiving messages and changing state a node does not
know from which specific nodes they have arrived.

Consider a positive integer $\lambda$ and the two associated networks
$G_{\lambda,1}$ and $G_{\lambda,2}$ defined as follows, c.f., Figure 1.

(a) $G_{\lambda,1}$

(b) $G_{\lambda,2}$

Figure 1: Illustration of Lemma 1.

$G_{\lambda,1}$ consists of $\lambda$ black nodes and $4$ white nodes,
connected in such a way that some two of the white nodes form a cycle of
length $3$ with each of the black nodes, and the remaining two white nodes
also form a cycle of length $3$ with each of the black nodes. It follows that
the graph is connected. Each black node has $4$ neighbors (namely, all white
nodes), and each white node has $\lambda+1$ neighbors (specifically, $\lambda$
black nodes and one white node).

$G_{\lambda,2}$ consists of $2\lambda$ black nodes and $8$ white nodes. The
black nodes are grouped into two groups of size $\lambda$ each, while the
white nodes are grouped into four pairs. Each black node in the first group is
connected with all first elements of the pairs of white nodes. Similarly, each
black node in the second group is connected with all second elements of the
pairs of white nodes. Additionally, for each pair of white nodes, both nodes
in the pair are also connected. It is easy to check that the graph is
connected, each black node has four neighbors (namely, either all white nodes
at first position in pairs or all white nodes at second position in pairs,
depending on the group it belongs to), and each white node has $\lambda+1$
neighbors (specifically, $\lambda$ black nodes, either from the first or the
second group depending on whether the node is first or second in its pair, and
one white node from the same pair).

In order to prove the lemma, consider executions of a deterministic Counting
algorithm on $G_{\lambda,1}$ and on $G_{\lambda,2}$. We prove that the
following invariant holds for each communication round $t$:

  * •

All black nodes in graphs $G_{\lambda,1}$ and $G_{\lambda,2}$ have the same
history (of received messages and input value) in the beginning of round $t$;

  * •

All white nodes in graphs $G_{\lambda,1}$ and $G_{\lambda,2}$ have the same
history (of received messages and input value) in the beginning of round $t$.

The proof is by induction. In the beginning of round one all black nodes in
both graphs know only that they are black, and similarly white nodes in both
graphs know only that they are not black. Hence the invariant holds.

Suppose the invariant holds for some $t\geq 1$, we show that it is also true
for $t+1$. Each black node in both graphs is a neighbor of four white nodes.
By the invariant for $t$, they had the same history at the beginning of round
$t$ and, since they follow a deterministic algorithm, they all either
broadcast exactly the same message or do not broadcast in round $t$. Hence, at
the end of round $t$ each black node gets the same messages (or no message,
respectively), and since by the invariant for $t$ they all had the same
history at the beginning of round $t$, their histories are also the same at
the end of round $t$, that is, also at the beginning of round $t+1$. Hence,
the first bullet of the invariant for $t+1$ holds.

Similarly, we argue about white nodes. Every white node in both graphs is a
neighbor of one white node and $\lambda$ black nodes. By the invariant for
$t$, all these black neighbors had the same history at the beginning of round
$t$, and the same applies to the white neighbors. Since they all follow a
deterministic algorithm, all black neighbors either broadcast exactly the same
message or do not broadcast in round $t$; similar property holds for white
neighbors. Hence, at the end of round $t$ each white node gets the same set of
messages (or no message, if both black and white nodes do not transmit in
round $t$), and since by the invariant for $t$ they all had the same history
at the beginning of round $t$, their histories are also the same at the end of
round $t$, which means, also at the beginning of round $t+1$. Hence the second
bullet of the invariant for $t+1$ holds as well.

To complete the proof, note that if nodes in both networks had accomplished
Counting at some round $t$, black nodes in $G_{\lambda,1}$ would return
$\lambda+4$ while black nodes in $G_{\lambda,2}$ would return $2(\lambda+4)$,
all based on the same history, which is impossible. More formally, consider
the first time $t$ in which some black node in any of these two networks
returns the correct number of nodes. By the invariant, all black nodes in both
networks have the same history, and since they follow the same deterministic
algorithm they all return the same value as the number of nodes. This however
is a contradiction, since black nodes in the first network should return a
different value. Hence, such time $t$ does not exist and no deterministic
algorithm accomplishes Counting in a finite time.

The following follows from the above lemma.

###### Theorem 2

If the number of black nodes is not given as a parameter, then there is no
deterministic Counting algorithm where all nodes stop and return the correct
count in all ADNs, not even with an approximation smaller than $\sqrt{2}$.

Proof. The impossibility of obtaining an exact count in all networks follows
from Lemma 1. Regarding the approximation, since the algorithm could not
distinguish between the two networks in Lemma 1 of sizes $\lambda+4$ and
$2(\lambda+4)$ respectively, for any $\lambda>0$, even if the algorithm
stopped and returned a consistent value (across all nodes) it would be within
at least $\sqrt{2}$ factor from some of these two sizes $\lambda+4$ and
$2(\lambda+4)$; since any of these two is feasible in the execution, the
approximation is at least $\sqrt{2}$, which occurs if the algorithm outputs a
count $x$ such that $x/(\lambda+4)=2(\lambda+4)/x$.

Remark: the inapproximability result could be extended from $\sqrt{2}$ to any
constant by considering networks with $c\cdot(\lambda+4)$ nodes, for an
arbitrary constant $c$ instead of $c=2$ used in the above proofs for the ease
of arguments.

###  4.2 Randomized Algorithms

###### Theorem 3

For any constant $0<c<1$ and any $\ell\geq 0$, there exists an Anonymous
Dynamic Network such that, if $\ell=0$ or $\ell$ is unknown to the nodes,
there is no Counting randomized algorithm such that, with probability $c$,
each node outputs the correct count when it stops.

Proof. For the sake of contradiction, assume such an algorithm exists, call it
${\mathcal{A}}$.

For an arbitrary number of black nodes $\ell\geq 0$, consider the following
network that we call a _gadget_ , depicted in Figure 2. If $\ell=0$, a gadget
is a simple path of $n$ white nodes connected by $n-1$ links, for arbitrary
$n>1$. If on the other hand it is $\ell>0$, a gadget is also a path of white
nodes, where each white node is linked to a separate black node (a
caterpillar). That is, the number of white nodes is also $\ell$ and the total
number of nodes in the gadget is $n=2\ell$.

(a) $\ell=0$

(b) $\ell>0$

Figure 2: Illustration of a gadget.

Let $G_{1,n,\ell}$ be a network formed by one gadget with an additional edge
connecting the (white) end nodes of the gadget as a cycle (see Figure 3 for
$\ell>0$). It follows that every node has the same number of neighbors of each
color. With probability at least $c$, all nodes running Algorithm
${\mathcal{A}}$ on $G_{1,n,\ell}$ must stop and output the correct count by
some time $T(n,\ell)$.

Figure 3: $G_{1,n,\ell}$ for $\ell>0$.

Without loss of generality, assume that in ${\mathcal{A}}$ each node draws one
random bit per round of communication. (If more random bits per round are
used, the same argument can be extended to more outcomes.)

Consider an execution of ${\mathcal{A}}$ on $G_{1,n,\ell}$ in the first
$T(n,\ell)$ rounds. Starting from the initial state where nodes have no
information besides their own color (recall that nodes do not have
identifiers), in each round a node makes decisions, based on the random bits
drawn and the received states of its neighbors to move to another state. With
respect to the random bits drawn, by time $t$ a node may be in one of $2^{t}$
states. We call the states of all network nodes at a given time a
_configuration_ of states. A configuration in $G_{1,n,\ell}$ where
${\mathcal{A}}$ stops at all nodes with an exact count of $n$ is called a
_winning configuration_. By definition of ${\mathcal{A}}$, the probability of
ending at a winning configuration is at least $c$, and there are
$2^{T(n,\ell)n}$ possible configurations. Hence, there must exist some winning
configuration $\Gamma$ that occurs in ${\mathcal{A}}$ with probability at
least $c/2^{nT(n)}$. Denote by $\Gamma_{\to t}$ the part of configuration
$\Gamma$ by round $t$.

Consider an execution of ${\mathcal{A}}$ on a network $G_{x,n,\ell}$, where
$x$ will be defined later, formed by $x$ gadgets connected in sequence by the
(white) end points so that white nodes form a cycle (see Figure 4).

Figure 4: $G_{x,n,\ell}$ for $\ell>0$.

Let a path of $2\lceil T(n,\ell)/(n-\ell)\rceil+1$ gadgets in $G_{x,n,\ell}$
be called a _witness_ , where the gadget in the center of a witness is called
the _core_ , and the $\lceil T(n,\ell)/(n-\ell)\rceil$ gadgets in each side of
the core are called a _buffer_ (see Figure 5).

Figure 5: A witness in $G_{x,n,\ell}$ for $\ell>0$.

We show now that, for $x$ large enough, after executing ${\mathcal{A}}$ on
$G_{x,n,\ell}$ for $T(n,\ell)$ rounds, the core of some witness has the
configuration $\Gamma$, hence nodes in that core stop with an incorrect count
of $n$ with probability larger than $1-c$, which proves the theorem.

Let $x$ be such that witnesses are separated by $2\lceil
T(n,\ell)/(n-\ell)\rceil$ gadgets. That is, they are disjoint and between any
pair of consecutive witnesses there are $2\lceil T(n,\ell)/(n-\ell)\rceil$
gadgets that do not belong to any considered witness. Therefore, during the
first $T(n,\ell)$ rounds of the execution of ${\mathcal{A}}$ on
$G_{x,n,\ell}$, the configurations on witnesses are independent.

Consider a single witness in $G_{x,n,\ell}$. Let any connected pair of white
and black nodes be called a _pair_. Define a $t$-semi-core of the witness, for
$0\leq t\leq\lceil T(n,\ell)/(n-\ell)\rceil(n-\ell)$, as a set containing the
pairs in the core and all the pairs in the buffer, such that their white nodes
are located at distance at most $T(n,\ell)-t$ from the core. In particular,
the $0$-semi-core is the whole witness, and the $\lceil
T(n,\ell)/(n-\ell)\rceil(n-\ell)$-semi-core is the core (see Figure 6).

Figure 6: Semi-cores in a witness in $G_{x,n,\ell}$, for $\ell>0$. $t$ is such
that $0\leq t\leq\mathcal{T}$ and $\mathcal{T}=\lceil
T(n,\ell)/(n-\ell)\rceil(n-\ell)$.

Using the above notation, we prove the following invariant (illustrated in
Figure 7).

  * _For any $0\leq t\leq\lceil T(n,\ell)/(n-\ell)\rceil(n-\ell)$, with probability at least $c/2^{nt}$, any pair $(v,v^{\prime})$ in the $t$-semi-core located at distance $x\leq\lceil T(n,\ell)/(n-\ell)\rceil(n-\ell)-t$ from the core, has the same configuration in $\Gamma_{\to t}$ as the pair $(w,w^{\prime})$ in the core at distance $x\bmod(n-\ell)$ from the other buffer._

Figure 7: Invariant in a witness in $G_{x,n,\ell}$, for $\ell>0$. $0\leq
t\leq\mathcal{T}$, $0\leq x\leq\mathcal{T}-t$, and $\mathcal{T}=\lceil
T(n,\ell)/(n-\ell)\rceil(n-\ell)$.

We prove the invariant by induction as follows. When the execution of
${\mathcal{A}}$ starts, all pairs in the $0$-semi-core are in the same state.
Then, assuming inductively that the invariant holds for some round $0\leq
t<\lceil T(n,\ell)/(n-\ell)\rceil(n-\ell)$, we can extend the configuration of
the $t$-semi-core at all but the end pairs of this semi-core to satisfy the
invariant for $t+1$. This is because all these pairs receive messages from
other nodes satisfying the invariant for $t$. Thus, cyclically modulo
$(n-\ell)$ from a core boundary, nodes mimick the behavior of ${\mathcal{A}}$
on $G_{1,n,\ell}$ at round $t+1$ of the protocol, which leads to the partial
configuration $\Gamma_{\to t+1}$ on $G_{1,n,\ell}$, and thus on the
corresponding nodes of the $(t+1)$-semi-core, cyclically modulo $(n-\ell)$
from a core boundary.

It follows from the invariant for $T(n,\ell)$ that the $n$ nodes in the core
end up in configuration $\Gamma$. Since $\Gamma$ is a winning configuration on
$n$ nodes, all nodes in the core stop and output a count of $n$, which
violates the correctness during the considered execution of ${\mathcal{A}}$ on
$G_{x,n,\ell}$.

It remains to prove that the union of the above events, over all the
considered $x/(4\lceil T(n,\ell)/(n-\ell)\rceil+1)$ witnesses, holds with
probability larger than $1-c$. For $y=x/(4\lceil T(n,\ell)/(n-\ell)\rceil+1)$,
we show that the complementary event holds with probability smaller than $c$,
that is, $\left(1-\left(c/2^{nT(n,\ell)}\right)^{2}\right)^{y}<c$. This is
indeed implied by $\exp\left(-c^{2}y/2^{2nT(n,\ell)}\right)<c$, which holds
for $y>\ln(1/c)2^{2nT(n,\ell)}/c^{2}$. That is, for
$x=\left(1+\ln(1/c)2^{2nT(n,\ell)}/c^{2}\right)(4\lceil
T(n,\ell)/(n-\ell)\rceil+1)$, with probability larger than $1-c$, there exists
at least one witness in $G_{x,n,\ell}$ with a winning configuration $\Gamma$
after running ${\mathcal{A}}$ for $T(n,\ell)$ rounds. Hence, the core nodes
stop and output an incorrect count, and the claim follows.

Since there is no deterministic algorithm that solves Counting if the number
of black nodes is unknown, and Counting cannot be solved even with a constant
probability by randomized algorithms if the number of black nodes is unknown
or there is no black node, we pursue two directions. One is to design a
polynomial-time deterministic algorithm for exact Counting if the exact number
of black nodes is a priori known. The other, for randomized algorithms, is to
focus on Unconscious Counting [11] as defined in Section 2.

##  5 Deterministic Counting

In this section we present and analyze our deterministic Counting algorithm
MMC.

The underlying idea of the algorithm is to search for the number of nodes
testing different estimates until the correct value is found. Starting with an
initial value, the estimate is doubled after each failed attempt. If at some
point the estimate goes above $n$, the correct estimate is found by binary
search in the range between the previous and the current estimate. To organize
this exploration, we structure the execution of the algorithm in _epochs_. In
each epoch, a new estimate is tested. Once the correct estimate is found, the
execution stops.

In each epoch, to detect whether the estimate is low, correct, or high, we use
some alarms, most of them based on the value of some _potentials_ held at
nodes. To implement these alarms we use a gossip-based approach to collect at
the black nodes the potentials, which are initially held only by the white
nodes. The way that potentials change, and their convergence values, depend on
the correctness of the estimate.

For the above potential-collection process we could have the black nodes
collecting continuously until done, but to facilitate our analysis techniques
we need all nodes participating in the gossiping process. Thus, rather than
collecting all the potential at once, we further structure each epoch in
_phases_ such that, during each phase, all nodes average the current
potentials, and only at the end of the phase black nodes remove their current
potential to a separate accumulator. The number of rounds of communication in
each phase are enough to reach such average or detect a wrong estimate.

In the following paragraphs, we give further details referring to the
pseudocode in Algorithms 1 and 2.

$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

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

5 if  _$status=probing$ and $|N|\leq d-1$ and $\forall i\in
N:status_{i}=probing$_ then

$\Phi\leftarrow\Phi+\sum_{i\in N}\Phi_{i}/d-|N|\Phi/d$

// update potential

6

7 else // $k<n$

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

9

10

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

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

$\rho\leftarrow\rho+\Phi$

// consume potential

13 $\Phi\leftarrow 0$

14

15

16 if  _$status=probing$_ then

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

18 $status\leftarrow done$

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

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

21 // $k<n$

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

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

24

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

26 $min\leftarrow k+1$

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

28

29 else

30 if  _$status=high$_ then

31 $max\leftarrow k-1$

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

33

34

35

36until  _$status=done$_

37return $k$

38

Algorithm 1 MMC algorithm for each _black node_. $N$ is the set of neighbors
of this node in the current round. $\ell$ is the number of black nodes. The
parameters $d,p,r$ and $\tau$ are as defined in Theorem 11.

$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

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

5 if  _$status=probing$ and $|N|\leq d-1$ and $\forall i\in
N:status_{i}=probing$_ then

$\Phi\leftarrow\Phi+\sum_{i\in N}\Phi_{i}/d-|N|\Phi/d$

// update potential

6

7 else // $k<n$

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

9

10

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

12 // $k<n$

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

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

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

16

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

18 $min\leftarrow k+1$

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

20

21 else

22 if  _$status=high$_ then

23 $max\leftarrow k-1$

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

25

26

27

28until  _$status=done$_

29return $k$

30

Algorithm 2 MMC algorithm for each _white node_. $N$ is the set of neighbors
of this node in the current round. $\ell$ is the number of black nodes. The
parameters $d,p,r$ and $\tau$ are as defined in Theorem 11.

Initially, each of the $\ell$ black nodes is assigned a potential of $0$ and
each of the $n-\ell$ white nodes is assigned a potential of $\ell$. Epoch $k$
corresponds to a size estimate $k$ that is iteratively updated from epoch to
epoch until the correct value $n$ is found. Each epoch is divided into $p$
phases, and each phase is composed by $r$ rounds of communication.

In each round, each node broadcasts its potential and receives the potential
of all its neighbors. Each node keeps only a fraction $1/d$ of the potentials
received. The parameters $p$, $r$, and $d$ are functions of $k$. The specific
functions needed to guarantee correctness and saught efficiency are defined in
Theorem 11. For the sake of presentation we simply write $p$, $r$, and $d$
instead of $p(k)$, $r(k)$, and $d(k)$. This varying way of distributing
potential is different from previous approaches using mass distribution. After
communication, each node updates its own potential accordingly (cf. Lines 1.1
and 2.2). That is, it adds a fraction $1/d$ of the potentials received, and
subtracts a fraction $1/d$ of the potential broadcasted times the number of
potentials received. Then, a new round starts. At the end of each phase, each
black node “consumes” its potential. That is, it increases an internal
accumulator $\rho$ by its current potential $\Phi$, and $\Phi$ is zeroed for
starting the next phase (cf. Lines 1.1 and 1.1).

The correctness (or incorrectness) of the estimate is detected by various
alarms as follows. A node stops the update of potential described, raises its
potential to $\ell$, and broadcasts an alarm status “low” in each round until
the end of the epoch if any of the following happens: 1) at the end of the
first phase its potential is above some threshold $\tau$ as defined in Theorem
11 (cf. Lines 1.1 and 2.2), 2) at any round it receives more than $d-1$
messages (cf. Lines 1.1 and 2.2), or 3) at any round receives an alarm status
“low” from one of its neighbors (cf. Lines 1.1 and 2.2). Case 1) allows the
black nodes to detect that the estimate is wrong when $k^{1+\epsilon}<n$ for
some $\epsilon>0$ (Lemmas 7 and 9), case 2) allows the black nodes to detect
that $d$ is too small and hence the estimate is low, and case 3) allows
dissemination of these alarms. (In “low” status the potential is set to $\ell$
to facilitate the analysis, but it is not strictly needed by the algorithm.)

At the end of each epoch, each black node checks the value of $\rho$ and
updates its status accordingly. If it is within some range, call it $\Gamma$,
the current estimate is correct and each black node changes its status to
“done” (cf. Line 1.1). Otherwise, the estimate is incorrect. If $\rho$ is
below (resp. above) $\Gamma$ each black node changes its status to “high”
(resp. “low”) indicating that the estimate is too big (resp. “low”) (cf. Lines
1.1 and 1.1 respectively). The case when $\rho$ is below (resp. above)
$\Gamma$ allows to detect when $k>n$ (resp. $k<n\leq k^{1+\epsilon}$) (c.f.
Lemmas 6 and 10 respectively.).

After black nodes update their status, the network is flooded with it for
$d>k$ rounds (cf. Lines 1.1 and 2.2). If $k\geq n$, those rounds are enough
for all white nodes to receive the “done” or “high” status. If they receive
“done”, after completing the $k$ rounds all nodes stop. Otherwise, after
completing the $k$ rounds all nodes update $k$ according to status to start a
new epoch (cf. Lines 1.1 and 2.2). If $k$ has not been detected to be greater
than $n$ since the computation started, it is doubled for the next epoch,
otherwise it is updated as in binary search. Notice that at the beginning of
each epoch the nodes’ status are set to “probing”. Hence, if $k<n$, white
nodes may or may not detect that the estimate is low, but if they do not
detect it they will move to the next epoch increasing $k$.

###  5.1 Analysis of MMC

In this section we analyze MMC. References to algorithm lines are given as
$\langle algorithm\\#\rangle.\langle line\\#\rangle$. We use standard
notations $\vec{I}$ for the unit vector, and $L_{p}$ for the norm of vector
$\vec{x}=(x_{1},x_{2},\dots,x_{n})$ as
$||\vec{x}||_{p}=\left(\sum_{i=1}^{n}|x_{i}|^{p}\right)^{1/p}$, for any $p\geq
1$. Only for the analysis, nodes are labeled as $0,1,2,\dots,n-1$. The
potential of a node $i$ at the beginning of round $s$ of phase $t$ is denoted
as $\Phi_{s,t}[i]$, the potential of all nodes is denoted as a vector
$\vec{\Phi}_{s,t}$, and the aggregated potential is then
$||\vec{\Phi}_{s,t}||_{1}$. The subindices $s$, $t$, or both are omitted
sometimes for clarity. We will refer to the potential right after the last
round of a phase as $\vec{\Phi}_{r+1}$. Such round does not exist in the
algorithm, but we use this notation to distinguish between the potential right
before black nodes consume their own potential (cf. Line 1.1) and the
potential at the beginning of the first round of the next phase.

First, we provide a broad description of our analysis of MMC. Consider the
vector of potentials $\vec{\Phi}_{i}$ held by nodes at the beginning of any
given phase $i$. Let a $d$-lazy random walk be a walk that picks each adjacent
edge with probability $1/d$, and with the remaining probability it stays at
the current vertex. The way that potentials are updated in each round (cf.
Lines 1.1 and 2.2) is equivalent to the progression of a $d$-lazy random walk
on the evolving graph underlying the network topology [1], where the initial
vector of potentials is equivalent to an initial distribution $\vec{\Pi}_{i}$
on the overall potential $||\vec{\Phi}_{i}||_{1}$ and the probability of
choosing a specific neighbor is $1/d$.

Note that MMC is not a simple “derandomization” of the lazy random walk on
evolving graphs. First, in the Anonymous Dynamic Network model neighbors
cannot be distinguished, and even their number is unknown at transmission time
(only at receiving time the node learns the number of its neighbors). Second,
due to unknown network parameters, it may happen in an execution of MMC that
the total potential received could be bigger than $1$. Third, our algorithm
does not know a priori when to terminate and provide a result even with some
reasonable accuracy, as the formulas on mixing and cover time of lazy random
walks depend on the (a priori unknown) number of nodes $n$. Nevertheless, we
can still use some results obtained in the context of analogous lazy random
walks in order to prove useful properties of parts of MMC, namely, some parts
in which parameters are temporarily fixed and the number of received messages
does not exceed parameter $d$.

It was shown in [1] that random walks on $d$-regular explorable evolving
graphs have a uniform stationary distribution, and bounds on the mixing and
cover time were proved as well. Moreover, it was observed that those
properties hold even if the graph is not regular and $d$ is only an upper
bound on the degree.666Their analysis relies on Lemma 12, which bounds the
eigenvalues of the transition matrix as long as it is stochastic, connected,
symmetric, and non-zero entries lower bounded by $1/d$. Those conditions hold
for all the transition matrices, even if the evolving graph is not regular.

Thus, for the cases where $d$ is an upper bound on the number of neighboring
nodes, we analyze the evolution of potentials within each phase leveraging
previous work on random walks on evolving graphs. Specifically, we use the
following result which is an extension of Corollary 14 in [1].

###### Theorem 4

(Corollary 14 in [1].) After $t$ rounds of a $d_{\max}$-lazy random walk on an
evolving graph with $n$ nodes, dynamic diameter $D$, upper bound on maximum
degree $d_{\max}$, and initial distribution $\vec{\Pi}_{0}$, the following
holds.

$\displaystyle\left|\left|\vec{\Pi}_{t}-\frac{\vec{I}}{n}\right|\right|_{2}^{2}\leq\left(1-\frac{1}{d_{\max}Dn}\right)^{t}\left|\left|\vec{\Pi}_{0}-\frac{\vec{I}}{n}\right|\right|_{2}^{2}$

In between phases, black nodes “consume” their potential, effectively changing
the distribution at that point. Then, a new phase starts.

In MMC, given that $d$ is a function of the estimate $k$, if the estimate is
low, there may be inputs for which $d$ is not an upper bound on the number of
neighbors. We show in our analysis that in those cases the black nodes detect
the error and after some time all nodes increase the estimate.

#### Structure of the proof

The proof of correctness is structured in the following cases, depending on
the relation between the size estimate $k$ and $n$. For some $\gamma$ and
$\epsilon$, after completing an epoch with size estimate $k$, we prove that
$\rho$, the potential accumulated by a black node, must be within the
following ranges.

$k=n$ | $\Rightarrow$ | $(k-\ell)\left(1-\frac{1}{k^{\gamma}}\right)\leq\rho\leq(k-\ell)\left(1+\frac{1}{k^{\gamma}}\right)$ | (Lemma 5)
---|---|---|---
$k>n$ | $\Rightarrow$ | $\rho<(k-\ell)\left(1-\frac{1}{k^{\gamma}}\right)$ | (Lemma 10)
$k<n\leq k^{1+\epsilon}$ | $\Rightarrow$ | $\rho>(k-\ell)\left(1+\frac{1}{k^{\gamma}}\right)$ | (Lemma 6)

For the remaining case when $k^{1+\epsilon}<n$, we prove first the following
relation between $\Phi_{r+1,1}$, the potential of any node at the end of the
first phase, and a threshold $\tau$.

$k^{1+\epsilon}<n$ | $\Rightarrow$ |  $\Phi_{r+1,1}>\tau$ for at least one node | (Lemma 7)
---|---|---|---
$k\geq n$ | $\Rightarrow$ |  $\Phi_{r+1,1}\leq\tau$ for all nodes | (Lemma 8)

Thus, if $k^{1+\epsilon}<n$, and only if $k<n$, there is at least one node
with potential above $\tau$, which moves to a status “low” and spreads this
alarm. We complete the proof with the following.

$k^{1+\epsilon}<n$ | $\Rightarrow$ | all nodes receive an alarm “low” during phase $2$ | (Lemma 9)
---|---|---|---

#### Analysis.

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

###### Lemma 5

If $d\geq k=n$, for an ADN with $\ell<k$ black nodes, for any $\gamma>0$ there
is a $\alpha\geq\max\\{2,1+\gamma+\log_{k}3\\}$ such that, after running the
MMC protocol for $p\geq(2\gamma\ln
k)/\left(\ell\left(\frac{1}{k}+\frac{1}{k^{\alpha}}\right)\right)$ phases,
each of $r\geq 2\alpha dk^{2}\ln k$ rounds, the potential $\rho$ consumed by
each of the $\ell$ black 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. Consider the vector of potentials $\vec{\Phi}_{i,1}$ at the beginning
of round $1$ of any phase $i$. We analyze the evolution of potentials within
phase $i$ as a random walk on the evolving graph underlying the network
topology. Consider the initial distribution $\vec{\Pi}_{1}$ on the overall
potential $||\vec{\Phi}_{i,1}||_{1}$. Given that $d\geq k$, for any
$\alpha\geq 0$ and using Theorem 4, we know that after a phase $i$ of $r\geq
2\alpha dk^{2}\ln k$ rounds the distribution is such that

$\displaystyle\left|\left|\vec{\Pi}_{r+1}-\frac{\vec{I}}{k}\right|\right|_{2}^{2}$
$\displaystyle\leq\left(1-\frac{1}{d{\cal
D}k}\right)^{r}\left|\left|\vec{\Pi}_{1}-\frac{\vec{I}}{k}\right|\right|_{2}^{2},\textrm{
for $d{\cal D}k>1$, it is }$ (1) $\displaystyle\leq\exp\left(-\frac{r}{d{\cal
D}k}\right)$ $\displaystyle\leq\exp\left(-\frac{2\alpha dk^{2}\ln k}{d{\cal
D}k}\right),\textrm{ given that $k=n>{\cal D}$, it is }$
$\displaystyle\leq\exp\left(-2\alpha\ln k\right)$
$\displaystyle=\frac{1}{k^{2\alpha}}\ .$

Given that
$(\Pi_{r+1}[j]-1/k)^{2}\leq\left|\left|\vec{\Pi}_{r+1}-\frac{\vec{I}}{k}\right|\right|_{2}^{2}$,
for any node $j$, we have that $(\Pi_{r+1}[j]-1/k)^{2}\leq 1/k^{2\alpha}$ and
hence

$\displaystyle\left|\Pi_{r+1}[j]-\frac{1}{k}\right|\leq\frac{1}{k^{\alpha}}\
.$ (2)

Notice that the latter is true for any initial distribution. Therefore, after
each phase a black 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 $||\vec{\Phi}_{1,1}||_{1}=\ell(k-\ell)$.

Using the latter observations, we first find conditions on $p$ to obtain the
desired bounds on $\rho$, as follows. After $p$ phases a black 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},$
(3)

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}.$
(4)

Given that $0<\ell\left(\frac{1}{k}+\frac{1}{k^{\alpha}}\right)<1$ for
$\alpha\geq 2$ and $k>\ell$, Equation 3 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)}$
$\displaystyle=(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$ (5) $\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 4:

$\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)}$
$\displaystyle=(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 find a value of $c$
such that

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

This is the same as Equation 5 and hence the claim follows.

The previous lemma shows that, after running MMC enough time, if for some
black 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 MMC long enough. To
ensure that $d\geq\Delta+1$, we restrict $d\geq k^{1+\epsilon}$.

###### Lemma 6

Under the following conditions $1<k<n\leq k^{1+\epsilon}\leq d$, $\epsilon>0$,
after running the MMC protocol for $p\geq 2\delta(\ln
k)/(\ell\left(1/n+1/k^{\beta}\right))$ phases, each of $r\geq 2\beta
dk^{2+2\epsilon}\ln k$ rounds, under the following conditions
$\beta\geq\log_{k}(n(2k^{\delta}+1))$, $\beta>2$,
$\delta>\log_{k}(nk^{\gamma}/(nk^{\gamma}-(n-1)(k^{\gamma}+1)))$, and
$\gamma>\log_{k}(n-1)$. Then, the potential $\rho$ consumed by any black node
is $\rho>(k-\ell)\left(1+1/k^{\gamma}\right)$.

Proof. Given that $d\geq n$, we can use Theorem 4 as in Lemma 5 to show that
after a phase of $r\geq 2\beta dk^{2+2\epsilon}\ln k$ rounds the distribution
is such that

$\displaystyle\left|\left|\vec{\Pi}_{r+1}-\frac{\vec{I}}{n}\right|\right|_{2}^{2}$
$\displaystyle\leq\left(1-\frac{1}{d{\cal
D}n}\right)^{r}\left|\left|\vec{\Pi}_{1}-\frac{\vec{I}}{n}\right|\right|_{2}^{2}$
$\displaystyle\leq\exp\left(-\frac{r}{d{\cal D}n}\right)$
$\displaystyle\leq\exp\left(-\frac{2\beta dk^{2+2\epsilon}\ln k}{d{\cal
D}n}\right).$

Given that $k^{1+\epsilon}\geq n>{\cal D}$, we have that

$\displaystyle\left|\left|\vec{\Pi}_{r+1}-\frac{\vec{I}}{n}\right|\right|_{2}^{2}$
$\displaystyle\leq\exp\left(-2\beta\ln k\right)$
$\displaystyle=\frac{1}{k^{2\beta}}\ .$

For any node $i$, given that
$(\Pi_{r+1}[i]-1/n)^{2}\leq\left|\left|\vec{\Pi}_{r+1}-\frac{\vec{I}}{n}\right|\right|_{2}^{2}$
we have that $(\Pi_{r+1}[i]-1/n)^{2}\leq 1/k^{2\beta}$ and hence
$\Pi_{r+1}[i]\geq 1/n-1/k^{\beta}$. The latter is true for any initial
distribution. Therefore, after each phase a black 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
$||\vec{\Phi}_{1,1}||_{1}=\ell(n-\ell)$.

Using the latter observations, after $p$ phases, any given black 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)}$
$\displaystyle=(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$
(cf. [21]), we have that

$\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)$
$\displaystyle\geq(n-\ell)\frac{k^{\beta}-n}{k^{\beta}+n}\left(1+\frac{1}{k^{\delta}}\right)\left(1-\frac{1}{k^{\delta}}\right)$
$\displaystyle\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$. First, we prove the following two
claims that establish properties of the potential during the execution of MMC.
(Recall that we use round $r+1$ to refer to potentials at the end of the phase
right before black nodes consume their potential in Line 1.1.)

###### Claim 1

Given an ADN of $n$ nodes running MMC with parameter $d$, for any round $t$ of
the first phase, such that $1\leq t\leq r+1$, if $d$ was larger than the
number of neighbors of each node $x$ for every round $t^{\prime}<t$, then
$||\vec{\Phi}_{t}||_{1}=(n-\ell)\ell$.

Proof. For the first round the claim holds as the initial potential of each
node is $\ell$ except the black nodes that get $0$. That is,
$||\vec{\Phi}_{1}||_{1}=(n-\ell)\ell$. For any given round $1<t\leq r+1$ in
phase $1$ and any given node $x$, if $d$ is larger than the number of
neighbors of $x$, the potential is updated only in Lines 1.1 and 2.2 as

$\displaystyle\Phi_{t+1}[x]$ $\displaystyle=\Phi_{t}[x]+\sum_{i\in
N_{t}[x]}\Phi_{t}[i]/d-|N_{t}[x]|\Phi_{t}[x]/d\ .$

Where $N_{t}[x]$ is the set of neighbors of node $x$ in round $t$.
Inductively, assume that the claim holds for some round $1\leq t\leq r$. We
want to show that consequently it holds for $t+1$. The potential for round
$t+1$ is

$\displaystyle||\vec{\Phi}_{t+1}||_{1}$
$\displaystyle=||\vec{\Phi}_{t}||_{1}+\frac{1}{d}\sum_{x\in V}\left(\sum_{y\in
N_{t}[x]}\Phi_{t}[y]-|N_{t}[x]|\Phi_{t}[x]\right)\ .$ (6)

In the ADN model, communication is symmetric. That is, for every pair of nodes
$x,y\in V$ and round $t$, it is $x\in N_{t}[y]\iff y\in N_{t}[x]$. Fix a pair
of nodes $x^{\prime},y^{\prime}\in V$ such that in round $t$ it is
$y^{\prime}\in N_{t}[x^{\prime}]$ and hence $x^{\prime}\in N_{t}[y^{\prime}]$.
Consider the summations in Equation 6. Due to symmetric communication, we have
that the potential $\Phi_{t}[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}$. This
observation applies to all pairs of nodes that communicate in any round $t$.
Therefore, we can re-write Equation 6 as

$\displaystyle||\vec{\Phi}_{t+1}||_{1}$
$\displaystyle=||\vec{\Phi}_{t}||_{1}+\frac{1}{d}\sum_{\begin{subarray}{c}x,y\in
V:\\\ y\in N_{t}[x]\\\
\end{subarray}}\bigg{(}\Phi_{t}[y]-\Phi_{t}[x]+\Phi_{t}[x]-\Phi_{t}[y]\bigg{)}$
$\displaystyle=||\vec{\Phi}_{t}||_{1}\ .$

Thus, the claim follows.

###### Claim 2

Given an ADN of $n$ nodes running MMC, for any round $t$ of any phase and any
node $x$, it is $0\leq\Phi_{t}[x]\leq\ell$.

Proof. If $t=1$ the potential of the black nodes is $\Phi_{1}[0]=0$ and the
potential of any white node $x$ is $\Phi_{1}[x]=\ell$. Thus, the claim
follows. Inductively, for any round $2<t\leq r+1$, we consider two cases
according to node status. If a node $x$ is in alarm status “low” at the
beginning of round $t$, then it is $\Phi_{t}[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 (cf. Figures 1 and 2).

In the second case, if a node $x$ is in “probing” status at the beginning of
round $t$, it means that it had its potential updated in all rounds
$t^{\prime}<t$ only in Lines 1.1 or 2.2 as

$\displaystyle\Phi_{t^{\prime}+1}[x]$
$\displaystyle=\Phi_{t^{\prime}}[x]+\sum_{y\in
N_{t^{\prime}}[x]}\Phi_{t^{\prime}}[y]/d-|N_{t^{\prime}}[x]|\Phi_{t^{\prime}}[x]/d\
.$

For all rounds $t^{\prime}<t$, node $x$ exchanged potential with less than $d$
neighbors, because otherwise it would have been changed to alarm status “low”
in Lines 1.1 or 2.2. Therefore it is
$|N_{t^{\prime}}[x]|\Phi_{t^{\prime}}[x]/d<\Phi_{t^{\prime}}[x]$ which implies
$\Phi_{t}[x]\geq 0$. On the other hand, it can also be seen that
$\Phi_{t}[x]\leq\ell$ because, for any $t^{\prime}<t$, it is

$\displaystyle\Phi_{t^{\prime}+1}[x]$
$\displaystyle=\Phi_{t^{\prime}}[x]+\sum_{y\in
N_{t^{\prime}}[x]}\Phi_{t^{\prime}}[y]/d-|N_{t^{\prime}}[x]|\Phi_{t^{\prime}}[x]/d\
.$

In particular for $t^{\prime}=t-1$, we know by inductive hypothesis that
$\Phi_{t-1}[v]\leq\ell$ for any $v\in V$. Replacing, in the latter equation we
get that $\Phi_{t}[x]\leq\ell$.

To show that if $k^{1+\epsilon}<n$ MMC detects that the estimate is low, we
focus on the first phase. We define a threshold $\tau$ and a number of rounds
such that, after the first phase is completed, some nodes will have potential
above $\tau$ and this can happen only if the estimate is low. Then we show
that black nodes receive an alarm indicating that.

First, we show an upper bound of at most $k^{1+\epsilon}$ nodes with potential
at most $\tau$ at the end of the first phase (Lemma 7). Thus, given that
$k^{1+\epsilon}<n$, 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 8). 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 9).

###### Lemma 7

For $\epsilon>0$, after running the first phase of the MMC protocol, 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 $t$ as
$s_{t}[x]=\ell-\Phi_{t}[x]$ and the vector of slacks at the beginning of round
$t$ as $\vec{s}_{t}$. 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 $1$ of phase $1$ is $||\vec{\Phi}_{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 with respect to the
maximum potential that could be held by all the $n$ nodes at the beginning of
round $1$ is $||\vec{s}_{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
black nodes consume their own potential in Line 1.1. That is,
$\Phi_{r+1}[x]\leq\tau$ for all $x\in L$ (and $\Phi_{r+1}[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_{r+1}[x]\leq||\vec{s}_{1}||_{1}=\ell^{2}$. By definition of
$L$, we have that for each node $x\in L$ it is
$s_{r+1}[x]=(\ell-\Phi_{r+1}[x])\geq\ell-\tau$. Therefore,
$|L|(\ell-\tau)\leq\sum_{x\in L}s_{r+1}[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_{r+1}[x]\leq\ell^{2}$. Let the scenario where $d$ 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 $||\vec{\Phi}_{r+1}||_{1}=\ell(n-\ell)$.
Therefore, the slack held by all nodes is $||\vec{s}_{r+1}||_{1}=\ell^{2}$ and
the slack held by nodes in $L\subseteq V$ is $\sum_{x\in
L}s_{r+1}[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$ neighbors or more in one or more rounds, the slack
is even smaller. To compare both scenarios we denote the slack for each round
$t$, each node $x$, and each case $i$ as $s^{(i)}_{t}[x]$.

Assume that some node $x$ is the first one to have $d^{\prime}>d-1$ neighbors.
Let $1\leq t\leq r$ be the round of the first phase when this event happened.
We claim that $||\vec{s}_{t+1}^{(2)}||_{1}\leq||\vec{s}_{t+1}^{(1)}||_{1}$.
The reason is the following. Given that more than $d-1$ potentials are
received, node $x$ increases its potential to $\ell$ for the rest of the epoch
(cf. Lines 1.1 and 2.2). That is, the slack of $x$ is $s_{t+1}^{(2)}[x]\leq
s_{t}^{(2)}[x]=s_{t}^{(1)}[x]$. Additionally, the potential shared by $x$ with
all neighbors during round $t$ is $d^{\prime}\Phi_{t}[x]/d>\Phi_{t}[x](1-1/d)$
(cf. Lines 1.1 and 2.2). That is, the potential shared by $x$ with neighbors
in case 2 is more than the potential that $x$ would have shared in case 1.
Then, combining both effects (the relative increase in potential of $x$ and
its neighbors’) the overall slack is
$||\vec{s}_{t+1}^{(2)}||_{1}\leq||\vec{s}_{t+1}^{(1)}||_{1}$. The same
argument applies to all other nodes with $d$ or more neighbors in round $t$.

Additionally, for any round $t^{\prime}$ of the first phase, such that
$t<t^{\prime}\leq r$, we have to also consider the case of a node $y$ that,
although it does not receive more than $d-1$ potentials, it moves to alarm
status “low” because it has received such status in round $t^{\prime}$. Then,
notice that the potential of $y$ is
$\Phi_{t^{\prime}+1}[y]=\ell\geq\Phi_{t^{\prime}}[y]$, and it will stay in
$\ell$ for the rest of the epoch (cf. Lines 1.1 and 2.2). Therefore, the slack
of $y$ is $s_{t+1}^{(2)}[y]\leq s_{t+1}^{(1)}[y]$.

Combining all the effects studied over all rounds, the slack at the end of the
first phase is $||\vec{s}_{r+1}^{(2)}||_{1}\leq||\vec{s}_{r+1}^{(1)}||_{1}$.
Given that $L\subseteq V$, it is $\sum_{x\in
L}s_{r+1}^{(2)}[x]\leq||\vec{s}_{r+1}^{(2)}||_{1}\leq||\vec{s}_{r+1}^{(1)}||_{1}\leq\ell^{2}$
which completes the proof.

###### Lemma 8

If $k\geq n$, $r\geq(4+2\epsilon-2\ln(k^{\epsilon}-1)/\ln k)dk^{2}\ln k$, and
$\epsilon>0$, given that $k>\ell\geq 1$, at the end of the first phase no
individual node should have potential larger than
$\tau=\ell(1-\ell/k^{1+\epsilon})$.

Proof. Using Theorem 4, we know that after phase $1$ of
$r\geq(4+2\epsilon-2\ln(k^{\epsilon}-1)/\ln k)dk^{2}\ln k$ rounds, the
distribution is such that

$\displaystyle\left|\left|\vec{\Pi}_{r+1}-\frac{\vec{I}}{n}\right|\right|_{2}^{2}$
$\displaystyle\leq\left(1-\frac{1}{d{\cal
D}n}\right)^{r}\left|\left|\vec{\Pi}_{1}-\frac{\vec{I}}{n}\right|\right|_{2}^{2}$
$\displaystyle\leq\exp\left(-\frac{r}{d{\cal D}n}\right)$
$\displaystyle\leq\exp\left(-\frac{(4+2\epsilon-2\ln(k^{\epsilon}-1)/\ln
k)dk^{2}\ln k}{d{\cal D}n}\right).$

Given that $k\geq n>{\cal D}$, we have that

$\displaystyle\left|\left|\vec{\Pi}_{r+1}-\frac{\vec{I}}{k}\right|\right|_{2}^{2}$
$\displaystyle\leq\exp\left(-(4+2\epsilon-2\ln(k^{\epsilon}-1)/\ln k)\ln
k\right)$ $\displaystyle=1/k^{4+2\epsilon-2\ln(k^{\epsilon}-1)/\ln k}\ .$

Given that for any node $j$, it is
$(\Phi_{r+1}[j]-1/k)^{2}\leq\left|\left|\vec{\Phi}_{r+1}-\frac{\vec{I}}{k}\right|\right|_{2}^{2}$,
we have that $(\Phi_{r+1}[j]-1/k)^{2}\leq
1/k^{4+2\epsilon-2\ln(k^{\epsilon}-1)/\ln k}$. Hence, it is $\Phi_{r+1}[j]\leq
1/k+1/k^{2+\epsilon-\ln(k^{\epsilon}-1)/\ln k}$ for any node $j$. Moreover, if
$d\geq k\geq n$ the total potential in the network would be $\ell(n-\ell)$
(cf. Claim 1) and no individual node should have potential larger than
$\ell(n-\ell)(1/k+1/k^{2+\epsilon-\ln(k^{\epsilon}-1)/\ln
k})\leq\ell(k-\ell)(1/k+1/k^{2+\epsilon-\ln(k^{\epsilon}-1)/\ln k})$. We show
that the latter is at most $\tau=\ell(1-\ell/k^{1+\epsilon})$ as follows:

$\displaystyle\ell(k-\ell)\left(\frac{1}{k}+\frac{1}{k^{2+\epsilon-\ln(k^{\epsilon}-1)/\ln
k}}\right)$ $\displaystyle\leq\ell\left(1-\frac{\ell}{k^{1+\epsilon}}\right)$
$\displaystyle(k-\ell)\left(\frac{1}{k}+\frac{1}{k^{2+\epsilon-\ln(k^{\epsilon}-1)/\ln
k}}\right)$ $\displaystyle\leq 1-\frac{\ell}{k^{1+\epsilon}}$ $\displaystyle
1-\frac{\ell}{k}+\frac{k-\ell}{k^{2+\epsilon-\ln(k^{\epsilon}-1)/\ln k}}$
$\displaystyle\leq 1-\frac{\ell}{k^{1+\epsilon}}$
$\displaystyle\frac{k-\ell}{k^{2+\epsilon-\ln(k^{\epsilon}-1)/\ln k}}$
$\displaystyle\leq\frac{\ell}{k}-\frac{\ell}{k^{1+\epsilon}}$
$\displaystyle\frac{k-\ell}{k^{2+\epsilon-\ln(k^{\epsilon}-1)/\ln k}}$
$\displaystyle\leq\ell\frac{k^{\epsilon}-1}{k^{1+\epsilon}}$ $\displaystyle
k-\ell$ $\displaystyle\leq\ell(k^{\epsilon}-1)k^{1-\ln(k^{\epsilon}-1)/\ln k}\
,\textrm{ given that $k>\ell$,}$ $\displaystyle\ln(k-\ell)$
$\displaystyle\leq\ln\ell+\ln(k^{\epsilon}-1)+\left(1-\frac{\ln(k^{\epsilon}-1)}{\ln
k}\right)\ln k$ $\displaystyle\ln(k-\ell)$ $\displaystyle\leq\ln(\ell k)\
,\textrm{ given that $k>\ell$,}$ $\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_{1,r+1}\leq\tau$). (Notice the inverse relation between estimate and
potential.) In the following lemma we show that if $k^{1+\epsilon}<n$ (i.e.
low estimate) there are some nodes with $\Phi_{1,r+1}>\tau$ (i.e. high
potential), and that all the other nodes will know this within the following
phase.

###### Lemma 9

If $k^{1+\epsilon}<n$, $0<\epsilon\leq 1+\log_{k}4d$, and
$r\geq(4+2\epsilon-2\ln(k^{\epsilon}-1)/\ln k)dk^{2}\ln k$, within the
following $k^{1+\epsilon}$ rounds after the first phase of the MMC protocol,
all black nodes have received 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 7 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 8 (that in case of not-low estimate, $k\geq n$, there would not be any
node like them), all nodes in $H$ move to alarm status “low” at the end of
phase $1$ (cf. Lines 2.2 or 1.1). (Notice the inverse relation between
potential and status, which in turn indicates whether the estimate is low or
not.) Nodes in $L$ may not have low status, but due to $1$-interval
connectivity at least one new node from $L$ moves to status “low” in each of
the following rounds (Lines 2.2 or 1.1).

The number of rounds of the second phase is at least

$\displaystyle\left(4+2\epsilon-2\frac{\ln(k^{\epsilon}-1)}{\ln
k}\right)dk^{2}\ln k$
$\displaystyle=\left(4+2\epsilon-2\log_{k}(k^{\epsilon}-1)\right)dk^{2}\ln k$
$\displaystyle>\left(4+2\epsilon-2\log_{k}k^{\epsilon}\right)dk^{2}\ln k$
$\displaystyle>4dk^{2}\ .$

Given that the size of $L$ is at most $k^{1+\epsilon}$, to complete the proof
it is enough to show that $4dk^{2}\geq k^{1+\epsilon}$, which is true for
$\epsilon\leq 1+\log_{k}4d$.

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

###### Lemma 10

Under the following conditions $d>k>n>\ell>0$, for

$\beta\geq\log_{k}(n(2k^{\delta}-1))\ ,$
$\delta>\log_{k}\frac{k^{\gamma}(n-\ell)}{k^{\gamma}-(n-\ell)-1}\ ,$
$\gamma>\log_{k}(n-\ell+1)\ ,$

after running the MMC protocol for $p$ phases and $r$ rounds such that

$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 2\beta dk^{2}\ln k\ ,$

the potential $\rho$ consumed by any black node is

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

Proof. Given that $d>k>n$, we can use Theorem 4 as in Lemma 5 to show that
after a phase of $r\geq 2\beta dk^{2}\ln k$ rounds the distribution is such
that

$\displaystyle\left|\left|\vec{\Pi}_{r+1}-\frac{\vec{I}}{n}\right|\right|_{2}^{2}$
$\displaystyle\leq\left(1-\frac{1}{d{\cal
D}n}\right)^{r}\left|\left|\vec{\Pi}_{1}-\frac{\vec{I}}{n}\right|\right|_{2}^{2}$
$\displaystyle\leq\exp\left(-\frac{r}{d{\cal D}n}\right)$
$\displaystyle\leq\exp\left(-\frac{2\beta dk^{2}\ln k}{d{\cal D}n}\right).$

Given that $k>n>{\cal D}$, we have that

$\displaystyle\left|\left|\vec{\Pi}_{r+1}-\frac{\vec{I}}{n}\right|\right|_{2}^{2}$
$\displaystyle\leq\exp\left(-2\beta\ln k\right)$
$\displaystyle=\frac{1}{k^{2\beta}}\ .$

For any node $i$, given that
$(\Pi_{r+1}[i]-1/n)^{2}\leq\left|\left|\vec{\Pi}_{r+1}-\frac{\vec{I}}{n}\right|\right|_{2}^{2}$
we have that $(\Pi_{r+1}[i]-1/n)^{2}\leq 1/k^{2\beta}$ and hence
$\Pi_{r+1}[i]\geq 1/n-1/k^{\beta}$. The latter is true for any initial
distribution. Therefore, after each phase a black 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
$||\vec{\Phi}_{1,1}||_{1}=\ell(n-\ell)$. Using the latter observations, after
$p$ phases, any given black 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)}$
$\displaystyle=(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),$
$\displaystyle\hskip 144.54pt\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)$
$\displaystyle=(n-\ell)\frac{k^{\beta}+n}{k^{\beta}-n}\left(1+\frac{1}{k^{\delta}}\right)\left(1-\frac{1}{k^{\delta}}\right)$
$\displaystyle\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.

Based on the above lemmata, we establish the correctness and running time of
MMC in the following theorem.

###### Theorem 11

Given an ADN with $n$ nodes, which includes $\ell$ black nodes such that
$n>\ell\geq 1$, and where $\ell$ is known to all nodes, after running MMC for
each estimate $k=\ell+1,\ell+2,\ell+3,\dots,n$ with parameters:

$\displaystyle d$ $\displaystyle=k^{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=\left\lceil 2dk^{2}(\ln
k)\max\left\\{\alpha,\beta
k^{2\epsilon},2+\epsilon-\frac{\ln(k^{\epsilon}-1)}{\ln
k}\right\\}\right\rceil\ ,$ $\displaystyle\tau$
$\displaystyle=\ell\left(1-\frac{\ell}{k^{1+\epsilon}}\right)\ ,$

under the following conditions:

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

Then, 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. First we show that the parameters and conditions of the theorem fulfill
the conditions of previous lemmas. Notice that for $k<n\leq k^{\epsilon}$ it
is

$\displaystyle\gamma$
$\displaystyle>\log_{k}(d-1)=\log_{k}(k^{1+\epsilon}-1)\geq\log_{k}(n-1)\ ,$
$\displaystyle\delta$
$\displaystyle>\log_{k}\frac{dk^{\gamma}}{k^{\gamma}+1-d}=\log_{k}\frac{k^{1+\epsilon}k^{\gamma}}{k^{\gamma}+1-k^{1+\epsilon}}$
$\displaystyle\geq\log_{k}\frac{nk^{\gamma}}{k^{\gamma}+1-n}=\log_{k}\frac{nk^{\gamma}}{nk^{\gamma}-(n-1)(k^{\gamma}+1)}\
,$ $\displaystyle\beta$
$\displaystyle\geq\log_{k}(d(2k^{\delta}+1))=\log_{k}(k^{1+\epsilon}(2k^{\delta}+1))\geq\log_{k}(n(2k^{\delta}+1))\
,$ $\displaystyle\frac{\delta}{1/d+1/k^{\beta}}$
$\displaystyle=\frac{\delta}{1/k^{1+\epsilon}+1/k^{\beta}}\geq\frac{\delta}{1/n+1/k^{\beta}}\
,$

as required by Lemma 6. On the other hand, for $d>k>n>\ell>0$, it is

$\displaystyle\beta$
$\displaystyle\geq\log_{k}(d(2k^{\delta}+1))\geq\log_{k}(n(2k^{\delta}-1))\ ,$
$\displaystyle\delta$
$\displaystyle>\log_{k}\frac{dk^{\gamma}}{k^{\gamma}+1-d}>\log_{k}\frac{k^{\gamma}(n-\ell)}{k^{\gamma}-(n-\ell)-1}\
,$ $\displaystyle\gamma$ $\displaystyle>\log_{k}(d-1)>\log_{k}(n-\ell+1)\ ,$

and

$\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\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 r$ $\displaystyle=\left\lceil 2dk^{2}(\ln
k)\max\left\\{\alpha,\beta
k^{2\epsilon},2+\epsilon-\frac{\ln(k^{\epsilon}-1)}{\ln
k}\right\\}\right\rceil\geq 2\beta dk^{2}\ln k\ ,$

as required by Lemma 10. And also we verify that for $d=k^{1+\epsilon}$ it is
$1+\log_{k}4d=2+\epsilon+\log_{k}4\geq\epsilon$, as required by Lemma 9.

We prove first that MMC is correct. To do so, it is enough to show that for
each estimate $k\neq n$ the algorithm detects the error and moves to the next
estimate, and that if otherwise $k=n$ the algorithm stops and outputs $k$. We
consider four cases: $k=n$, $k>n$, $k<n\leq k^{1+\epsilon}$, and
$k^{1+\epsilon}<n$, for some $\epsilon>0$.

Assume first that $k^{1+\epsilon}<n$. Lemmas 7 and 9 show that within the
following $k^{1+\epsilon}$ rounds after the first phase all nodes have
received and/or produced an alarm status “low”, even if no node has detected
more than $d-1$ neighbors during the execution of this phase. Moreover, Lemma
8 shows that the event triggering this alarm would not have happened if the
estimate was not low. For the given function $p$ and $k\geq\ell+1$, the epoch
has more than one phase. Therefore, within $k^{1+\epsilon}$ rounds into the
second phase, all nodes will have status “low” (Lines 1.1 and 2.2), and will
not change their status in this epoch (which could only happen if black nodes
were in status “probing” in Line 1.1). Hence, all nodes will continue to the
next epoch after updating $k$ accordingly in Lines 1.1 and 2.2.

Assume now that $k<n\leq k^{1+\epsilon}$. Even if some black nodes do not
receive an alarm status “low” during the execution, as shown in Lemma 6, at
the end of the epoch in Line 1.1 all black nodes will detect that $\rho$ is
too large and will change their status to “low”. Then, they will disseminate
their status in the loop of Line 1.1, which has enough iterations to reach all
nodes due to $1$-interval connectivity and $d=k^{1+\epsilon}\geq n$. Then, all
nodes will continue to the next epoch after updating $k$ appropriately.

If $k>n$, Lemma 10 shows that the accumulated potential $\rho$ of every black
node after running MMC for $p$ phases will be less than
$(k-\ell)(1-1/k^{\gamma})$, which is detected by the black nodes in Line 1.1.
Thus, all black nodes will change their status to “high”. Then, they will
disseminate their status in the loop of Line 1.1, which has enough iterations
to reach all nodes due to $1$-interval connectivity and $d>k>n$. Then, all
nodes will continue to the next epoch after updating $k$ appropriately.

Finally, if $k=n$, Lemma 5 shows that the accumulated potential $\rho$ of
every black node after running MMC long enough will be
$(k-\ell)(1-1/k^{\gamma})\leq\rho\leq(k-\ell)(1+1/k^{\gamma})$. Thus, in Line
1.1 all black nodes will change their status to “done”, and in the loop of
Line 1.1 will inform all other nodes that the current estimate is correct
disseminating their status. The number of iterations is enough to do so due to
$1$-interval connectivity.

The claimed running time can be obtained by inspection of either algorithm,
black nodes or white nodes, since they are synchronized. Refer for instance to
Algorithm 1. For each epoch, Line 1.1 starts a loop of $p$ phases followed by
$d$ rounds in Line 1.1. Each of the $p$ phases has $r$ rounds. In each round,
nodes communicate exactly once. Then, the number of communication rounds on
each epoch is $pr+d$. The parameters $p$, $r$, and $d$ are all monotonically
increasing functions of $k$. Hence, the running time $pr+d$ for each epoch
depends on the estimate size $k$ used in that epoch, and if the values of $k$
for a given network depend on the execution, the execution with largest values
of $k$ is the worst case.

For a given network, the sequence of values of $k$ used is initially
$2^{i}(\ell+1)$ for $i=0,1,\dots,\log\lceil n/(\ell+1)\rceil$, which is the
set $E$ defined in the theorem, independently of the execution. Once
$i=\log\lceil n/(\ell+1)\rceil$, if $k\neq n$, $k$ will be updated in a binary
search fashion within the range $(2^{i-1}(\ell+1),2^{i}(\ell+1))$. The worst
case then corresponds to a binary search concentrated in the larger half of
each successive range. Such sequence of values of $k$ is $(2^{\log\lceil
n/(\ell+1)\rceil}-2^{i})(\ell+1)$ for $i=0,1,\dots,\log\lceil
n/(\ell+1)\rceil-2$, which is the set $B$ defined in the theorem.

Thus, the claimed worst-case number of communication rounds follows.

###### Corollary 12

The time complexity of MMC on an ADN with $\ell$ black nodes and $n-\ell$
white nodes is $O\left(\frac{n^{4+\epsilon}}{\ell}\log^{3}n\right)$, for any
$\epsilon>0$.

Proof. The following algebraic manipulations refer to the parameters and
conditions in Theorem 11. Fixing $\alpha=1+\gamma+\log_{k}3$,
$\beta=\log_{k}(d(2k^{\delta}+1))$, and $\gamma=\log_{k}d$, the conditions on
$\alpha$, $\beta$, and $\gamma$ are fulfilled. Replacing $d=k^{1+\epsilon}$
and $\gamma=\log_{k}d$ in the condition on $\delta$, we have that
$\delta>2(1+\epsilon)$. Therefore, in the maximization in the definition of
$p$, we get that
$\max\left\\{\frac{\delta}{1/d+1/k^{\beta}},\frac{\gamma}{1/k+1/k^{\alpha}}\right\\}=\frac{\delta}{1/d+1/k^{\beta}}$.
Thus, it is

$\displaystyle p$ $\displaystyle=\left\lceil\frac{2\ln
k}{\ell}\frac{\delta}{1/d+1/k^{\beta}}\right\rceil$
$\displaystyle=\left\lceil\frac{2\ln
k}{\ell}\frac{\delta}{1/d+1/(d(2k^{\delta}+1))}\right\rceil$
$\displaystyle=\left\lceil\frac{2d\ln
k}{\ell}\frac{\delta}{1+1/(2k^{\delta}+1)}\right\rceil$
$\displaystyle<\left\lceil\frac{2d\ln k^{\delta}}{\ell}\right\rceil.$

On the other hand, replacing $\alpha$, $\beta$ and $\gamma$ in the
maximization in the definition of $r$, that is $\max\left\\{\alpha,\beta
k^{2\epsilon},2+\epsilon-\frac{\ln(k^{\epsilon}-1)}{\ln k}\right\\}$, we
observe that $\beta k^{2\epsilon}>2+\epsilon-\frac{\ln(k^{\epsilon}-1)}{\ln
k}$ and $\beta k^{2\epsilon}>\alpha$. Thus, it is

$\displaystyle r$ $\displaystyle=\left\lceil 2dk^{2}(\ln k)\beta
k^{2\epsilon}\right\rceil$ $\displaystyle=\left\lceil 2d^{3}\beta\ln
k\right\rceil$ $\displaystyle=\left\lceil 2d^{3}\log_{k}(d(2k^{\delta}+1))\ln
k\right\rceil$ $\displaystyle=\left\lceil
2d^{3}\ln(d(2k^{\delta}+1))\right\rceil.$

Then, replacing in $pr+d$, we get

$\displaystyle pr+d<\left\lceil\frac{2d}{\ell}\ln
k^{\delta}\right\rceil\left\lceil 2d^{3}\ln(d(2k^{\delta}+1))\right\rceil+d\in
O\left(\frac{d^{4}}{\ell}\log^{2}d\right).$

Replacing $d=k^{1+\epsilon}<(2n)^{1+\epsilon}$ and noticing that the total
number of terms in the summation of the running time of Theorem 11 is
$O(\log(n/\ell))$, the claim follows.

##  6 Randomized Unconscious Counting

In this section, we present and analyze our randomized algorithm for
Unconscious Counting [11] as defined in Section 2, that is, in finite time all
nodes must obtain the correct count, possibly not knowing when exactly they
have got it.

In our algorithm, that we call Leaderless Methodical Counting (LLMC), nodes
update their count, possibly multiple times. We show that there is a point in
the execution where all nodes have obtained the correct count, and do not
change it to an incorrect count anymore. Nodes do not know when the count is
final, hence they continue executing the algorithm forever. Although LLMC does
not terminate, our analysis shows an upper bound on the time to obtain the
final count. Given that the time bound is a function of $n$ and $n$ is
unknown, it cannot be used as a termination condition.

We first give the intuition of the algorithm referring to the pseudocode in
Algorithm 3. LLMC uses a modified version of MMC as a subroutine. We summarize
those modifications in Algorithm 4. Further pseudocode details can be found in
Algorithms 5 and 6. Recall that references to algorithms lines are given as
$\langle algorithm\\#\rangle.\langle line\\#\rangle$.

The main idea of LLMC is the following. We consider consecutive powers of $2$
as values of some variable $K$. For each such $K$, we select black nodes
locally with probability corresponding to the inverse of $K$, and we run MMC
configured for one black node. We call this modified algorithm MMCT with
parameters $K$ and $\ell^{\prime}$, where $\ell^{\prime}$ is the aimed number
of black nodes. Thus, it is $\ell^{\prime}=1$, whereas $\ell$ is the actual
number of black nodes after the random choices.

If $K\geq n$ and there is indeed one black node (i.e. $\ell=\ell^{\prime}=1$),
MMCT guarantees that all nodes obtain the exact count $n$ of nodes. Because
$K$ is doubled iteratively at some point it will be $K\geq n$. There is
however a problem: what to do when $K\geq n$ but there is no black node or at
least two black nodes. Algorithm LLMC overcomes this issue with two
techniques:

  * •

Introducing parallel threads (Line 3.3) and carefully counting locally the
number of threads with no black nodes recorded (Line 3.3) and requiring their
ratio to be bigger than half (Line 3.3). The latter is to have guarantees that
in at least one thread it is $\ell=1$ with sufficiently high probability.

  * •

Making use of the fact that having more than one black node in the execution
of MMCT configured for $\ell^{\prime}=1$ (as a subroutine of LLMC) cannot
return an estimate bigger than if it was run with one black node; therefore,
taking the maximum of returned estimates over threads (Line 3.3) addresses the
potential problem of more than one black node.

The main control parameter used in LLMC is $K$, which is an upper bound for
estimates considered in one execution of the while loop (Line 3.3), which we
call _iteration_ $K$. We start from a value of $K$ (Line 3.3) appropriate for
our analysis. Within one iteration, we initiate $f(K)$ parallel threads (Line
3.3). That is, nodes run $f(K)$ instances of the same algorithm specified in
Lines 3.3 to 3.3, sharing among all instances a variable $EmptyThreads$ and a
set $Count$ for each node. For each thread, we select black nodes for the
whole thread (Line 3.3) — trying to make sure that the chance of getting one
black node is sufficiently large, especially for $K\geq n$ (recall that we
could not recognize for sure whether $K\geq n$ or not). Then, in each thread
independently, we run MMCT configured for $\ell^{\prime}=1$ as a subroutine
(Line 3.3), hoping that we selected exactly one black node
($\ell=\ell^{\prime}$) in the beginning of the iteration. MMCT checks all
possible values of $k$ from $1$ to $K$ aiming to find a good estimate of $n$.
I.e., in MMCT we trim the execution of MMC to estimates $k\leq K$ (Line 4.4).

This approach does not work for $K<n$, as then the probability of getting more
than one black node could be bigger than the one for one black node; however,
we can eliminate such cases by monitoring the number of threads with no black
node (Line 3.3), which in case of $K<n$ should be compared with a large
threshold (Line 3.3). Intuitively, we want LLMC to reach this threshold with
high probability when $K$ is close to $n$. Note that in MMCT a no-black-node
thread will output an indicator of such event, and a thread that does not
reach a result (e.g. if $\ell=1$ but $K<n$) will output a count of zero (Line
4.4). If instead a thread identifies a good estimate (i.e. MMCT returns a
count larger than $0$ in that thread) it adds its value to the set $Count$ and
rather than entering the next iteration, stops returning the maximum value in
the set $Count$ (Line 3.3). The latter is to give preference to threads with
one black node over those with more than one black node (we will argue that
threads with more than one black node could return values, but not bigger than
ones by threads with one black node).

For $K<n$, there is a chance of having some threads with undetected black
nodes for some nodes and detected for others, and some of those nodes may
obtain a count, but such count will be smaller than $n$ because $K<n$ and MMCT
outputs an estimate $k\leq K$. Thus, this incorrect count will be updated
later on when $K$ increases (cf. Line 3.3).

For $K\geq n$ there will be an iteration when all nodes obtain the correct
count with large enough probability, as we show in our analysis. In later
iterations, some threads may have more than one black node yielding MMCT to
return an incorrect count, but such count will be smaller than $n$. Hence,
nodes disregard it (cf. Line 3.3).

1 $count\leftarrow 0$

$K\leftarrow\lceil\lceil 12/\zeta\rceil\rceil$

// $\lceil\lceil x\rceil\rceil$: the smallest power of 2 bigger than $x$

$Count\leftarrow\emptyset$

// set of potentially "good" estimates computed

$EmptyThreads\leftarrow 0$

// # threads with no black node detected

2 while  _true_ do

3 $Count\leftarrow\emptyset$, $EmptyThreads\leftarrow 0$

4 $K\leftarrow 2K$

Initiate $f(K)=64\frac{\log(K/\zeta)}{\log(e/(e-2))}$ parallel threads

// parallel computation and messages sharing same resources/medium

5 for  _each thread_ do

6 for  _each node_ do

7 Select to be a black node with probability $1/g(K)$, where $g(K)=K/2$

8

$\langle k,b\rangle\leftarrow MMCT(K,1)$

// refer to Algorithm 4

9 if  _$k >0$_ then $Count\leftarrow Count\cup\\{k\\}$

10 if  _$b=false$_ then // no black node detected

11 $EmptyThreads\leftarrow EmptyThreads+1$

12

13

14 if  _$Count\neq\emptyset$ and $EmptyThreads>f(K)/2$_ then

$count\leftarrow\max\\{count,\max(Count)\\}$

// update $n$

15

16

17

Algorithm 3 LLMC algorithm for each node. $\zeta\in(0,1)$ and $K$ is notation
for the maximum size estimate.

1 Function  _MMCT (_$K$ ,$\ell^{\prime}$_)_

2 Run MMC modified as follows:

3 – Stop iterations when size estimate $k>K$

// Lines 5.5 and 6.6

4 – If estimate $k<K$, remain idle until end of phase $K$

// for synch, Lines 5.5and 6.6

5

6 – Include a Boolean $b_{j}$ in each node $j$ as follows:

7 — Initially:

8 if  _node $j$ is black_ then $b_{j}\leftarrow true$ else $b_{j}\leftarrow
false$

// Lines 5.5 and 6.6

9 — In each iteration:

10 Broadcast and Receive messages including $b_{j}$

11 if  _$b_{i}=true$ received from some neighbor $i$_ then $b_{j}\leftarrow
true$

// Lines 6.6 and 6.6

12

13 Upon completion, for each node $j$:

14 if  _$status=done$_ then return $\langle k,b_{j}\rangle$ else return
$\langle 0,b_{j}\rangle$

// Lines 5.5 and 6.6

15

Algorithm 4 Summary of modifications of MMC to be used as a subroutine for
LLMC. Refer to Algorithms 5 and 6 for the complete details of MMCT.
$\ell^{\prime}$ is the aimed number of black nodes and $K$ is the maximum size
estimate.

1 Function  _MMCT (_$K$ ,$\ell^{\prime}$_)_

2

$k\leftarrow\ell^{\prime}+1,min\leftarrow k,max\leftarrow\infty$

// initial size estimate and range

$b\leftarrow true$

// existence of black nodes

$\\#rounds\leftarrow 0$

// counter of communication rounds for synchronization

3 repeat // iterating epochs

$status\leftarrow probing$, $\Phi\leftarrow 0$

// status$=$probing$|$low$|$high$|$done, current potential

$\rho\leftarrow 0$

// potential accumulator

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

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

6 Broadcast $\langle\Phi,status,b\rangle$ and Receive
$\langle\Phi_{i},status_{i},b_{i}\rangle,\forall i\in N$

7 $\\#rounds\leftarrow\\#rounds+1$

8 if  _$status=probing$ and $|N|\leq d-1$ and $\forall i\in
N:status_{i}=probing$_ then

$\Phi\leftarrow\Phi+\sum_{i\in N}\Phi_{i}/d-|N|\Phi/d$

// update potential

9

10 else // $k<n$

11 $status\leftarrow low$, $\Phi\leftarrow\ell^{\prime}$

12

13 if  _$phase=1$ and $\Phi>\tau$_ then // $k<n$

14 $status\leftarrow low$, $\Phi\leftarrow\ell^{\prime}$

15 if  _$status=probing$_ then // prepare for next phase

$\rho\leftarrow\rho+\Phi$

// consume potential

16 $\Phi\leftarrow 0$

17

18 if  _$status=probing$_ then

19 if
_$(k-\ell^{\prime})(1-k^{-\gamma})\leq\rho\leq(k-\ell^{\prime})(1+k^{-\gamma})$_
then $status\leftarrow done$

20 // $k=n$ if  _$\rho <(k-\ell^{\prime})(1-k^{-\gamma})$_ then
$status\leftarrow high$

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

22 // $k<n$

23 for  _$round=1$ to $d$_ do // disseminate status and existence of black
nodes

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

25 $\\#rounds\leftarrow\\#rounds+1$

26

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

28 $min\leftarrow k+1$

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

30

31 else

32 if  _$status=high$_ then

33 $max\leftarrow k-1$

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

35

36

37

38 until  _$status=done$ or $k>K$_

39 while  _$\\#rounds\leq round_{\max}$_ do // for synchronization among
threads

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

41 $\\#rounds\leftarrow\\#rounds+1$

42

43 if  _$status=done$_ then return $\langle k,b\rangle$ else return $\langle
0,b\rangle$

44

Algorithm 5 MMCT algorithm for each _black node_. Sections that are identical
to MMC are grayed-out. $N$ is the set of neighbors of this node in the current
round, $\ell^{\prime}$ and $K$ are notations for the aimed number of black
nodes and the maximum size estimate respectively. The parameters $d,p,r$ and
$\tau$ are as defined in Theorem 11 for MMC, as functions of $k,\ell^{\prime}$
instead of $k,\ell$, and $round_{\max}=\sum_{k=2^{i}:i=1,2,\dots,\lceil\log
K\rceil}(pr+d)$.

1 Function  _MMC (_$K$ ,$\ell^{\prime}$_)_

2

$k\leftarrow\ell^{\prime}+1,min\leftarrow k,max\leftarrow\infty$

// initial size estimate and range

$b\leftarrow false$

// existence of black nodes

$\\#rounds\leftarrow 0$

// counter of communication rounds for synchronization

3 repeat // iterating epochs

$status\leftarrow probing$, $\Phi\leftarrow\ell^{\prime}$

// status$=$probing$|$low$|$high$|$done, current potential

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

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

6 Broadcast $\langle\Phi,status,b\rangle$ and Receive
$\langle\Phi_{i},status_{i},b_{i}\rangle,\forall i\in N$

7 $\\#rounds\leftarrow\\#rounds+1$

8 if  _$\exists i\in N:b_{i}=true$_ then $b\leftarrow true$

9 if  _$status=probing$ and $|N|\leq d-1$ and $\forall i\in
N:status_{i}=probing$_ then

10 $\Phi\leftarrow\Phi+\sum_{i\in N}\Phi_{i}/d-|N|\Phi/d$ // update potential

11 else $status\leftarrow low$, $\Phi\leftarrow\ell^{\prime}$

12 // $k<n$

13 if  _$phase=1$ and $\Phi>\tau$_ then $status\leftarrow low$,
$\Phi\leftarrow\ell^{\prime}$

14 // $k<n$

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

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

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

18 $\\#rounds\leftarrow\\#rounds+1$

19 if  _$\exists i\in N:b_{i}=true$_ then $b\leftarrow true$

20

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

22 $min\leftarrow k+1$

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

24

25 else

26 if  _$status=high$_ then

27 $max\leftarrow k-1$

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

29

30

31

32 until  _$status=done$ or $k>K$_

33 while  _$\\#rounds\leq round_{\max}$_ do // for synchronization among
threads

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

35 $\\#rounds\leftarrow\\#rounds+1$

36 if  _$\exists i\in N:b_{i}=true$_ then $b\leftarrow true$

37

38 if  _$status=done$_ then return $\langle k,b\rangle$ else return $\langle
0,b\rangle$

39

Algorithm 6 MMCT algorithm for each _white node_. Sections that are identical
to MMC are grayed-out. $N$ is the set of neighbors of this node in the current
round, $\ell^{\prime}$ and $K$ are notations for the aimed number of black
nodes and the maximum size estimate respectively. The parameters $d,p,r$ and
$\tau$ are as defined in Theorem 11 for MMC, but as functions of
$k,\ell^{\prime}$ instead of $k,\ell$, and
$round_{\max}=\sum_{k=2^{i}:i=1,2,\dots,\lceil\log K\rceil}(pr+d)$.

###  6.1 Analysis of LLMC

Throughout the analysis that follows, we consider an adaptive adversary, as we
allow network changes to be done online when viewing the whole history of the
computation up to the current round.

Recall that we refer to an execution of the while loop in Line 3.3 for fixed
parameter $K$ as iteration $K$. Recall also that $K$ is a power of $2$ bigger
than $\lceil\lceil 12/\zeta\rceil\rceil$ (cf. Line 3.3). By $\lceil\lceil
x\rceil\rceil$ we denote the smallest power of $2$ bigger than $x$.

We conjecture that all arbitrary constants in the algorithm, i.e., in the
definition of the starting value of $K$, functions $f(K)$ and $g(K)$, could be
substantially lowered, as we set them high to avoid too many cases in the
analysis (so making it as much focused on main arguments as possible).

In the analysis of LLMC that follows, we refer to lemmas proving properties of
MMC. Those properties also hold for MMCT, after changing $\ell$ by
$\ell^{\prime}$ and $n$ by $K$ as needed.

While $K<n$, nodes may obtain a count, and such count may be incorrect.
However, given that LLMC continues executing doubling $K$, we focus on:
showing that for $K\geq n$ the count obtained is correct, bounding the time to
reach that state, and showing that after the correct count is obtained the
nodes do not go back to an incorrect count. We start from stating the
following structural property.

###### Proposition 1

For any iteration $K\geq n$, if the number of threads with no black node is
bigger than $f(K)/2$, and there is at least one thread with one black node,
then all threads with one black node store the same value in the set $Count$
and it is the biggest value stored in $Count$ in this iteration.

Proof. By properties of algorithm MMCT run for $\ell^{\prime}=1$ as a
subroutine, when $K\geq n$, threads with one black node store the correct
value of $n$ in the set $Count$ (c.f., Theorem 11 for MMC and Line 3.3).
Threads with no black node do not store any value in $Count$, while in threads
with at least two black nodes, black nodes acummulate a potential that yield a
count at most $n$, hence nodes store a value at most $n$ in $Count$ (c.f. Line
5.5 in MMCT or Line 1.1 in MMC). Therefore, by taking the maximum value from
the set $Count$ in Line 3.3 in MMC, each node obtains the correct count in the
considered case.

###### Lemma 13

Consider an iteration $K\geq n$. The probability of event: in iteration $K$
all nodes obtain the correct count, is at least
$1-\exp(-f(K)/64)-\exp\left(-\frac{nf(K)}{g(K)e}\right)$.

Proof. Observe that the considered event is implied by the following case: the
number of threads without a black node is bigger than $f(K)/2$ and there is a
thread with exactly one black node. Thus, by Proposition 1 all nodes obtain
the correct value. Therefore, it is enough to estimate from below the
probability of the case to hold.

The probability of a fixed thread to be without a black node is

$\left(1-\frac{1}{g(K)}\right)^{n}\geq\min\left\\{4^{-n/g(K)},1-\frac{n}{g(K)}\right\\}\geq\frac{3}{4}$

for $K\geq 8n$, by simple calculus and definition of function $g$. Therefore,
the expected number of threads with no black node is at least $3f(K)/4$ for
$K\geq 8n$. By Chernoff bound, the probability that this number is bigger than
$f(K)/2$ is at least $1-\exp(-f(K)/64)$, for $K\geq 8n$.

On the other hand, the probability that there is a thread with exactly one
black node is

$\displaystyle
1-\left(1-\frac{n}{g(K)}\left(1-\frac{1}{g(K)}\right)^{n-1}\right)^{f(K)}$
$\displaystyle\geq 1-\left(1-\frac{n}{g(K)e}\right)^{f(K)}$ $\displaystyle\geq
1-\exp\left(-\frac{nf(K)}{g(K)e}\right)\ .$

Putting the two probabilities together, we get that the probability of the
considered event is at least

$1-\exp(-f(K)/64)-\exp\left(-\frac{nf(K)}{g(K)e}\right)\ .$

###### Corollary 14

Consider iteration $K=\lceil\lceil 8n\rceil\rceil$. The probability of event:
in iteration $K$ all nodes obtain the correct count, is at least $1-\zeta/n$.

Proof. By substituting $K$ by $\lceil\lceil 8n\rceil\rceil$ in Lemma 13 we get
the probability of the considered event to be at least
$1-\exp(-f(K)/64)-\exp\left(-\frac{nf(K)}{g(K)e}\right)\geq
1-\zeta/(2n)-\zeta/(2n)=1-\zeta/n$.

###### Theorem 15

For any given $\epsilon>0$ and $\zeta>0$, with probability at least $1-\zeta$,
all nodes running LLMC obtain the correct count $n$ in
$O((n+1/\zeta)^{4+\epsilon}\log^{3}(n+1/\zeta))$ rounds and will not change it
to an incorrect count after that, even when running against an adaptive
adversary.

Proof. By Corollary 14, all nodes obtain the correct count at the end of
iteration $K=\lceil\lceil 8n\rceil\rceil$, with probability at least
$1-\zeta/n$.

As $K$ increases beyond $\lceil\lceil 8n\rceil\rceil$, the probability of
having more than $f(K)/2$ threads without black nodes increases. Thus, threads
with black nodes may produce a count in future iterations. If there is a
thread with exactly one black node, all nodes obtain the correct count by
Proposition 1. If on the other hand in those threads either $\ell=0$ or
$\ell>1$, nodes do not obtain a new count or obtain a count smaller than $n$
respectively. Hence, nodes do not update their count in Line 3.3.

The total number of communication rounds for each iteration of LLMC is the
number of rounds defined in MMCT, which is
$round_{\max}=\sum_{k=2^{i}:i=1,2,\dots,\lceil\log K\rceil}(pr+d)$ (recall
that $p$, $r$, and $d$ depend on $k$). The value of $round_{\max}$ corresponds
to the worst case scenario (with respect to running time) of $\ell=1$. As in
Corollary 12 (of MMC) we can show that the latter is $round_{\max}\in
O(K^{4+\epsilon}\log^{3}K)$, which is then the running time of each iteration
$K$.

Now we consider two cases. If $\lceil\lceil 12/\zeta\rceil\rceil$, which is
the initial value of $K$, is larger than $\lceil\lceil 8n\rceil\rceil$, which
is the value of $K$ in the last iteration, we know that LLMC will have only
one iteration. Thus, the running time would be $O(K^{4+\epsilon}\log^{3}K)\in
O((1/\zeta)^{4+\epsilon}\log^{3}(1/\zeta))$. Otherwise, if $\lceil\lceil
12/\zeta\rceil\rceil\leq\lceil\lceil 8n\rceil\rceil$, the number of rounds by
the end of iteration $K=\lceil\lceil 8n\rceil\rceil$ is
$O(n^{4+\epsilon}\log^{3}n)$, since $K=O(n)$, by the end of iteration $K$
there were less than $\log K$ iterations, $K,K/2,K/2^{2},\ldots$, and each
iteration $K/2^{i}$ had $O((K/2^{i})^{4+\epsilon}\log^{3}(K/2^{i}))$ rounds.
Summing up these times we get $O(K^{4+\epsilon}\log^{3}K)\in
O(n^{4+\epsilon}\log^{3}n)$. Thus, the claimed time to obtain the correct
count follows.

##  7 Conclusions

This paper expanded the knowledge about feasibility of polynomial computation
in anonymous dynamic environment/networks. In particular, a counting-type of
computation could be done deterministically if symmetry is broken by existing
a partition of nodes in which one part knows its size. It is also feasible
without any distinction between the nodes with an arbitrary probability,
albeit without termination. Our algorithms are structured in phases, where
nodes average some potential values. This phased process, which could be
slower than a continuous one, is needed by our analysis. We leave the study of
how to simplify the structure of the algorithm and to speed up the computation
for future work. Other natural open directions include studying randomized
approximation solutions and extension to other related models and problems, as
well as deriving tighter upper and lower bounds in the considered setting.

## Acknowledgements

We thank anonymous reviewers for numerous comments and suggestions to improve
the quality of arguments and presentation. This work was supported by the
National Science Center Poland (NCN) grant 2017/25/B/ST6/02553; the UK Royal
Society International Exchanges 2017 Round 3 Grant #170293; and Pace
University SRC Grant and Kenan Fund.

## References

  * [1] 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.
  * [2] Roberto Baldoni and Giuseppe A Di Luna.  Counting on anonymous dynamic networks: Bounds and algorithms.  manuscript, 2016.
  * [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] Stephen Boyd, Arpita Ghosh, Balaji Prabhakar, and Devavrat Shah.  Randomized gossip algorithms.  IEEE Transactions on Information Theory, 52(6):2508–2530, 2006\.
  * [5] 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.
  * [6] 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.
  * [7] Maitri Chakraborty, Alessia Milani, and Miguel A. Mosteiro.  A faster exact-counting protocol for anonymous dynamic networks.  Algorithmica, 80(11):3023–3049, 2018.
  * [8] 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\.
  * [9] Giuseppe Antonio Di Luna and Roberto Baldoni.  Investigating the cost of anonymity on dynamic networks.  CoRR, abs/1505.03509, 2015.
  * [10] Giuseppe Antonio Di Luna and Roberto Baldoni.  Non trivial computations in anonymous dynamic networks.  In Proceedings of the 19th International Conference on Principles of Distributed Systems, Leibniz International Proceedings in Informatics, 2015.  To appear.
  * [11] 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.
  * [12] 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.
  * [13] 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.
  * [14] M. Farach-Colton, A. Fernández Anta, A. Milani, M. A. Mosteiro, and S. Zaks.  Opportunistic information dissemination in mobile ad-hoc networks: adaptiveness vs. obliviousness and randomization vs. determinism.  In Proc. of the 10th Latin American Theoretical Informatics Symposium, volume 7256 of Lecture Notes in Computer Science, pages 303–314. Springer-Verlag, Berlin, 2012.
  * [15] Antonio Fernández Anta, Alessia Milani, Miguel A. Mosteiro, and Shmuel Zaks.  Opportunistic information dissemination in mobile ad-hoc networks: the profit of global synchrony.  Distributed Computing, 25(4):279–296, 2012.
  * [16] Dariusz R. Kowalski and Miguel A. Mosteiro.  Polynomial counting in anonymous dynamic networks with applications to anonymous dynamic algebraic computations.  In 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic, pages 156:1–156:14, 2018.
  * [17] Dariusz R. Kowalski and Miguel A. Mosteiro.  Polynomial anonymous dynamic distributed computing without a unique leader.  In Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi, editors, 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9-12, 2019, Patras, Greece, volume 132 of LIPIcs, pages 147:1–147:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.
  * [18] 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.
  * [19] 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.
  * [20] 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.
  * [21] D. S. Mitrinović.  Elementary Inequalities.  P. Noordhoff Ltd. - Groningen, 1964.
  * [22] Damon Mosk-Aoyama and Devavrat Shah.  Fast distributed algorithms for computing separable functions.  IEEE Transactions on Information Theory, 54(7):2997–3007, 2008\.
  * [23] Angelia Nedic, Alex Olshevsky, Asuman Ozdaglar, and John N Tsitsiklis.  On distributed averaging algorithms and quantization effects.  IEEE Transactions on Automatic Control, 54(11):2506–2517, 2009\.
  * [24] Sujay Sanghavi, Bruce Hajek, and Laurent Massoulié.  Gossiping with multiple messages.  IEEE Transactions on Information Theory, 53(12):4640–4654, 2007\.
  * [25] Atish Das Sarma, Anisur Rahaman Molla, and Gopal Pandurangan.  Distributed computation in dynamic networks via random walks.  Theoretical Computer Science, 581:45–66, 2015.