# Computing in Anonymous Dynamic Networks Is Linear

Giuseppe A. Di Luna  DIAG, Sapienza University of Rome<EMAIL_ADDRESS>Giovanni Viglietta  Japan Advanced Institute of Science and Technology
(JAIST<EMAIL_ADDRESS>
###### Abstract

We give the first linear-time counting algorithm for processes in anonymous
1-interval-connected dynamic networks with a leader. As a byproduct, we are
able to compute in $3n$ rounds _every_ function that is deterministically
computable in such networks. If explicit termination is not required, the
running time improves to $2n$ rounds, which we show to be optimal up to a
small additive constant (this is also the first non-trivial lower bound for
counting). As our main tool of investigation, we introduce a combinatorial
structure called _history tree_ , which is of independent interest. This makes
our paper completely self-contained, our proofs elegant and transparent, and
our algorithms straightforward to implement.

In recent years, considerable effort has been devoted to the design and
analysis of counting algorithms for anonymous 1-interval-connected networks
with a leader. A series of increasingly sophisticated works, mostly based on
classical mass-distribution techniques, have recently led to a celebrated
counting algorithm in $O({n^{4+\epsilon}}\log^{3}(n))$ rounds (for
$\epsilon>0$), which was the state of the art prior to this paper. Our
contribution not only opens a promising line of research on applications of
history trees, but also demonstrates that computation in anonymous dynamic
networks is practically feasible and far less demanding than previously
conjectured.

> All our wisdom is stored in the trees.
>
> Santosh Kalwar

###### Contents

  1. 1 Introduction
    1. 1.1 Our Contributions
  2. 2 Definitions and Preliminaries
  3. 3 History Trees
  4. 4 Linear-Time Computation
    1. 4.1 Stabilizing Algorithm
    2. 4.2 Terminating Algorithm
  5. 5 Negative Results
  6. 6 Conclusion
  7. A Formal Model Definition and Basic Results
    1. A.1 Model of Computation
    2. A.2 Multi-Aggregation Problems
    3. A.3 Counting Problem
  8. B Formal Definition of History Trees and Basic Properties
    1. B.1 Abstract Structure of a History Tree
    2. B.2 History Tree of a Dynamic Network
    3. B.3 Basic Properties of History Trees
    4. B.4 Constructing and Updating History Trees
  9. C Additional Lower Bounds and Counterexamples
    1. C.1 Naive Termination May Fail
    2. C.2 Worst-Case Example for the Terminating Algorithm
    3. C.3 More General but Wearker Lower Bounds
  10. D Survey of Related Work
    1. D.1 Dynamic Networks with IDs
    2. D.2 Anonymous Static Networks
    3. D.3 Counting in Anonymous Interval-Connected Networks
    4. D.4 Average Consensus

##  1 Introduction

Background. The study of theoretical and practical aspects of highly dynamic
distributed systems has received a great deal of attention [10, 33, 36]. These
models involve a constantly changing network of computational devices called
_processes_ (sometimes referred to as “processors” or “agents”). This dynamism
is typical of modern real-world systems and is the result of technological
innovations, such as the spread of mobile devices, software-defined networks,
wirelesses sensor networks, wearable devices, smartphones, etc.

There are several models of dynamism [10]; a popular choice is the
_1-interval-connected_ network model [31, 38]. Here, a fixed set of $n$
processes communicate through links forming a time-varying graph, i.e., a
graph whose edge set changes at discrete time units called _rounds_ (thus, the
system is synchronous); such a graph changes unpredictably, but is assumed to
be connected at all times.

A large number of research papers have considered dynamic systems where each
process has a distinct identity (_unique IDs_) [31]. In this setting, there
are efficient algorithms for consensus [32], broadcast [9], counting [31, 38],
and many other problems [30, 36].

The study of dynamic 1-interval-connected networks with unique IDs began with
a seminal paper by Kuhn et al. [31], who showed that knowing the size of the
system (i.e., the number $n$ of processes) is useful for non-trivial
computations. For example, to find out if there is at least one process with
input $x$ in the system, every process can start broadcasting its input and
wait $n-1$ rounds to see if it receives $x$. Note that this technique is
ineffective if nothing is known about $n$.

Counting problem. There are real-world scenarios in which the individual
processes may be unaware of the size of the system; an example are large-scale
ad-hoc sensor networks [38]. In such scenarios, the problem of determining $n$
is called _Counting problem_. In [31] it is shown how to solve the Counting
problem in at most $n+1$ rounds in a 1-interval-connected network with unique
IDs.

Anonymous systems. The known landscape changes if we consider networks without
IDs, which are called _anonymous systems_. In this model, all processes have
identical initial states, and may only differ by their inputs. In the last
thirty years, a large body of works [7, 13, 14, 15, 23, 42, 45] have
investigated the computational power of anonymous static networks, giving
characterizations of what can be computed in various settings [7, 8]. Studying
anonymous systems is not only important from a theoretical perspective, but
also for their practical relevance. In a highly dynamic system, IDs may not be
guaranteed to be unique due to operational limitations [38], or may compromise
user privacy. Indeed, users may not be willing to be tracked or to disclose
information about their behavior; examples are COVID-19 tracking apps [43],
where a threat to privacy was felt by a large share of the public even if
these apps were assigning a rotating random ID to each user. In fact, an
adversary can easily track the continuous broadcast of a fixed random ID
tracing the movements of a person [4]. Anonymity is also found in insect
colonies and other biological systems [24].

Unique leader. In order to deterministically solve non-trivial problems in
anonymous systems, it is necessary to have some form of initial “asymmetry”
[1, 8, 35, 45]. The most common assumption is the existence of a _leader_ ,
i.e., a single special process that starts in a different and unique initial
state. The presence of a leader is a realistic assumption: examples include a
base station in a mobile network, a gateway in a sensor network, etc. For
these reasons, the computational power of anonymous systems enriched with a
leader has been extensively studied in the classical model of static networks
[23, 41, 46], as well as in population protocols [2, 3, 5, 6, 22].

State of the art. A long series of papers have studied the Counting problem in
anonymous 1-interval-connected networks with a leader [11, 17, 18, 19, 20, 21,
25, 26, 29, 35]. These works have shown better and better upper bounds,
leading to the recent paper [29], which solves the Counting problem in
$O({n^{4+\epsilon}}\log^{3}(n))$ rounds (for $\epsilon>0$). Almost all of
these works share the same basic approach of implementing a mass-distribution
mechanism similar to the local averaging used to solve the average consensus
problem [16, 39, 44]. (In Appendix D we give a comprehensive survey.) We point
out that the mass-distribution approach requires processes to exchange numbers
whose representation size grows at least linearly with the number of rounds.
Thus, all previous works on counting in anonymous 1-interval-connected
networks need messages of size at least $\Omega(n^{4})$.

In spite of the technical sophistication of this line of research, there is
still a striking gap in terms of running time—a multiplicative factor of
$O(n^{3}\log^{3}(n))$—between the best algorithm for anonymous networks and
the best algorithm for networks with unique IDs. The same gap exists with
respect to _static_ anonymous networks, where the Counting problem is known to
be solvable in $2n$ rounds [35]. Given the current state of the art, solving
non-trivial problems in large-scale dynamic networks is still impractical.

###  1.1 Our Contributions

Main results. In this paper, we close the aforementioned gaps by showing that
counting in 1-interval-connected anonymous dynamic networks with a leader is
linear: we give a deterministic algorithm for the Counting problem that
terminates in $3n-2$ rounds (Theorem 4.10), as well as a non-terminating
algorithm that stabilizes on the correct count in $2n-2$ rounds (Theorem 4.4).

We also prove a lower bound of roughly $2n$ rounds, both for terminating and
stabilizing counting algorithms (Theorem 5.2); this is the first non-trivial
lower bound for anonymous networks (better than $n-1$), and it shows that our
stabilizing algorithm is optimal up to a small additive constant.

In addition, our algorithms support network topologies with multiple parallel
links and self-loops (i.e., _multigraphs_ , as opposed to the simple graphs
used in traditional models).

Significance. Our algorithms actually solve a generalized version of the
Counting problem: when processes are assigned inputs, they are able to count
how many processes have each input. Solving such a _Generalized Counting
problem_ allows us to solve a much larger class of problems, called _multi-
aggregation problems_ , in the same number of rounds (Theorem 2.1). On the
other hand, these are the only problems that can be solved deterministically
in anonymous networks (Theorem 5.1).

Thus, we come to an interesting conclusion: In 1-interval-connected anonymous
dynamic networks with a leader, any problem that can be solved
deterministically has a solution in at most $3n-2$ rounds. Our lower bounds
show that there is an overhead to be paid for counting in anonymous dynamic
networks compared to networks with IDs, but the overhead is only linear. This
is much less than what was previously conjectured [27, 29]; in fact, our
results make computations in anonymous and dynamic large-scale networks
possible and efficient in practice.

We remark that the local computation time and the amount of processes’
internal memory required by our algorithms is only polynomial in the size of
the network. Also, like in previous works, processes need to send messages of
polynomial size.

Technique. Our algorithms and lower bounds are based on a novel combinatorial
structure called _history tree_ , which completely represents an anonymous
dynamic network and naturally models the idea that processes can be
distinguished if and only if they have different “histories” (Section 3).
Thanks to the simplicity of our technique, this paper is entirely self-
contained, our proofs are transparent and easy to understand, and our
algorithms are elegant and straightforward to implement.111An implementation
can be found here: https://github.com/viglietta/Dynamic-Networks. The
repository includes a dynamic network simulator that can be used to run tests
and visualize the history trees of custom networks.

We argue that history trees are of independent interest, as they could help in
the study of different network models, as well as networks with specific
restricted dynamics.

##  2 Definitions and Preliminaries

Here we give some informal definitions; the interested reader may find
rigorous ones in Appendix A.

Dynamic network. Our model of computation involves a system of $n$ _anonymous_
processes in a _1-interval-connected_ dynamic network whose topology changes
unpredictably at discrete time units called _rounds_. That is, at round $t\geq
1$, the network’s topology is modeled by a connected undirected multigraph
$G_{t}$ whose edges are called _links_. Processes can send _messages_ through
links and can update their _internal states_ based on the messages they
receive.

Round structure. Each round is subdivided into two phases: in the _message-
passing phase_ , each process broadcasts a message containing (an encoding of)
its internal state through all the links incident to it. After all messages
have been exchanged, the _local-computation phase_ occurs, where each process
updates its own internal state based on a function $\mathcal{A}$ of its
current state and the multiset of messages it has just received. Processes are
_anonymous_ , implying that the function $\mathcal{A}$ is the same for all of
them. We stress that all local computations are deterministic.

Input and output. At round $0$, each process is assigned an _input_ , which is
deterministically converted into the process’ initial internal state.
Furthermore, at every round, each process produces an _output_ , which is a
function of its internal state. Some states are _terminal_ ; once a process
enters a terminal state, it can no longer change it.

Stabilization and termination. A system is said to _stabilize_ if the outputs
of all its processes remain constant from a certain round onward; note that a
process’ internal state may still change even when its output is constant. If,
in addition, all processes reach a terminal state, the system is said to
_terminate_.

Problems. A _problem_ defines a relationship between processes’ inputs and
outputs: an algorithm $\mathcal{A}$ _solves_ a given problem if, whenever the
processes are assigned a certain multiset of $n$ inputs, and all processes
execute $\mathcal{A}$ in their local computations, the system eventually
stabilizes on the correct multiset of $n$ outputs. Note that the same
algorithm $\mathcal{A}$ must work for all $n\geq 1$ (i.e., the system is
unaware of its own size) and regardless of the network’s topology (as long as
it is 1-interval-connected). A stronger notion of solvability requires that
the system not only stabilizes but actually terminates on the correct multiset
of outputs.

Unique leader. A commonly made assumption is the presence of a _unique leader_
in the system. This can be modeled by assuming that each process’ input
includes a _leader flag_ , and an input assignment is valid if and only if
there is exactly one process whose input has the leader flag set.

Multi-aggregation problems. A _multi-aggregation problem_ is a problem where
the output to be computed by each process only depends on the process’ own
input and the multiset of all processes’ inputs. In the special case where all
processes have to compute the same output, we have an _aggregation problem_.
Notable examples of aggregation problems include computing statistical
functions on input numbers, such as sum, average, maximum, median, mode,
variance, etc.

As we will see, the multi-aggregation problems are precisely the problems that
can be solved in 1-interval-connected anonymous dynamic networks with a unique
leader. Specifically, in Section 4 we will show that all multi-aggregation
problems can be solved in a linear number of rounds. On the other hand, in
Section 5 we will prove that no other problem can be solved at all.

Counting problem. An important aggregation problem is the _Generalized
Counting problem_ , where each process must output the multiset of all
processes’ inputs. That is, the system has to count how many processes have
each input. In the special case where all (non-leader) processes have the same
input, this reduces to the _Counting problem_ : determining the size of the
system, $n$.

Completeness. The Generalized Counting problem is _complete_ for the class of
multi-aggregate problems (no matter if the network is connected or has a
unique leader), in the following sense:

######  Theorem 2.1.

If the Generalized Counting problem can be solved (with termination) in $f(n)$
rounds, then every multi-aggregate problem can be solved (with termination) in
$f(n)$ rounds, too.

###### Proof.

Once a process with input $x$ has determined the multiset $\mu$ of all
processes’ inputs, it can immediately compute any function of $(x,\mu)$ within
the same local-computation phase. ∎

##  3 History Trees

We introduce _history trees_ as a natural tool of investigation for anonymous
dynamic networks. An example of a history tree is illustrated in Figure 1, and
a formal definition is found in Appendix B.

Indistinguishable processes. Since processes are anonymous, they can only be
distinguished by their inputs or by the multisets of messages they have
received. This leads to an inductive definition of _indistinguishability_ :
Two processes are indistinguishable at the end of round $0$ if and only if
they have the same input. At the end of round $t\geq 1$, two processes $p$ and
$q$ are indistinguishable if and only if they were indistinguishable at the
end of round $t-1$ and, for every equivalence class $A$ of processes that were
indistinguishable at the end of round $t-1$, both $p$ and $q$ receive an equal
number of (identical) messages from processes in $A$ at round $t$.

Levels of a history tree. A _history tree_ is a structure associated with a
dynamic network. It is an infinite graph whose nodes are subdivided into
_levels_ $L_{-1}$, $L_{0}$, $L_{1}$, $L_{2}$, …, where each node in level
$L_{t}$, with $t\geq 0$, represents an equivalence class of processes that are
indistinguishable at the end of round $t$. The level $L_{-1}$ contains a
unique node $r$, representing all processes in the system. Each node in level
$L_{0}$ has a label indicating the (unique) input of the processes it
represents.

Black and red edges. A history tree has two types of undirected edges; each
edge connects nodes in consecutive levels. The _black edges_ induce an
infinite tree rooted at $r$ and spanning all nodes. A black edge
$\\{v,v^{\prime}\\}$, with $v\in L_{t}$ and $v^{\prime}\in L_{t+1}$, indicates
that the _child node_ $v^{\prime}$ represents a subset of the processes
represented by the _parent node_ $v$.

The _red multiedges_ represent messages. A red edge $\\{v,v^{\prime}\\}$ with
multiplicity $m$, with $v\in L_{t}$ and $v^{\prime}\in L_{t+1}$, indicates
that, at round $t+1$, each process represented by $v^{\prime}$ receives a
total of $m$ (identical) messages from processes represented by $v$.

Anonymity of a node. The _anonymity_ $a(v)$ of a node $v$ of a history tree is
defined as the number of processes represented by $v$. Since the nodes in a
same level represent a partition of all the processes, the sum of their
anonymities must be $n$. Moreover, by the definition of black edges, the
anonymity of a node is equal to the sum of the anonymities of its children.

Observe that the Generalized Counting problem can be rephrased as the problem
of determining the anonymities of all the nodes in $L_{0}$.

Figure 1: The first rounds of a dynamic network with $n=12$ processes and the
corresponding levels of the history tree. The letters L, A, B indicate
processes’ inputs (the process with input L is the leader). At each round, the
network’s links are represented by solid red edges. Sets of indistinguishable
processes are indicated by dashed blue lines and unique labels. The same
labels are also reported in the history tree: each node corresponds to a set
of indistinguishable processes. It should be noted that labels other than L,
A, B are not part of the history tree itself, and have been added for the
reader’s convenience. The dashed red edges in the history tree represent
messages received by processes through the links; the numbers indicate their
multiplicities (when greater than $1$). For example, the edge
$\\{c_{2},b_{4}\\}$ has multiplicity $2$ because, at round 3, each of the two
processes in the class $c_{2}$ receives two identical messages from the
(indistinguishable) processes that were in the class $b_{4}$ in the previous
round. On the other hand, the node labeled $c_{5}$ represents four processes
(i.e., its _anonymity_ is $4$) at round 3; among them, only one receives a
message from $c_{6}$ in the next round. Thus, this process is disambiguated,
which causes the node $c_{5}$ to branch into two nodes: $d_{7}$, with
anonymity $3$, and $d_{8}$, with anonymity $1$. The _view_ of the node labeled
$b_{3}$ is the subgraph of the history tree induced by the nodes with labels
in the set $\\{b_{3},a_{3},a_{5},\mbox{L},\mbox{A},\mbox{B},r\\}$.

History of a process. A _monotonic path_ in the history tree is a sequence of
nodes in distinct levels, such that any two consecutive nodes are connected by
a black or a red edge. We define the _view_ of a node $v$ in the history tree
as the finite subgraph induced by all the nodes spanned by monotonic paths
with endpoints $v$ and $r$. The _history_ of a process $p$ at round $t$ is the
view of the (unique) node in $L_{t}$ that represents a set of processes
containing $p$.

Fundamental theorem. Intuitively, the history of a process at round $t$
contains all the information that the process can use at that round for its
local computations. This intuition is made precise by the following
fundamental theorem (a rigorous proof is found in Section B.3):

######  Theorem 3.1.

The state of a process $p$ at the end of round $t$ is determined by a function
$\mathcal{F}_{\mathcal{A}}$ of the history of $p$ at round $t$. The mapping
$\mathcal{F}_{\mathcal{A}}$ depends entirely on the local algorithm
$\mathcal{A}$ and is independent of $p$.∎

Locally constructing the history. The significance of Theorem 3.1 is that it
allows us to shift our focus from dynamic networks to history trees. As shown
in Section B.4, there is a local algorithm $\mathcal{A}^{\ast}$ that allows
processes to construct and update their history at every round. Thanks to
Theorem 3.1, processes are guaranteed not to lose any information if they
simply execute $\mathcal{A}^{\ast}$, regardless of their goal, and then
compute their outputs as a function of their history. Thus, in the following,
we will assume without loss of generality that a process’ internal state at
every round, as well as all the messages it broadcasts, always coincide with
its history at that round.

##  4 Linear-Time Computation

As discussed at the end of Section 3, the following algorithms assume that all
processes have their current history as their internal state and broadcast
their history through all available links at every round. We will show how to
solve the Generalized Counting problem in such a setting.

###  4.1 Stabilizing Algorithm

In a history tree (or in a view), a node $v$ is said to be _non-branching_ if
it has exactly one child, which we denote as $c(v)$. Recall that the parent-
child relation is determined by black edges only.

A pair of non-branching nodes $(v_{1},v_{2})$ in a history tree is said to be
_exposed_ with multiplicity $(m_{1},m_{2})$ if the red edge
$\\{c(v_{1}),v_{2}\\}$ is present with multiplicity $m_{1}\geq 1$, while the
red edge $\\{c(v_{2}),v_{1}\\}$ has multiplicity $m_{2}\geq 1$ (see Figure 2,
left). Note that $v_{1}$ and $v_{2}$ must be on the same level.

Thanks to the following lemma, if we know the anonymity of a node in an
exposed pair, we can determine the anonymity of the other node. (Recall that
we denote the anonymity of $v$ by $a(v)$.)

######  Lemma 4.1.

If $(v_{1},v_{2})$ is an exposed pair with multiplicity $(m_{1},m_{2})$, then
$a(v_{1})\cdot m_{1}=a(v_{2})\cdot m_{2}$.

###### Proof.

Let $v_{1},v_{2}\in L_{t}$, and let $P_{1}$ and $P_{2}$ be the sets of
processes represented by $v_{1}$ and $v_{2}$, respectively. Since $v_{1}$ is
non-branching, we have $a(c(v_{1}))=a(v_{1})$, and therefore $c(v_{1})$
represents $P_{1}$, as well. Hence, the number of links between $P_{1}$ and
$P_{2}$ in $G_{t+1}$ (counted with their multiplicities) is $a(c(v_{1}))\cdot
m_{1}=a(v_{1})\cdot m_{1}$. By a symmetric argument, this number is equal to
$a(v_{2})\cdot m_{2}$. ∎

It is well known that, in a 1-interval-connected network, any piece of
information can reach all processes in $n-1$ rounds [31]. We can rephrase this
observation in the language of history trees.

######  Lemma 4.2.

Let $P$ be a set of processes in a 1-interval-connected dynamic network of
size $n$, such that $1\leq|P|\leq n-1$, and let $t\geq 0$. Then, at every
round $t^{\prime}\geq t+|P|$, in the history of every process there is a node
at level $L_{t}$ representing at least one process not in $P$.

###### Proof.

Let $Q$ be the complement of $P$ (note that $Q$ is not empty), and let
$Q_{t+i}$ be the set of processes represented by the nodes in $L_{t+i}$ whose
view contains a node in $L_{t}$ representing at least one process in $Q$. We
will prove by induction that $|Q_{t+i}|\geq|Q|+i$ for all $0\leq i\leq|P|$.
The base case holds because $Q_{t}=Q$. The induction step is implied by
$Q_{t+i}\subsetneq Q_{t+i+1}$, which holds for all $0\leq i<|P|$ as long as
$|Q_{t+i}|<n$. Indeed, because $G_{t+i+1}$ is connected, it must contain a
link between a process $p\in Q_{t+i}$ and a process $q\notin Q_{t+i}$. Thus,
the history of $q$ at round $t+i+1$ contains the history of $p$ at round
$t+i$, and so $Q_{t+i}\subsetneq Q_{t+i}\cup\\{q\\}\subseteq Q_{t+i+1}$.

Now, plugging $i:=|P|$, we get $|Q_{t+|P|}|=n$. In other words, the history of
each node in $L_{t+|P|}$ (and hence in subsequent levels) contains a node at
level $L_{t}$ representing a process in $Q$. ∎

######  Corollary 4.3.

In the history tree of a 1-interval-connected dynamic network, every node at
level $L_{t}$ is in the view of every node at level $L_{t^{\prime}}$, for all
$t^{\prime}\geq t+n-1$.

###### Proof.

Let $v\in L_{t}$, and let $P$ be the set of processes not represented by $v$.
If $P$ is empty, then all nodes in $L_{t^{\prime}}$ are descendants of $v$,
and have $v$ in their view. Otherwise, $1\leq|P|\leq n-1$, and Lemma 4.2
implies that $v$ is in the view of all nodes in $L_{t^{\prime}}$. ∎

######  Theorem 4.4.

There is an algorithm that solves the Generalized Counting problem in
1-interval-connected anonymous dynamic networks with a leader and stabilizes
in at most $2n-2$ rounds.

###### Proof.

Let $n>1$, and let $L_{T}$ be the first level of the history tree whose nodes
are all non-branching. Since $|L_{0}|\geq 2$ and $|L_{t-1}|\leq|L_{t}|\leq n$
for all $t\geq 0$, we have $T\leq n-2$ by the pigeonhole principle.

Let $\ell\in L_{T}$ be the node corresponding to the leader; we know that
$a(\ell)=1$. Since $G_{T+1}$ is connected, the exposed pairs of nodes in
$L_{T}$ must form a connected graph on $L_{T}$, as well. Hence, thanks to
Lemma 4.1, any process that has complete knowledge of $L_{T}$ and $L_{T+1}$
can use the information that $a(\ell)=1$ to compute the anonymities of all
nodes in $L_{T}$. In fact, by Corollary 4.3, every process is able to do so by
round $(T+1)+n-1\leq 2n-2$.

The local algorithm for each process is given in Listing 1: Find the first
level in your history whose nodes are all non-branching. If such a level
exists and contains a node corresponding to the leader, assume this is level
$L_{T}$ and compute the anonymities of all its nodes. Then add together the
anonymities of nodes having equal inputs, and give the result as output. Even
if some outputs may be incorrect at first, the whole system stabilizes on the
correct output by round $2n-2$. ∎

If we were to use a strategy such as the one in Listing 1 to devise a
terminating algorithm, we would be bound to fail, as the counterexample in
Section C.1 shows. The problem is that a process has no easy way of knowing
whether the first level in its history whose nodes are all non-branching is
really $L_{T}$, and so it may end up terminating too soon with the wrong
output. To find a correct termination condition, we will have to considerably
develop the theory of history trees.

Figure 2: Left: an _exposed_ pair of nodes. Center: if the anonymities of $u$,
$u_{1}$, $u_{2}$, …, $u_{k}$ are known, then $v$ is _guessable_ by $u$. Right:
if the colored nodes are counted, the blue ones form a _counting cut_ , and
the orange ones define a non-trivial _isle_ with root $s$, where the nodes
with a dot are internal. Listing 1: Algorithm for the Generalized Counting
problem that stabilizes in $2n-2$ rounds

⬇

1# This local algorithm is executed at every round by each process.

2# Input: the current history $\mathcal{V}$ of the process

3# Output: a multiset of inputs received by processes at round $0$

4

5For $t:=0$ to the height of $\mathcal{V}$

6 If level $L_{t}$ does not contain a leader node, return $\emptyset$

7 Assign $a(\ell):=1$, where $\ell\in L_{t}$ is the leader node

8 Assign ${\rm non\\_branching}:={\rm true}$

9 For each node $v\in L_{t}$

10 If $v$ does not have exactly one child in $\mathcal{V}$, assign ${\rm
non\\_branching}:={\rm false}$

11 If $v\neq\ell$, assign $a(v):=0$

12 If ${\rm non\\_branching}$

13 While there is an exposed pair $(v_{1},v_{2})$ in $L_{t}$ with
$a(v_{1})\neq 0$ and $a(v_{2})=0$

14 Let $(m_{1},m_{2})$ be the multiplicity of the exposed pair $(v_{1},v_{2})$

15 Assign $a(v_{2}):=\left\lceil a(v_{1})\cdot m_{1}/m_{2}\right\rceil$

16 For each node $v\in L_{0}$

17 Assign $a(v):=\sum_{v^{\prime}\in L_{t}\text{ descendant of
}v}a(v^{\prime})$

18 Return the multiset $\\{({\rm label}(v),a(v))\mid v\in L_{0}\\}$

Listing 2: Algorithm for the Generalized Counting problem that terminates in
$3n-2$ rounds

⬇

1# This local algorithm is executed at every round by each process.

2# Input: the current history $\mathcal{V}$ of the process

3# Output: either a multiset of inputs received by processes at round $0$

4# or "Unknown"

5

6For each leader node $\ell$ in $\mathcal{V}$

7 Assign $a(\ell):=1$ and mark $\ell$ as counted

8While $\mathcal{V}$ has guessable levels

9 Let $v$ be a guessable non-counted node of smallest depth in $\mathcal{V}$

10 Assign a guess $g(v)$ to $v$ as in Equation 1 and mark $v$ as guessed

11 Let $P_{v}$ be the black path from $v$ to the root $r$ of $\mathcal{V}$

12 If there is a heavy node in $P_{v}$

13 Let $v^{\prime}$ be the heavy node in $P_{v}$ of maximum depth

14 Assign $a(v^{\prime}):=g(v^{\prime})$; mark $v^{\prime}$ as counted and not
guessed

15 If $v^{\prime}$ is the root or a leaf of a non-trivial complete isle $I$

16 For each internal node $w$ of $I$

17 Assign $a(w)=\sum_{w^{\prime}\text{ leaf of }I\text{ and descendant of
}w}a(w^{\prime})$

18 Mark $w$ as counted and not guessed

19Assign $C:=\emptyset$

20For each node $v$ in $\mathcal{V}$ marked as counted

21 Let $P_{v}$ be the black path from $v$ to the root $r$ of $\mathcal{V}$

22 Let $v^{\prime}$ be the counted node in $P_{v}$ of minimum depth

23 Assign $C:=C\cup\\{v^{\prime}\\}$

24If $C$ is not a counting cut of $\mathcal{V}$, return "Unknown"

25Let $L_{t}$ be the level of $\mathcal{V}$ containing the deepest node of $C$

26Let $L_{t^{\prime}}$ be the deepest level of $\mathcal{V}$

27Let $n^{\prime}=\sum_{v\in C}a(v)$

28If $t^{\prime}<t+n^{\prime}$, return "Unknown"

29For each node $v\in L_{0}$

30 Assign $a(v):=\sum_{v^{\prime}\in C\text{ descendant of }v}a(v^{\prime})$

31Return the multiset $\\{({\rm label}(v),a(v))\mid v\in L_{0}\\}$ and enter a
terminal state

###  4.2 Terminating Algorithm

Guessing anonymities. Inspired by Lemma 4.1, we now describe a more
sophisticated way of estimating the anonymity of a node based on known
anonymities (see Figure 2, center). Let $u$ be a node of a history tree, and
assume that the anonymities of all its children $u_{1}$, $u_{2}$, …, $u_{k}$
are known: such a node $u$ is called a _guesser_. If $v$ is not among the
children of $u$ but is at their same level, and the red edge $\\{v,u\\}$ is
present with multiplicity $m\geq 1$, we say that $v$ is _guessable_ by $u$. In
this case, we can make a _guess_ $g(v)$ on the anonymity of $v$:

$g(v)=\left\lceil\frac{a(u_{1})\cdot m_{1}+a(u_{2})\cdot
m_{2}+\dots+a(u_{k})\cdot m_{k}}{m}\right\rceil,$ (1)

where $m_{i}$ is the multiplicity of the red edge $\\{u_{i},v^{\prime}\\}$ for
all $1\leq i\leq k$, and $v^{\prime}$ is the parent of $v$ (possibly,
$m_{i}=0$). Although a guess may be inaccurate, it never underestimates the
anonymity:

######  Lemma 4.5.

If $v$ is guessable, then $g(v)\geq a(v)$. Moreover, if $v$ has no siblings,
$g(v)=a(v)$.

###### Proof.

Let $u,v^{\prime}\in L_{t}$, and let $P_{1}$ and $P_{2}$ be the sets of
processes represented by $u$ and $v^{\prime}$, respectively. By counting the
links between $P_{1}$ and $P_{2}$ in $G_{t+1}$ in two ways, we have
$\sum_{i}a(u_{i})\,m_{i}=\sum_{i}a(v_{i})\,m^{\prime}_{i}$, where the two sums
range over all children of $u$ and $v^{\prime}$, respectively (note that
$v=v_{j}$ for some $j$), and $m^{\prime}_{i}$ is the multiplicity of the red
edge $\\{v_{i},u\\}$ (so, $m=m^{\prime}_{j}$). Our lemma easily follows. ∎

Heavy nodes. Even if a node is guessable, it is not always a good idea to
actually assign it a guess. For reasons that will become apparent in Lemma
4.6, our algorithm will only assign guesses in a _well-spread_ fashion, i.e.,
in such a way that at most one node per level is assigned a guess.

Suppose now that a node $v$ has been assigned a guess. We define its _weight_
$w(v)$ as the number of nodes in the subtree hanging from $v$ that have been
assigned a guess (this includes $v$ itself). Recall that subtrees are
determined by black edges only. We say that $v$ is _heavy_ if $w(v)\geq g(v)$.

######  Lemma 4.6.

In a well-spread assignment of guesses, if $w(v)>a(v)$, then some descendants
of $v$ are heavy (the _descendants_ of $v$ are the nodes in the subtree
hanging from $v$ other than $v$ itself).

###### Proof.

Our proof is by well-founded induction on $w(v)$. Assume for a contradiction
that no descendants of $v$ are heavy. Let $v_{1}$, $v_{2}$, …, $v_{k}$ be the
“immediate” descendants of $v$ that have been assigned guesses. That is, for
all $1\leq i\leq k$, no internal nodes of the black path with endpoints $v$
and $v_{i}$ have been assigned guesses (observe that $k\geq 1$ because, by
assumption, $w(v)>1$).

By the basic properties of history trees, $a(v)\geq\sum_{i}a(v_{i})$. Also,
the induction hypothesis implies that $w(v_{i})\leq a(v_{i})$ for all $1\leq
i\leq k$, or else one of the $v_{i}$’s would have a heavy descendant.
Therefore, $w(v)-1=\sum_{i}w(v_{i})\leq\sum_{i}a(v_{i})\leq a(v)\leq w(v)-1$.
It follows that $w(v_{i})=a(v_{i})$ and $a(v)=\sum_{i}a(v_{i})$.

Let $v_{d}$ be the deepest of the $v_{i}$’s, which is unique, since the
assignment of guesses is well spread. Note that $v_{d}$ has no siblings at
all, otherwise we would have $a(v)>\sum_{i}a(v_{i})$. Due to Lemma 4.5, we
conclude that $g(v_{d})=a(v_{d})=w(v_{d})$, and so $v_{d}$ is heavy. ∎

Correct guesses. We say that a node $v$ has a _correct_ guess if $v$ has been
assigned a guess and $g(v)=a(v)$. The next lemma gives a criterion to
determine if a guess is correct.

######  Lemma 4.7.

In a well-spread assignment of guesses, if a node $v$ is heavy and no
descendant of $v$ is heavy, then $v$ has a correct guess.

###### Proof.

Because $v$ is heavy, $g(v)\leq w(v)$. Since $v$ has no heavy descendants,
Lemma 4.6 implies $w(v)\leq a(v)$. Also, by Lemma 4.5, $a(v)\leq g(v)$. We
conclude that $g(v)\leq w(v)\leq a(v)\leq g(v)$, and therefore $g(v)=a(v)$. ∎

When the criterion in Lemma 4.7 applies to a node $v$, we say that $v$ has
been _counted_. So, counted nodes are nodes that have been assigned a guess,
which was then confirmed to be correct.

Cuts and isles. Fix a view $\mathcal{V}$ of a history tree $\mathcal{H}$. A
set of nodes $C$ in $\mathcal{V}$ is said to be a _cut_ for a node $v\notin C$
of $\mathcal{V}$ if two conditions hold: (i) for every leaf $v^{\prime}$ of
$\mathcal{V}$ that lies in the subtree hanging from $v$, the black path from
$v$ to $v^{\prime}$ contains a node of $C$, and (ii) no proper subset of $C$
satisfies condition (i). A cut for the root $r$ whose nodes are all counted is
said to be a _counting cut_ (see Figure 2, right).

Let $s$ be a counted node in $\mathcal{V}$, and let $F$ be a cut for $v$ whose
nodes are all counted. Then, the set of nodes spanned by the black paths from
$s$ to the nodes of $F$ is called _isle_ ; $s$ is the _root_ of the isle,
while each node in $F$ is a _leaf_ of the isle (see Figure 2, right). The
nodes in an isle other than the root and the leaves are called _internal_. An
isle is said to be _trivial_ if it has no internal nodes.

If $s$ is an isle’s root and $F$ is its set of leaves, we have
$a(s)\geq\sum_{v\in F}a(v)$, because $s$ may have some descendants in the
history tree $\mathcal{H}$ that do not appear in the view $\mathcal{V}$. If
equality holds, then the isle is said to be _complete_ ; in this case, we can
easily compute the anonymities of all the internal nodes by adding up
anonymities starting from the nodes in $F$ and working our way up to $s$.

Algorithm overview. Our counting algorithm repeatedly assigns guesses to nodes
based on known anonymities (starting from the nodes corresponding to the
leader). Eventually some nodes become heavy, and the criterion in Lemma 4.7
causes the deepest of them to become counted. In turn, counted nodes
eventually form isles; the internal nodes of complete isles are marked as
counted, which gives rise to more guessers, and so on. In the end, if a
counting cut has been created, a simple condition determines whether the
anonymities of its nodes add up to the correct count, $n$.

Algorithm details. Our complete counting algorithm is found in Listing 2. The
algorithm takes as input a view $\mathcal{V}$ (which, we recall, is the
history of a process) and uses flags to mark nodes as “guessed” or “counted”;
initially, no node is marked. Thanks to these flags, we can check if a node
$u\in\mathcal{V}$ is a guesser: let $u_{1}$, $u_{2}$, …, $u_{k}$ be the
children of $u$ that are also in $\mathcal{V}$ (recall that a view does not
contain all nodes of a history tree); $u$ is a _guesser_ if and only if it is
marked as counted, all the $u_{i}$’s are marked as counted, and
$a(u)=\sum_{i}a(u_{i})$.

The algorithm will ensure that nodes marked as guessed are well-spread at all
times; if a level of $\mathcal{V}$ contains a guessed node, it is said to be
_locked_. A level $L_{t}$ is _guessable_ if it is not locked and has a non-
counted node $v$ that is guessable, i.e., there is a guesser $u$ in $L_{t-1}$
and the red edge $\\{v,u\\}$ is present in $\mathcal{V}$ with positive
multiplicity.

The algorithm starts by assigning an anonymity of $1$ to all leader nodes,
marking them as counted. Then, as long as there are guessable levels, it keeps
assigning guesses to non-counted nodes. When a guess is made on a node $v$,
some nodes in the path from $v$ to the root may become heavy; if so, the
algorithm marks the deepest heavy node $v^{\prime}$ as counted. Furthermore,
if the newly counted node $v^{\prime}$ is the root or a leaf of a complete
isle $I$, then the anonymities of all the internal nodes of $I$ are
determined, and such nodes are marked as counted (this also unlocks their
levels if such nodes were marked as guessed).

Finally, when there are no more guessable levels, the algorithm checks if the
termination condition is satisfied, as follows. Each counting cut yields an
estimate of $n$, which is given by the sum of the anonymities of its nodes.
The terminating condition is satisfied if and only if there is a counting cut
$C$ whose total anonymity $n^{\prime}$ is not greater than the difference
between the current round $t^{\prime}$ and the round $t$ corresponding to the
deepest node of $C$ (note that $t^{\prime}$ can be inferred from the height of
the view $\mathcal{V}$). If so, $n^{\prime}$ is guaranteed to be equal to the
correct number of processes $n$, and the anonymities of the nodes in $L_{0}$
can be easily computed from $C$.

Invariants. We argue that the above algorithm maintains some _invariants_ ,
i.e., conditions that are satisfied every time Line 9 is reached. Namely, (i)
the nodes marked as guessed are well spread, (ii) there are no heavy nodes,
and (iii) all complete isles are trivial.

These can be verified by induction: (i) the algorithm never makes a guess in a
locked level; (ii) as soon as a new guess in Line 10 creates some heavy nodes,
the deepest one becomes counted (Line 14), making all other nodes non-heavy
(in Lines 16–18, weights may only decrease, and no heavy nodes are created);
(iii) as soon as a complete isle $I$ is created due to a node $v^{\prime}$
being marked as counted in Line 14, $I$ is immediately reduced to a set of
trivial isles (Lines 16–18).

The invariants also imply that Lines 10–14 are correct: if no nodes are heavy
to begin with, the new guessed node $v$ may create heavy nodes only on the
black path from $v$ to $r$. Thus, the first heavy node along this path has a
correct guess due to Lemma 4.7. Furthermore, since the anonymities assigned in
Line 14 are correct, then so are the ones assigned in Line 17.

Termination condition. We will now prove that Lines 19–31 are correct: the
algorithm indeed gives the correct output if the termination condition is met.
We already know that the anonymities computed for the nodes of the counting
cut $C$ are correct, and hence we only have to prove that the set $P$ of
processes represented by the nodes of $C$ includes all processes. Assume the
contrary; Lemma 4.2 implies that, if $t^{\prime}\geq t+|P|=t+n^{\prime}$,
there is a node $z\in L_{t}$ representing some process not in $P$. Thus, the
black path from $z$ to the root $r$ does not contain any node of $C$,
contradicting the fact that $C$ is a counting cut whose deepest node is in
$L_{t}$. So, the termination condition is correct.

Running time. We have proved that the algorithm is correct; we will now study
its running time.

######  Lemma 4.8.

Whenever Line 9 is reached, at most $n-1$ levels are locked.

###### Proof.

We will prove that, if the subtree hanging from a node $v$ of $\mathcal{V}$
contains more than $a(v)$ guessed nodes, then it contains a guessed node
$v^{\prime}$ such that $w(v^{\prime})>a(v^{\prime})$. The proof is by well-
founded induction based on the subtree relation in $\mathcal{V}$. If $v$ is
guessed, then we can take $v^{\prime}=v$. Otherwise, by the pigeonhole
principle, $v$ has at least one child $u$ whose hanging subtree contains more
than $a(u)$ guessed nodes. Thus, $v^{\prime}$ is found in this subtree by the
induction hypothesis.

Assume for a contradiction that at least $n$ levels of $\mathcal{V}$ are
locked; hence, $\mathcal{V}$ contains at least $n$ guessed nodes. None of the
nodes representing the leader is ever guessed, because all of them are marked
as counted in Lines 6–7. Hence, all of the guessed nodes must be in the
subtrees hanging from the nodes in $L_{0}$ representing non-leader nodes,
whose total anonymity is $n-1$. Thus, by the pigeonhole principle, the subtree
of one such node $v\in L_{0}$ contains more than $a(v)$ guessed nodes. The
node $v$ must be in $\mathcal{V}$, and therefore the subtree hanging from $v$
contains a guessed node $v^{\prime}$ such that $w(v^{\prime})>a(v^{\prime})$.

Since the algorithm’s invariant (i) holds, we can apply Lemma 4.6 to
$v^{\prime}$, which implies that there exist heavy nodes. In turn, this
contradicts invariant (ii). We conclude that at most $n-1$ levels are locked.
∎

######  Lemma 4.9.

Assume that all the levels of the history tree up to $L_{t}$ are entirely
contained in the view $\mathcal{V}$. Then, whenever Line 9 is reached and a
counting cut has not been created yet, there are at most $n-2$ levels in the
range from $L_{1}$ to $L_{t}$ that lack a guessable non-counted node.

###### Proof.

Lines 6–7 create guessers in every level from $L_{0}$ to $L_{t-1}$ (these are
the nodes representing the leader); hence, these levels must have a non-empty
set of guessers at all times. Consider any level $L_{i}$ with $1\leq i\leq t$
such that all the guessable nodes in $L_{i}$ are already counted. Let $S$ be
the set of guessers in $L_{i-1}$; note that not all nodes in $L_{i-1}$ are
guessers, or else they would give rise to a counting cut. The network is
1-interval-connected, so there is a red edge $\\{u,v\\}$ (with positive
multiplicity) such that $u\in S$ and the parent of $v$ is not in $S$. By
definition, the node $v$ is guessable; therefore, it is counted. Also, since
the parent of $v$ is not a guesser, $v$ must have a non-counted parent or a
non-counted sibling; note that such a non-counted node is in $\mathcal{V}$.

We have proved that every level (up to $L_{t}$) lacking a guessable non-
counted node contains a counted node $v$ having a parent or a sibling that is
not counted: we call such a node $v$ a _bad_ node. To conclude the proof, it
suffices to show that there are at most $n-2$ bad nodes up to $L_{t}$.

We will prove by induction that, if a subtree $\mathcal{W}$ of $\mathcal{V}$
contains the root $r$, no counting cuts, and no non-trivial isles, then
$\mathcal{W}$ contains at most $f-1$ bad nodes, where $f$ is the number of
leaves of $\mathcal{W}$ not representing the leader. The base case is $f=1$,
which holds because any counted non-leader node in $\mathcal{W}$ gives rise to
a counting cut. For the induction step, let $v$ be a bad node of maximum depth
in $\mathcal{W}$. Let $(v_{1},v_{2},\dots,v_{k})$ be the black path from
$v_{1}=v$ to the root $v_{k}=r$, and let $1<i\leq k$ be the smallest index
such that $v_{i}$ has more than one child in $\mathcal{W}$ ($i$ must exist,
because $v_{k}$ branches into leader and non-leader nodes). Let
$\mathcal{W}^{\prime}$ be the tree obtained by deleting the black edge
$\\{v_{i-1},v_{i}\\}$ from $\mathcal{W}$, as well as the subtree hanging from
it. Notice that the induction hypothesis applies to $\mathcal{W}^{\prime}$:
since $v_{1}$ is counted, and none of the nodes $v_{2}$, …, $v_{i-1}$ are
branching, the removal of $\\{v_{i-1},v_{i}\\}$ does not create counting cuts
or non-trivial isles. Also, $v_{2}$ is not counted (unless perhaps
$v_{2}=v_{i}$), because $v_{1}$ is bad. Furthermore, none of the nodes
$v_{3}$, …, $v_{i-1}$ is counted, or else $v_{2}$ would be an internal node of
a (non-trivial) isle. Therefore, $\mathcal{W}^{\prime}$ has exactly one less
bad node than $\mathcal{W}$ and one less leaf; the induction hypothesis now
implies that $\mathcal{W}$ contains at most $f-1$ bad nodes.

Observe that the subtree $\mathcal{V}^{\prime}$ of $\mathcal{V}$ formed by all
levels up to $L_{t}$ satisfies all of the above conditions, as it contains the
root $r$ and has no counting cuts, because a counting cut for
$\mathcal{V}^{\prime}$ would be a counting cut for $\mathcal{V}$, as well.
Also, invariant (iii) ensures that $\mathcal{V}^{\prime}$ contains no non-
trivial complete isles. However, since the levels up to $L_{t}$ are contained
in $\mathcal{V}^{\prime}$, all isles in $\mathcal{V}^{\prime}$ are complete,
and thus must be trivial. We conclude that, if $\mathcal{V}^{\prime}$ has $f$
non-leader leaves, it contains at most $f-1$ bad nodes. Since the non-leader
leaves of $\mathcal{V}$ induce a partition of the $n-1$ non-leader processes,
we have $f\leq n-1$, implying that the number of bad nodes up to $L_{t}$ is at
most $n-2$. ∎

######  Theorem 4.10.

There is an algorithm that solves the Generalized Counting problem in
1-interval-connected anonymous dynamic networks with a leader and terminates
in at most $3n-2$ rounds.

###### Proof.

It suffices to prove that, if a process $p$ executes the above algorithm at
round $t^{\prime}=3n-2$, it terminates. By Corollary 4.3, the levels of the
history tree up to $L_{2n-1}$ completely appear in $p$’s history. Due to
Lemmas 4.8 and 4.9, as long as a counting cut has not been created, at least
one level between $L_{1}$ and $L_{2n-2}$ is guessable (because at most $n-1$
levels are locked and at most $n-2$ levels lack a guessable non-counted node).
Hence, when Line 19 is reached, a counting cut $C$ has been found whose
deepest node is in $L_{t}$, with $t\leq 2n-2$. The level $L_{t}$ is completely
contained in $p$’s history, and therefore $n^{\prime}=\sum_{v\in C}a(v)=n$.
Thus, $t^{\prime}=3n-2\geq t+n^{\prime}$, and $p$ terminates. ∎

Our analysis of the algorithm is tight: In Section C.2, we will show that
there are 1-interval-connected networks where the algorithm terminates in
exactly $3n-3$ rounds.

##  5 Negative Results

Unsolvable Problems. We will now prove that the multi-aggregation problems
introduced in Section 2 are the only problems that can be solved
deterministically in anonymous networks.

######  Theorem 5.1.

No problem other than the multi-aggregation problems can be solved
deterministically, even when restricted to simple connected static networks
with a unique leader.

###### Proof.

Let us consider the (static) network whose topology at round $t$ is the
complete graph $G_{t}=K_{n}$, i.e., each process receives messages from all
other processes at every round. We can prove by induction that all nodes of
the history tree other than the root have exactly one child. This is because
any two processes with the same input always receive equal multisets of
messages, and are therefore always indistinguishable. Thus, the history tree
is completely determined by the multiset $\mu$ of all processes’ inputs;
moreover, a process’ history at any given round only depends on the process’
own input and on $\mu$. By Theorem 3.1, this is enough to conclude that if a
process’ output stabilizes, that output must be a function of the process’ own
input and of $\mu$, which is the defining condition of a multi-aggregation
problem. ∎

Lower Bound. We now prove a lower bound of roughly $2n$ rounds on the Counting
problem. In Section C.3, we will provide additional (albeit weaker) lower
bounds for several other problems.

We first introduce a family of 1-interval-connected dynamic networks. For any
$n\geq 1$, we consider the dynamic network $\mathcal{G}_{n}$ whose topology at
round $t$ is the graph $G^{(n)}_{t}$ defined on the system
$\\{p_{1},p_{2},\dots,p_{n}\\}$ as follows. If $t\geq n-2$, then $G^{(n)}_{t}$
is the path graph $P_{n}$ spanning all processes $p_{1}$, $p_{2}$, …, $p_{n}$
in order. If $1\leq t\leq n-3$, then $G^{(n)}_{t}$ is $P_{n}$ with the
addition of the single edge $\\{p_{t+1},p_{n}\\}$. We assume $p_{1}$ to be the
leader and all other processes to have the same input.

######  Theorem 5.2.

No deterministic algorithm can solve the Counting problem in less than $2n-6$
rounds, even in a simple 1-interval-connected dynamic network, and even if
there is a unique leader in the system. If termination is required, the bound
improves to $2n-4$ rounds.222A slightly better bound can be obtained if we
allow networks with double links. If we double the edge $\\{p_{n-1},p_{n}\\}$
in $G^{(n)}_{n-2}$ and we add a double self-loop on $p_{n}$ in $G^{(n)}_{t}$
for all $t\geq n-1$, we obtain a lower bound of $2n-3$ rounds for
stabilization and $2n-1$ rounds for termination.

###### Proof.

Let us consider the network $\mathcal{G}_{n}$ as defined above. It is
straightforward to prove by induction that, at round $t\leq n-3$, the process
$p_{t+1}$ gets disambiguated, while all processes $p_{t+2}$, $p_{t+3}$, …,
$p_{n}$ are still indistinguishable. So, the history tree of $\mathcal{G}_{n}$
has a very regular structure, which is illustrated in Figures 3 and 4. By
comparing the history trees of $\mathcal{G}_{n}$ and $\mathcal{G}_{n+1}$, we
see that the leaders of the two systems have identical histories from round
$1$ up to round $2n-5$. Thus, by Theorem 3.1, both leaders must have equal
internal states and give equal outputs up to round $2n-5$.

It follows that, if the leader of $\mathcal{G}_{n}$ were to output the number
$n$ and terminate in less than $2n-4$ rounds, then the leader of
$\mathcal{G}_{n+1}$ would do the same, producing the incorrect output $n$
instead of $n+1$. Assume now that the leaders of $\mathcal{G}_{n}$ and
$\mathcal{G}_{n+1}$ could stabilize on the correct output in less than
$f(n)=2n-6$ and $f(n+1)=2(n+1)-6=2n-4$ rounds, respectively. Then, at round
$2n-5$, the two leaders would output $n$ and $n+1$ respectively, contradicting
the fact that they should give the same output. ∎

Acknowledgments. The authors would like to thank Gregory Schwartzman for
useful comments.

##  6 Conclusion

We have presented an algorithm for the Generalized Counting problem that
terminates in $3n-2$ rounds, which allows the linear-time computation of all
deterministically computable functions in 1-interval-connected anonymous
dynamic networks with a leader.

We also proved a lower bound of roughly $2n$ rounds for the Counting problem,
both for terminating and for stabilizing algorithms, and we gave a stabilizing
algorithm for Generalized Counting that matches the lower bound (up to a small
additive constant). Determining whether the $2n$ lower bound is tight for
terminating algorithms is left as an open problem.

We introduced the novel concept of _history tree_ as our main investigation
technique. History trees are a powerful tool that completely and naturally
captures the concept of symmetry in anonymous dynamic networks. We have
demonstrated the effectiveness of our methods by optimally solving a wide
class of fundamental problems, and we argue that our technique can be used in
similar settings, such as the case with multiple leaders, as well as to obtain
better bounds for networks with special topologies or randomly generated
networks.

Figure 3: The first rounds of the dynamic network $\mathcal{G}_{n}$ used in
Theorem 5.2 (left) and the corresponding levels of its history tree (right),
where $n=6$; the process in blue is the leader. The white nodes and the dashed
edges in the history tree are not in the history of the leader at round $7$.
The labels $p_{1}$, …, $p_{6}$ have been added for the reader’s convenience,
and mark the processes that get disambiguated, as well as their corresponding
nodes of the history tree, which have anonymity $1$. Figure 4: The first
rounds of the dynamic network $\mathcal{G}_{n+1}$ with $n=6$. Observe that the
history of the leader at round $7$ is identical to the history highlighted in
Figure 3. The intuitive reason is that, from round $1$ to round $n-3$, both
networks have a cycle whose processes are all indistinguishable (and are
therefore represented by a single node in the history tree), except for the
one process with degree $3$. Thus, the history trees of $\mathcal{G}_{n}$ and
$\mathcal{G}_{n+1}$ are identical up to level $n-3$. After that, the two
networks get disambiguated, but this information takes another $n-3$ rounds to
reach the leader. Therefore, if the leader of $\mathcal{G}_{n}$ and the leader
of $\mathcal{G}_{n+1}$ execute the same algorithm, they must have the same
internal state up to round $2n-5$, due to Theorem 3.1. In particular, they
cannot give different outputs up to that round, which leads to our lower
bounds on stabilization and termination for the Counting problem.

APPENDIX

##  Appendix A Formal Model Definition and Basic Results

A _multiset_ on an _underlying set_ $X$ is a function $\mu\colon
X\to\mathbb{N}$. The non-negative integer $\mu(x)$ is the _multiplicity_ of
$x\in X$, and specifies how many _copies_ of each element of $X$ are in the
multiset. The set of all multisets on the underlying set $X$ is denoted as
$\mathcal{M}_{X}$.

###  A.1 Model of Computation

A _dynamic network_ is an infinite sequence $\mathcal{G}=(G_{i})_{i\geq 1}$,
where $G_{i}=(V,E_{i})$ is an undirected multigraph, i.e., $E_{i}$ is a
multiset of unordered pairs of elements of $V$. In this context, the set
$V=\\{1,2,\dots,n\\}$ is called _system_ , and its $n\geq 1$ elements are the
_processes_. The elements of the multiset $E_{i}$ are called _links_ ; note
that we allow any number of “parallel links” between two processes.333In the
dynamic networks literature, $G_{i}$ is typically assumed to be a simple
graph, as at most one link between the same two processes is allowed. However,
our results hold more generally for multigraphs.

The standard model of computation for systems of processes specifies the
following _computation parameters_ :

  * •

three sets $\mathcal{I}$, $\mathcal{O}$, $\mathcal{S}$, representing the
possible _inputs_ , _outputs_ , and _internal states_ for a process,
respectively;

  * •

A partition of $\mathcal{S}$ into two subsets $\mathcal{S}_{T}$ and
$\mathcal{S}_{N}$, representing the _terminal_ and _non-terminal_ states,
respectively;

  * •

an _input map_ $\iota\colon\mathcal{I}\to\mathcal{S}$, where $\iota(x)$
represents the initial state of a process whose input is $x$;

  * •

an _output map_ $\omega\colon\mathcal{S}_{T}\to\mathcal{O}$, where $\omega(s)$
represents the output of a process in a terminal state $s$;

  * •

a function
$\mathcal{A}\colon\mathcal{S}_{N}\times\mathcal{M}_{\mathcal{S}}\to\mathcal{S}$,
representing a _deterministic algorithm_ for local computations. The algorithm
takes as input the (non-terminal) state of a process $p$, as well as the
multiset of states of all processes linked to $p$, and it outputs the new
state for $p$.

Given the above parameters and a dynamic network $\mathcal{G}=(G_{i})_{i\geq
1}$, the computation proceeds as follows. The system $V$ is assigned an
_input_ in the form of a function $\lambda\colon V\to\mathcal{I}$. Time is
discretized into units called _rounds_ $r_{1}$, $r_{2}$, $r_{3}$, etc.; the
multigraph $G_{i}$ describes the links that are present at round $r_{i}$, and
is called the _topology_ of the network at round $r_{i}$.

Each process in the system updates its own state at the end of every round. We
denote by $\sigma_{i}(p)\in\mathcal{S}$ the state of process $p\in V$ after
round $r_{i}$, for $i\geq 1$. Moreover, we define the _initial state_ of $p$
as $\sigma_{0}(p)=\iota(\lambda(p))$ (we could say that each process is
assigned its initial state at “round $r_{0}$”).

During round $r_{i}$, each process $p\in V$ _broadcasts_ its state to all its
neighbors in $G_{i}$; then, $p$ receives the multiset $M_{i}(p)$ of states of
all its neighbors (one state per incident link in $E_{i}$).444In a slightly
different model, a process does not necessarily broadcast its entire state,
but a _message_ , which in turn is computed as a function of the internal
state. Finally, if $p$’s state is non-terminal, it computes its next state
based on its current state and $M_{i}(p)$. In formulas, if
$\sigma_{i-1}(p)\in\mathcal{S}_{T}$, then $\sigma_{i}(p)=\sigma_{i-1}(p)$.
Otherwise, $\sigma_{i}(p)=\mathcal{A}(\sigma_{i-1}(p),M_{i}(p))$, where
$M_{i}(p)$ is defined as

$M_{i}(p)\colon\mathcal{S}\to\mathbb{N}\quad\mbox{such
that}\quad\mathcal{S}\ni s\mapsto\sum_{\begin{subarray}{c}q\in V\\\
\sigma_{i-1}(q)=s\end{subarray}}E_{i}(\\{p,q\\}).$

Note that processes are _anonymous_ : they are initially identical and
indistinguishable except for their input, and they all update their internal
states by executing the same deterministic algorithm $\mathcal{A}$.

Once all processes in $V$ are in a terminal state, the system’s _output_ is
defined as the function $\zeta\colon V\to\mathcal{O}$ such that
$\zeta(p)=\omega(\sigma_{t}(p))$. If this happens for the first time after
round $r_{t}$, we say that the execution _terminates_ in $t$ rounds.

Given an input set $\mathcal{I}$ and an output set $\mathcal{O}$, a _problem_
on $(\mathcal{I},\mathcal{O})$ is a sequence of functions $P=(\pi_{n})_{n\geq
1}$, where $\pi_{n}$ maps every function
$\lambda\colon\\{1,2,\dots,n\\}\to\mathcal{I}$ to a function
$\zeta\colon\\{1,2,\dots,n\\}\to\mathcal{O}$. Essentially, a problem
prescribes a relationship between inputs and outputs: whenever a system of $n$
processes is assigned a certain input $\lambda$, it must eventually terminate
with the output $\zeta=\pi_{n}(\lambda)$. We denote the set of all problems on
$(\mathcal{I},\mathcal{O})$ as $\mathcal{P}(\mathcal{I},\mathcal{O})$.

We say that a problem $P=(\pi_{n})_{n\geq
1}\in\mathcal{P}(\mathcal{I},\mathcal{O})$ is _solvable in $f(n)$ rounds_ if
there exists computation parameters (i.e., an algorithm $\mathcal{A}$, as well
as a set of states $\mathcal{S}=\mathcal{S}_{N}\cup\mathcal{S}_{T}$, an input
map $\iota$, and an output map $\omega$) such that, whenever a system
$V=\\{1,2,\dots,n\\}$ of $n$ processes is given an input $\lambda\colon
V\to\mathcal{I}$ and carries out its computation on a dynamic network
$\mathcal{G}$ as described above, it terminates in at most $f(n)$ rounds and
outputs $\pi_{n}(\lambda)$, regardless of the topology of $\mathcal{G}$. Note
that the algorithm $\mathcal{A}$ must be the same for every $n$, i.e., it is
_uniform_ ; in other words, the system is unaware of its own size.

A weaker notion of solvability involves _stabilization_ instead of
termination. Here, the processes are only required to output
$\pi_{n}(\lambda)$ starting at round $f(n)$ and at all subsequent rounds,
without necessarily reaching a terminal state.

Since only trivial problems can be solved if no restrictions are made on the
topology of the dynamic network $\mathcal{G}$ (think of a dynamic network with
no links at all), it is customary to require that the dynamic network be
_1-interval-connected_. That is, if $\mathcal{G}=(G_{i})_{i\geq 1}$, we assume
that $G_{i}$ is a connected multigraph for all $i\geq 1$.

Another assumption that is often made about the system is the presence of a
_unique leader_ among the processes. That is, the input set $\mathcal{I}$ is
of the form $\mathcal{I}=\\{L,N\\}\times\mathcal{I}^{\prime}$, and an input
assignment $\lambda\colon V\to\mathcal{I}$ is valid if and only if there is
exactly one process $p\in V$, the _leader_ , such that $\lambda(p)=(L,x)$ for
some $x\in\mathcal{I}^{\prime}$ (thus, all non-leader processes have an input
of the form $(N,x)$).

###  A.2 Multi-Aggregation Problems

In this section we will define an important class of problems in
$\mathcal{P}(\mathcal{I},\mathcal{O})$, the _multi-aggregation problems_. As
we will see, these are precisely the problems that can be solved in
1-interval-connected anonymous dynamic networks with a unique leader.

Given a system $V$ and an input assignment $\lambda\colon V\to\mathcal{I}$, we
define the _inventory_ of $\lambda$ as the function
$\mu_{\lambda}\colon\mathcal{I}\to\mathbb{N}$ which counts the processes that
are assigned each given input. Formally, $\mu_{\lambda}$ is the multiset on
$\mathcal{I}$ such that $\mu_{\lambda}(x)=|\lambda^{-1}(x)|$ for all
$x\in\mathcal{I}$.

A problem $P\in\mathcal{P}(\mathcal{I},\mathcal{O})$ is said to be a _multi-
aggregation problem_ if the output to be computed by each process only depends
on the process’ own input and the inventory of all processes’ inputs.
Formally, $P=(\pi_{n})_{n\geq 1}$ is a multi-aggregation problem if there is a
function $\psi\colon\mathcal{I}\times\mathcal{M}_{\mathcal{I}}\to\mathcal{O}$,
called _signature function_ , such that every input assignment
$\lambda\colon\\{1,2,\dots,n\\}\to\mathcal{I}$ is mapped by $\pi_{n}$ to the
output $\zeta\colon\\{1,2,\dots,n\\}\to\mathcal{O}$ where
$\zeta(p)=\psi(\lambda(p),\mu_{\lambda})$.

###  A.3 Counting Problem

If the signature function $\psi(x,\mu)$ of a multi-aggregation problem
$P\in\mathcal{P}(\mathcal{I},\mathcal{O})$ does not depend on the argument
$x$, then $P$ is simply said to be an _aggregation problem_. Thus, all
aggregation problems are _consensus problems_ , where all processes must
terminate with the same output. Notable examples of aggregation problems in
$\mathcal{P}(\mathbb{R},\mathbb{R})$ include computing statistical functions
on the input values, such as sum, average, maximum, median, mode, variance,
etc.

The _Counting Problem_ $C_{\mathcal{I}}$ is the aggregation problem in
$\mathcal{P}(\mathcal{I},\mathcal{M}_{\mathcal{I}})$ whose signature function
is $\psi(x,\mu)=\mu$. That is, all processes must determine the inventory of
their input assignment $\lambda$, i.e., count the number of processes that
have each input. If all inputs are the same (or, in the presence of a leader,
if $\mathcal{I}=\\{L,N\\}$), the Counting Problem reduces to determining the
total number of processes in the system, $n$.

The Counting Problem is _complete_ for the class of multi-aggregation
problems, in the sense that solving it efficiently implies solving any other
multi-aggregation problem efficiently (actually, with no overhead at all). The
following theorem makes this observation precise.

######  Theorem A.1.

For every input set $\mathcal{I}$ and output set $\mathcal{O}$, if the
Counting Problem $C_{\mathcal{I}}$ is solvable in $f(n)$ rounds, then every
multi-aggregation problem in $\mathcal{P}(\mathcal{I},\mathcal{O})$ is
solvable in $f(n)$ rounds, as well.

###### Proof.

The proof is essentially the same whether the requirement is termination or
stabilization. For brevity, we only discuss termination.

Let $\mathcal{A}$ be an algorithm that solves $C_{\mathcal{I}}$ in $f(n)$
rounds with the computation parameters
$\mathcal{S}=\mathcal{S}_{N}\cup\mathcal{S}_{T}$, $\iota$, $\omega$ as defined
in Section A.1. We will show how to solve $P$ by modifying $\mathcal{A}$ and
the above parameters.

The idea is that each process should execute $\mathcal{A}$ while remembering
its own input $x$. Once it has computed the inventory $\mu_{\lambda}$ of the
system’s input assignment, it immediately uses $x$ and $\mu_{\lambda}$ to
compute the signature function of $P$.

We define the set of internal states for $P$ as
$\mathcal{S}^{\prime}=\mathcal{S}\times\mathcal{I}$, with non-terminal states
$\mathcal{S}^{\prime}_{N}=\mathcal{S}_{N}\times\mathcal{I}$. The new input map
is $\iota^{\prime}(x)=(\iota(x),x)\in\mathcal{S}^{\prime}$ for all
$x\in\mathcal{I}$. The algorithm
$\mathcal{A}^{\prime}\colon\mathcal{S}^{\prime}_{N}\times\mathcal{M}_{\mathcal{S}^{\prime}}\to\mathcal{S}^{\prime}$
is defined as
$\mathcal{A}^{\prime}((s,x),\mu)=(\mathcal{A}(s,\mu^{\prime}),x)$, where
$\mu^{\prime}$ is defined as

$\mu^{\prime}\colon\mathcal{S}\to\mathbb{N}\quad\mbox{such
that}\quad\mathcal{S}\ni s\mapsto\sum_{x\in\mathcal{I}}\mu((s,x)).$

Finally, we define the output map as
$\omega^{\prime}((s,x))=\psi(x,\omega(s))$, where
$\psi\colon\mathcal{I}\times\mathcal{M}_{\mathcal{I}}\to\mathcal{O}$ is the
signature function of $P$.

Since $\mathcal{A}$ solves the Counting Problem, when a system $V$ of $n$
processes is assigned an input $\lambda$ and executes $\mathcal{A}$ on a
network $\mathcal{G}$, within $f(n)$ rounds each process $p\in V$ reaches a
terminal state $s\in\mathcal{S}_{T}$ such that $\omega(s)=\mu_{\lambda}$.
Therefore, if the system executes $\mathcal{A}^{\prime}$ on the same input and
in the same network, the process $p$ reaches the terminal state
$(s,\lambda(p))\in\mathcal{S}^{\prime}$ in the same number of rounds. Thus,
$p$ gives the output
$\omega^{\prime}((s,\lambda(p)))=\psi(\lambda(p),\omega(s))=\psi(\lambda(p),\mu_{\lambda})$,
as required by the problem $P$. ∎

We remark that Theorem A.1 makes no assumption on the dynamic network’s
topology or the presence of a leader.

##  Appendix B Formal Definition of History Trees and Basic Properties

###  B.1 Abstract Structure of a History Tree

A _history tree_ on an input set $\mathcal{I}$ is a quintuplet
$\mathcal{H}=(H,u,B,R,\ell)$ such that:666Note that, in Figure 1, the root
node $u$ has been renamed $r$ to match the notation of Section 2.

  * •

$H$ is a countably infinite set of _nodes_ , with $u\in H$;

  * •

$(H,B)$ is an infinite undirected tree rooted at $u$, where every node has at
least one child;

  * •

$(H,R)$ is an infinite undirected multigraph, where all edges have finite
multiplicities;

  * •

$\ell\colon H\setminus\\{u\\}\to\mathcal{I}$ is a function that assigns a
_label_ $\ell(h)\in\mathcal{I}$ to each node $h\in H$ other than $u$.

The elements of $B$ are called _black edges_ , and $(H,B)$ is the _black tree_
of $\mathcal{H}$. Similarly, $(H,R)$ is the _red multigraph_ of $\mathcal{H}$,
and its edges (with positive multiplicity) are called _red edges_.

The _depth_ of $h\in H$ is the distance between the nodes $u$ and $h$ as
measured in the black tree. For all $i\geq-1$, we define the $i$th _level_
$L_{i}\subseteq H$ as the set of nodes that have depth $i+1$. Thus,
$L_{-1}=\\{u\\}$.

The nodes of a history tree inherit their “parent-child-sibling” relationships
from the black tree: for example, $u$ is the _parent_ of all the nodes in
$L_{0}$ because it is connected to all of them by black edges; thus, every two
nodes in $L_{0}$ are _siblings_ , etc.

A _descending path_ in a history tree is a sequence of $k\geq 1$ nodes
$(h_{1},h_{2},\dots,h_{k})$ such that, for all $1\leq i<k$, the unordered pair
$\\{h_{i},h_{i+1}\\}$ is either a black or a red edge and, if $h_{i}\in
L_{j}$, then $h_{i+1}\in L_{j^{\prime}}$ with $j^{\prime}>j$. Equivalently, we
say that $(h_{k},h_{k-1},\dots,h_{1})$ is an _ascending path_. The node
$h_{1}$ is the _upper endpoint_ of the path, and $h_{k}$ is the _lower
endpoint_. If $k=1$, then $h_{1}$ is both the upper and the lower endpoint.

Let $h$ be a node in a history tree $\mathcal{H}=(H,u,B,R,\ell)$, and let
$H_{h}\subset H$ be the set of all upper endpoints of ascending paths whose
lower endpoint is $h$. The _view_ of $h$ in $\mathcal{H}$, denoted as
$\nu(h)$, is the (finite) subtree of $\mathcal{H}$ induced by $H_{h}$. Namely,
$\nu(h)=(H_{h},B_{h},R_{h},\ell_{h})$, where $B_{h}\subset B$ is the set of
black edges whose endpoints are both in $H_{h}$, $R_{h}$ is the restriction of
$R$ to the unordered pairs of nodes in $H_{h}$, and $\ell_{h}$ is the
restriction of $\ell$ to $H_{h}$. The node $h$ is said to be the _viewpoint_
of the view $\nu(h)$; note that the viewpoint is the unique deepest node in
the view. We will denote by $\mathcal{V}_{\mathcal{I}}$ the set of all views
of all history trees on the input set $\mathcal{I}$.

###  B.2 History Tree of a Dynamic Network

Given a dynamic network $\mathcal{G}=(G_{i}=(V,E_{i}))_{i\geq 1}$ and an input
assignment $\lambda\colon V\to\mathcal{I}$, we will show how to construct a
history tree $\mathcal{H}=(H,u,B,R,\ell)$ with labels in $\mathcal{I}$ that is
naturally associated with $\mathcal{G}$ and $\lambda$.

At the same time, for all $i\geq-1$, we will construct a _representation
function_ $\rho_{i}\colon V\to L_{i}\subset H$. Intuitively, if $h\in L_{i}$,
the preimage $\rho_{i}^{-1}(h)$ is a set of processes that, based on their
“history”, are necessarily “indistinguishable” at the end of round $r_{i}$ (we
will also give a meaning to this sentence when $i=-1$ and $i=0$). The
_anonymity_ of a node $h\in L_{i}\subset H$ is the number of processes that
$h$ represents, and is given by the function $\alpha\colon
H\to\mathbb{N}^{+}$, where $\alpha(h)=|\rho_{i}^{-1}(h)|$.

In this paradigm, the label $\ell(h)$ of a node $h\neq u$ is the input
$\lambda(p)$ that each process $p$ represented by $h$ has received at the
beginning of the execution (all such processes must have received the same
input, or else they would have different histories, and they would not be
_necessarily_ indistinguishable).

The black tree keeps track of the progressive “disambiguation” of processes:
if two processes are represented by the same node $h\in L_{i-1}$, they have
had the same history up to round $r_{i-1}$. However, if they receive different
multisets of messages at round $r_{i}$, they are no longer _necessarily_
indistinguishable, and will therefore be represented by two different nodes in
$L_{i}$, each of which is a child of $h$ in $\mathcal{H}$.

Red edges represent “observations”: if, at round $r_{i}$, each of the
processes represented by node $h\in L_{i}$ has received messages from
processes represented by node $h^{\prime}\in L_{i-1}$ through a total of $m$
links in $G_{i}$, then $R$ contains the red edge $\\{h,h^{\prime}\\}$ with
multiplicity $m$.

We inductively construct the history tree $\mathcal{H}$ and the representation
functions $\rho_{i}$ level by level. First we define $\rho_{-1}(p)=u$ for all
$p\in V$, where $u$ is the root of $\mathcal{H}$. The intuitive meaning is
that, before processes are assigned inputs (i.e., at “round $r_{-1}$”), they
are all indistinguishable, because the network is anonymous. Thus, the
anonymity of the root node $u$ is $|V|=n$.

The level $L_{0}$ of $\mathcal{H}$ represents the system at the end of “round
$r_{0}$”, i.e., after every process $p\in V$ has been assigned its input
$\lambda(p)\in\mathcal{I}$ and has acquired an initial state
$\iota(\lambda(p))$. At this point, processes with the same input are
necessarily indistinguishable. Thus, for every input $x\in\lambda(V)$, there
is a node $h_{x}\in L_{0}$ with label $\ell(h_{x})=x$. Accordingly, for every
process $p\in\lambda^{-1}(x)$, we define $\rho_{0}(p)=h_{x}$.

In order to inductively construct the level $L_{i}$ of $\mathcal{H}$ for
$i\geq 1$, we define the concept of _observation multiset_
$o_{i}(p)\in\mathcal{M}_{L_{i-1}}$ of a process $p\in V$ at round $r_{i}$.
This corresponds to the multiset of “necessarily indistinguishable” messages
received by $p$ at round $r_{i}$, and its underlying set is $L_{i-1}$, i.e.,
the collection of equivalence classes of processes that are necessarily
indistinguishable after round $r_{i-1}$. The definition of $o_{i}(p)$ is
similar to the definition of $M_{i}(p)$ in Section A.1, as these are two
closely related concepts:

$o_{i}(p)\colon L_{i-1}\to\mathbb{N}\quad\mbox{such that}\quad L_{i-1}\ni
h\mapsto\sum_{q\in\rho_{i-1}^{-1}(h)}E_{i}(\\{p,q\\}).$

Now, the children of $h\in L_{i-1}$ in $L_{i}$ are constructed as follows.
Define the equivalence relation $\sim_{h}$ on the set of processes
$V_{h}=\rho_{i-1}^{-1}(h)$ such that $p\sim_{h}q$ if and only if
$o_{i}(p)=o_{i}(q)$. Let $W_{1}$, $W_{2}$, …, $W_{k}$ be the equivalence
classes of $\sim_{h}$, with $W_{1}\cup W_{2}\cup\dots\cup W_{k}=V_{h}$. The
node $h$ has exactly $k$ children $h_{1}$, $h_{2}$, …$h_{k}$ in $L_{i}$, one
for each equivalence class of $\sim_{h}$. Thus, for every $1\leq j\leq k$ and
every process $p\in W_{j}$, we define $\rho_{i}(p)=h_{j}$. Also, since
$W_{j}\subseteq V_{h}$ and a process’ input never changes, we set
$\ell(h_{j})=\ell(h)$. The red edges connecting $h_{j}$ with nodes in
$L_{i-1}$ match the observation multiset of the processes in $W_{j}$. That is,
if the node $h^{\prime}\in L_{i-1}$ has multiplicity $m$ in $o_{i}(p)$, where
$p\in W_{j}$, then the red edge $\\{h_{j},h^{\prime}\\}$ has multiplicity $m$
in $R$.

###  B.3 Basic Properties of History Trees

The following properties of history trees are easily derived from the
definitions in Section B.2.

######  Observation B.1.

  * •

No two nodes in $L_{0}$ have the same label, and each node in
$H\setminus(L_{-1}\cup L_{0})$ has the same label as its parent.

  * •

Edges only connect nodes in adjacent levels; if $\\{h,h^{\prime}\\}$ is a
black or red edge with $h\in L_{i}$, then $h^{\prime}\in L_{i-1}\cup L_{i+1}$.

  * •

If $h\in L_{i}$ with $i\geq-1$ and $h_{1},h_{2},\dots,h_{k}\in L_{i+1}$ are
the children of $h$, then

$\bigsqcup_{j=1}^{k}\rho_{i+1}^{-1}(h_{j})=\rho_{i}^{-1}(h),\quad\mbox{and
therefore}\quad\sum_{j=1}^{k}\alpha(h_{j})=\alpha(h).$

We will now give a concrete meaning to the idea that the processes represented
by a node of a history tree are “necessarily indistinguishable”. That is, if a
node is in the $i$th level, then all the processes it represents must have the
same state at the end of round $r_{i}$, regardless of the deterministic
algorithm being executed (cf. Corollary B.3).

We will first prove a fundamental result: the internal state $\sigma_{i}(p)$
of any process $p\in V$ at the end of any round $r_{i}$, with $i\geq 0$, can
be inferred from the process’ _history_ $\xi_{i}({p})$, which is defined as
the view of the node of $L_{i}$ representing $p$, i.e.,
$\xi_{i}({p})=\nu(\rho_{i}(p))$.

######  Theorem B.2.

Given any set of computation parameters (as defined in Section A.1), there
exists a function $\mathcal{F}\colon\mathcal{V}_{\mathcal{I}}\to\mathcal{S}$
such that, for every history tree $\mathcal{H}$ associated with a dynamic
network $\mathcal{G}$ and an input assignment $\lambda$ (as defined in Section
B.2), and for every process $p\in V$ and every $i\geq 0$,
$\mathcal{F}(\xi_{i}({p}))=\sigma_{i}(p)$.

###### Proof.

Let $h=\rho_{i}(p)$, and let
$\xi_{i}({p})=\nu(h)=(H_{h},B_{h},R_{h},\ell_{h})$ be the view of $h$ in the
history tree $\mathcal{H}=(H,u,B,R,\ell)$. We will define $\mathcal{F}$ (in
terms of the computation parameters $\iota\colon\mathcal{I}\to\mathcal{S}$ and
$\mathcal{A}\colon\mathcal{S}_{N}\times\mathcal{M}_{\mathcal{S}}\to\mathcal{S}$)
in such a way that
$\mathcal{F}(\xi_{i}({p}))=\mathcal{F}(\nu(h))=\sigma_{i}(p)$.

Note that $\mathcal{F}$ can identify $h$ as the deepest node of
$\xi_{i}({p})$. Also, it can compute $i$ as the depth of $h$ in the black tree
$(H_{h},B_{h})$ minus $1$. Hence, $h$ and $i$ do not have to be explicitly
provided as arguments to $\mathcal{F}$.

The construction of $\mathcal{F}$ is done by induction on $i$. If $i=0$, the
view $\xi_{0}({p})=\nu(h)$ contains the node $h\in L_{0}$, whose label
$\ell_{h}(h)=\ell(h)$ is the input of $p$, i.e., $\lambda(p)$ (cf. the
construction of $L_{0}$ in Section B.2). Therefore, we set
$\mathcal{F}(\xi_{i}({p}))=\iota(\ell(h))$; indeed,
$\mathcal{F}(\xi_{i}({p}))=\iota(\lambda(p))=\sigma_{0}(p)$ (cf. the
definition of $\sigma_{0}(p)$ in Section A.1).

Now let $i\geq 1$, and assume that $\mathcal{F}(\xi_{i-1}({q}))$ has been
defined for every $q\in V$. We will show how, given $\xi_{i}({p})=\nu(h)$, the
function $\mathcal{F}$ can compute $\sigma_{i}(p)$.

By definition of view, it immediately follows that the view of any node
$h^{\prime}\in H_{h}$ is contained in the view of $h$. That is, all nodes and
all black and red edges of $\nu(h^{\prime})$ are contained in $\nu(h)$, and
the two views also agree on the labels. Thus, given the history
$\xi_{i}({p})=\nu(h)$, the function $\mathcal{F}$ can infer the view of any
node $h^{\prime}\in H_{h}$ by taking all the ascending paths in $\nu(h)$ with
lower endpoint $h^{\prime}$. In particular, if $\\{h,h^{\prime}\\}$ is a black
or red edge in $\nu(h)$, then $h^{\prime}\in L_{i-1}$, and therefore
$\mathcal{F}$ can determine the state $\sigma_{i-1}(q)$ of any process
$q\in\rho_{i-1}^{-1}(h^{\prime})$, by the inductive hypothesis.

Observe that the only black edge $\\{h,h^{\prime\prime}\\}\in B_{h}$ incident
to $h$ connects it with its parent $h^{\prime\prime}\in L_{i-1}$, and
$p\in\rho_{i-1}^{-1}(h^{\prime\prime})$, due to B.1. Thus, $\mathcal{F}$ can
identify the parent of $h$ and determine $\sigma_{i-1}(p)$. Similarly, the
observation multiset $o_{i}(p)$ can be inferred by taking the multiplicities
of all red edges of the form $\\{h,h^{\prime\prime\prime}\\}\in R_{h}$ (cf.
the construction of the red edges in Section B.2). Again, for each such
$h^{\prime\prime\prime}\in L_{i-1}$, it is possible to determine the state
$\sigma_{i-1}(q)$ of any process
$q\in\rho_{i-1}^{-1}(h^{\prime\prime\prime})$. The multiset of these states
(with the multiplicities inherited from $o_{i}(p)$) is precisely $M_{i}(p)$,
i.e., the multiset of states that $p$ receives at round $r_{i}$ (cf. the
definition of $M_{i}(p)$ in Section A.1).

We conclude that $\mathcal{F}$ can compute $\sigma_{i}(p)$ by first
determining $\sigma_{i-1}(p)$ and $M_{i}(p)$, and then computing
$\mathcal{A}(\sigma_{i-1}(p),M_{i}(p))$ (cf. the definition of $\sigma_{i}(p)$
in Section A.1). ∎

######  Corollary B.3.

During a computation in an anonymous dynamic network, at the end of round
$r_{i}$, with $i\geq 0$, all processes represented by the same node (in the
$i$th level) of the history tree have the same state.

###### Proof.

The history at round $r_{i}$ of all processes represented by the node $h\in
L_{i}$ is $\nu(h)$. Therefore, all such processes must have the same state
$\mathcal{F}(\nu(h))$, by Theorem B.2. ∎

###  B.4 Constructing and Updating History Trees

We will now describe the algorithm $\mathcal{A}^{\ast}$ mentioned at the end
of Section 3. This algorithm takes as input a process $p$’s history at the end
of the previous round $\xi_{i-1}(p)$, as well as the multiset of histories of
neighboring processes $M_{i}(p)$, and constructs the new history $\xi_{i}(p)$
by _merging_ $\xi_{i-1}(p)$ with all the histories in $M_{i}(p)$.

Let us give a preliminary definition. A _homomorphism_ from a view
$\nu(a)=(H_{a},B_{a},R_{a},\ell_{a})\in\mathcal{V}_{\mathcal{I}}$ to a view
$\nu(b)=(H_{b},B_{b},R_{b},\ell_{b})\in\mathcal{V}_{\mathcal{I}}$ is a
function $\varphi\colon H_{a}\to H_{b}$ that “preserves structure”. That is,
for all $\\{h,h^{\prime}\\}\in B_{a}$, we have
$\\{\varphi(h),\varphi(h^{\prime})\\}\in B_{b}$; for all $h,h^{\prime}\in
H_{a}$, we have
$R_{a}(\\{h,h^{\prime}\\})=R_{b}(\\{\varphi(h),\varphi(h^{\prime})\\})$; for
all $h\in H_{a}$, we have $\ell_{a}(h)=\ell_{b}(\varphi(h))$.

The new history $\xi_{i}(p)$ can be constructed from $\xi_{i-1}(p)$ and
$M_{i}(p)$ as follows. The first step is to identify the viewpoint of
$\xi_{i-1}(p)$, which is the (unique) deepest node $h$ in the view; note that
$h=\rho_{i}(p)$. The second step is to “extend” $\xi_{i-1}(p)$ by adding a new
node $h^{\prime}$, with the same label as $h$, and the new black edge
$\\{h,h^{\prime}\\}$. Let $Z_{0}\in\mathcal{V}_{\mathcal{I}}$ be the resulting
view; note that $h^{\prime}$ is the (unique) child of $h$ in $Z_{0}$.
Eventually, the node $h^{\prime}$ will be the viewpoint of $\xi_{i}(p)$.

Let $\xi_{i-1}(q_{1})$, $\xi_{i-1}(q_{2})$, …, $\xi_{i-1}(q_{k})$ be the
histories with positive multiplicity in $M_{i}(p)$ (note that they must all be
histories of processes at round $r_{i-1}$: such are the messages received by
$p$ at round $r_{i}$). The next phase of the algorithm is to construct a
sequence of views $Z_{0},Z_{1},Z_{2},\dots,Z_{k}\in\mathcal{V}_{\mathcal{I}}$
such that $Z_{j}$ is the smallest view in $\mathcal{V}_{\mathcal{I}}$ that
contains both $Z_{j-1}$ and $\xi_{i-1}(q_{j})$, for all $1\leq j\leq k$.

In practice, the algorithm constructs $Z_{j}$ by starting from $Z_{j-1}$ and
gradually adding the “missing nodes” from $\xi_{i-1}(q_{j})$, at the same time
constructing an (injective) homomorphism $\varphi_{j}$ from $\xi_{i-1}(q_{j})$
to $Z_{j}$. First, the root of $\xi_{i-1}(q_{j})$ is mapped by $\varphi_{j}$
to the root of $Z_{j-1}$. Then, the algorithm scans all the nodes of
$\xi_{i-1}(q_{j})$ level by level (i.e., doing a breadth-first traversal along
the black edges). Let $v$ be a node of $\xi_{i-1}(q_{j})$ encountered during
the traversal, and let $v^{\prime}$ be its parent in $\xi_{i-1}(q_{j})$. The
algorithm attempts to match $v$ with a child $w$ of the node
$w^{\prime}=\varphi_{j}(v^{\prime})$ in $Z_{j-1}$. The label of $w$ should be
the same as the label of $v$ and, for every red edge
$\\{v,v^{\prime\prime}\\}$ in $\xi_{i-1}(q_{j})$, connecting $v$ with a
previous-level node $v^{\prime\prime}$, the edge
$\\{w,\varphi_{j}(v^{\prime\prime})\\}$ should also appear in $Z_{j-1}$ with
the same multiplicity. If a node $w$ with these properties does not exist, the
algorithm creates one, and then sets $\varphi_{j}(v)=w$. When the traversal is
over, the resulting structure is $Z_{j}$, by definition.

Note that the final structure $Z_{k}$ coincides with $\xi_{i}(p)$, except for
some missing red edges: these are the red edges incident to the viewpoint
$h^{\prime}$ which represent the messages received by $p$ at round $r_{i}$.
Thus, for every $1\leq j\leq k$, the viewpoint $h_{j}$ of $\xi_{i-1}(q_{j})$
is found (as the unique deepest node in $\xi_{i-1}(q_{j})$) and the red edge
$\\{h^{\prime},\varphi_{j}(h_{j})\\}$ is added to $Z_{k}$, with the same
multiplicity as $\xi_{i-1}(q_{j})$ in $M_{i}(p)$. The resulting history is
$\xi_{i}(p)$.

##  Appendix C Additional Lower Bounds and Counterexamples

###  C.1 Naive Termination May Fail

The example in Figure 5 shows that the techniques in Section 4.1 are
insufficient to formulate a correct termination condition. The first level in
the leader’s view where all nodes are non-branching is $L_{0}$, but the
stabilizing algorithm in Section 4.1 computes the wrong anonymities, reporting
that $n=5$ (note that $L_{0}$ is actually branching in the full history tree).
By increasing $k$ indefinitely, we let the leader see only four nodes per
level for an arbitrarily long time, while the real size of the network is kept
hidden. This makes any naive termination strategy ineffective.

Figure 5: An example of a dynamic network where the naive techniques of
Section 4.1 fail to provide a termination condition. The white nodes in the
history tree are not in the history of the leader at the last round; the red
edges not in the view are not drawn. Same-colored processes have equal inputs.
Note that, after level $L_{1}$, all levels in the leader’s view are identical
for an arbitrarily long sequence of rounds (depending on the parameter $k$).

###  C.2 Worst-Case Example for the Terminating Algorithm

The example in Figure 6, which can be easily generalized to networks of any
size $n$, shows that the counting algorithm of Section 4.2 may terminate in
$3n-3$ rounds. This almost matches our analysis in Theorem 4.10, which gives
an upper bound of $3n-2$ rounds.

Figure 6: An example of a dynamic network where the algorithm of Section 4.2
terminates in $3n-3$ rounds, and its history tree. The white nodes are not in
the history of the leader at the last round.

###  C.3 More General but Wearker Lower Bounds

We will show that a large class of multi-aggregation problems cannot be solved
in an anonymous dynamic network in less than $1.5n-2$ rounds, even if the
network’s topology may change only once. Note that the bound of Theorem 5.2 is
better, but it only applies to the Counting Problem, and requires the
network’s topology to change $\Omega(n)$ times.

Our new lower bound is based on the construction of some 1-interval-connected
dynamic networks whose topology changes from a cycle graph to a path graph
(refer to Figures 7 and 8). Given two parameters $n,m\in\mathbb{N}^{+}$ with
$m<n$, we define the system $V_{n}=\\{1,2,\dots,n\\}$ and the dynamic network
$\mathcal{G}_{n,m}=(G_{i}=(V_{n},E_{i}))_{i\geq 1}$ as follows. For all $1\leq
i<m$, the edge multiset $E_{i}$ contains all edges of the form $(j,j+1)$ with
$1\leq j<n$, as well as $(1,n)$, all with multiplicity $1$ (thus, $G_{i}$ is a
cycle graph spanning all processes). For $i\geq m$, the topology changes
slightly: the edges $(m,m+1)$ and $(1,n)$ are removed, and the edge $(m,n)$ is
introduced, with multiplicity $1$ (thus, $G_{i}$ is a path graph spanning all
processes, with endpoints $1$ and $m+1$).

We will first apply our technique to the Counting Problem. Although this is
redundant in light of Theorem 5.2, it allows us to showcase a proof pattern
that applies to several more problems.

######  Theorem C.1.

No deterministic algorithm can solve the Counting Problem
$\mathcal{C}_{\mathcal{I}}$ in an anonymous dynamic network of $n$ processes
in less than $1.5n-2$ rounds, even if the network is 1-interval-connected, and
even if there is a unique leader in the system.

###### Proof.

Let $\mathcal{I}=\\{L,N\\}\times\mathcal{I}^{\prime}$ be the input set, and
let $x\in\mathcal{I}^{\prime}$. Fix $m\geq 1$, and let $n=2m$ and
$n^{\prime}=2m+1$. Consider the two systems $V=V_{n}$ and
$V^{\prime}=V_{n^{\prime}}$ with their respective dynamic networks
$\mathcal{G}=\mathcal{G}_{n,m}=(G_{i}=(V_{n},E_{i}))_{i\geq 1}$ and
$\mathcal{G}^{\prime}=\mathcal{G}_{n^{\prime},m}=(G^{\prime}_{i}=(V_{n^{\prime}},E^{\prime}_{i}))_{i\geq
1}$ (where $\mathcal{G}_{n,m}$ and $\mathcal{G}_{n^{\prime},m}$ are as defined
above). We further define the input assignments $\lambda\colon
V\to\mathcal{I}$ and $\lambda^{\prime}\colon V^{\prime}\to\mathcal{I}$, which
assign the input $(L,x)$ to process $1$ and the input $(N,x)$ to all other
processes. Thus, in both systems, process $1$ is the leader, and all other
processes are anonymous. We denote as $\mathcal{H}$ (respectively,
$\mathcal{H}^{\prime}$) the history tree associated with $\lambda$ and
$\mathcal{G}$ (respectively, $\lambda^{\prime}$ and $\mathcal{G}^{\prime}$),
while $\xi_{i}(p)$ and $\xi^{\prime}_{i}(p^{\prime})$ denote the histories of
processes $p\in V$ and $p^{\prime}\in V^{\prime}$, respectively, at round
$r_{i}$.

We define the _$d$ -neighborhood_ $\mathcal{N}_{i}(p,d)$ of a process $p\in V$
at round $r_{i}$, with $i\geq 1$, as the subgraph of $G_{i}$ induced by the
processes that have distance at most $d$ from $p$ in $G_{i}$ (similarly, we
define the $d$-neighborhood $\mathcal{N}^{\prime}_{i}(p^{\prime},d)$ of a
process in $p^{\prime}\in V^{\prime}$). We say that $\mathcal{N}_{i}(p,d)$ is
_equivalent_ to $\mathcal{N}^{\prime}_{i}(p^{\prime},d)$ if there is a graph
isomorphism $\varphi$ from $\mathcal{N}_{i}(p,d)$ to
$\mathcal{N}^{\prime}_{i}(p^{\prime},d)$ that preserves inputs; that is,
$\lambda(q)=\lambda^{\prime}(\varphi(q))$ for all processes $q$ in
$\mathcal{N}_{i}(p,d)$.

Recall that, for the first $m-1$ rounds, the topology of both networks is a
cycle graph. Thus, all processes at the same distance from their respective
leader have equivalent $(m-1)$-neighborhoods throughout the first $m-1$
rounds, and therefore also have equal histories. That is, there is a function
$\delta\colon V\to V^{\prime}$ such that
$\xi_{i}(p)=\xi^{\prime}_{i}(\delta(p))$ for all $p\in V$ and $1\leq i<m$.
Namely, $\delta(p)=p$ for all $1\leq p\leq m$, and $\delta(n-p)=n^{\prime}-p$
for all $0\leq p<m$.

Starting at round $r_{m}$, the topology of both networks changes to a path
graph with the leader at one endpoint. These path graphs have the property
that the process at distance $d$ from the leader in $V$ has the same history
as the process at distance $d$ from the leader in $V^{\prime}$ for all $0\leq
d<n$. Thus, the two leaders will keep having equal histories for the following
$n-1=2m-1$ rounds. We conclude that the leaders of the two systems have equal
histories up to round $r_{3m-2}$.

Assume for a contradiction that there are computation parameters (as defined
in Section A.1) that cause all processes in both systems to output the
inventory of their respective input assignments, $\mu_{\lambda}$ and
$\mu_{\lambda^{\prime}}$, thus solving $\mathcal{C}_{\mathcal{I}}$, in less
than $1.5n-1=\lfloor 1.5n^{\prime}\rfloor-2=3m-1$ rounds. Since the leaders of
$V$ and $V^{\prime}$ have equal histories throughout the first $3m-2$ rounds,
by Theorem B.2 they must have equal states, as well. Thus, both leaders must
give the same output upon termination, implying that
$\mu_{\lambda}=\mu_{\lambda^{\prime}}$. This is a contradiction, because
$\mu_{\lambda}((N,x))=n-1\neq n=\mu_{\lambda^{\prime}}((N,x))$. ∎

We can extend Theorem C.1 to several other (multi-aggregation) problems. For
example, fix $n,k\in\mathbb{N}^{+}$, let $m=\lfloor n/2\rfloor$, and consider
the two dynamic networks $\mathcal{G}=\mathcal{G}_{n,m}$ and
$\mathcal{G}^{\prime}=\mathcal{G}_{2n+k-1,m}$ for the systems $V=V_{n}$ and
$V^{\prime}=V_{2n+k-1}$, respectively. Let us assign a leader input to process
$1$ in both systems, any arbitrary $k$-tuple
$((N,x_{1}),(N,x_{2}),\dots,(N,x_{k}))$ of inputs to processes $n+1$, $n+2$,
…, $n+k$ in $V^{\prime}$, and another input $(N,x)$ (not in the $k$-tuple) to
all other processes.

Now, the same argument used for proving Theorem C.1 shows that the two leaders
have equal histories for the first $3m-2$ rounds. Thus, the leaders are not
only unable to count the number of processes in less than $1.5n-2$ rounds, but
are also unable to tell whether the system contains any process at all with
inputs in the chosen $k$-tuple.

Figure 7: The dynamic network $\mathcal{G}_{n,m}$ with $m=4$ and $n=8$, and
its history tree. The red edges not in the view of the leader have not been
drawn. Figure 8: The dynamic network $\mathcal{G}_{n,m}$ with $m=4$ and $n=9$,
and its history tree. Observe that the leaders of this network and of the
network in Figure 7 have isomorphic histories at round $3m-2=10$ (cf. Theorem
C.1).

##  Appendix D Survey of Related Work

We examine related work on counting and related problems by first discussing
the case of dynamic networks with unique IDs, then the case of static
anonymous networks, and finally the case of interval-connected anonymous
networks. We conclude the section by examining the average consensus problem,
which is deeply related to counting.

###  D.1 Dynamic Networks with IDs

The problem of counting the size of a dynamic network has been first studied
by the peer-to-peer systems community [34]. In this case having an exact count
of the network at a given time is impossible, as processes may join or leave
in an unrestricted way. Therefore, their algorithms mainly focus on providing
estimates on the network size with some guarantees. The most related is the
work that introduced 1-interval-connected networks [31]. They show a counting
algorithm that terminates in at most $n+1$ rounds when messages are
unrestricted and in $O(n^{2})$ rounds when the message size is $O(\log n)$
bits. The techniques used heavily rely on the presence of unique IDs and
cannot be extended to our settings.

###  D.2 Anonymous Static Networks

The study of computability on anonymous networks has been pioneered by Angluin
in [1] and it has been a fruitful research topics for the last 30 years [1, 7,
13, 14, 15, 23, 42, 45]. A key concept in anonymous networks is the symmetry
of the system; informally, it is the indistinguishability of nodes that have
the same view of the network. As an example, in an anonymous static ring
topology, all processes will have the exact same view of the system, and such
a view does not change between rings of different size. Therefore, non-trivial
computations including counting are impossible on rings, and some symmetry-
breaking assumption is needed (such as a leader [23]). The situation changes
if we consider topologies that are asymmetric. As an example, on a wheel graph
the central node has a view that is unique, and this allows for the election
of a leader and the possibility, among other tasks, of counting the size of
the network.

Several tools have been developed to characterize what can be computed on a
given network topology (examples are views [45] or fibrations [8]).
Unfortunately, these techniques are usable only in the static case and are not
defined for highly dynamic systems like the ones studied in our work.
Regarding the counting problem in anonymous static networks with a leader,
[35] gives a counting algorithm that terminates in at most $2n$ rounds.

###  D.3 Counting in Anonymous Interval-Connected Networks

The papers that studied counting in anonymous dynamic networks can be divided
into two periods. A first series of works [12, 19, 20, 35] gave solutions for
the counting problem assuming some initial knowledge on the possible degree of
a processes. As a matter of fact [35] conjectured that some kind of knowledge
was necessary to have a terminating counting algorithm. A second series of
works [17, 25, 27, 28, 29] has first shown that counting was possible without
such knowledge, and then has proposed increasingly faster solutions. We remark
that all these papers assume that a leader (or multiple leaders in [28]) is
present. This assumption is needed to break the symmetry.

#### Counting with knowledge on the degrees.

Counting in interval-connected anonymous networks was first studied in [35],
where it is observed that a leader is necessary to solve counting in static
(and therefore also dynamic) anonymous networks (this result can be derived
from previous works on static networks such as [8, 45]). The paper does not
give a counting algorithm but it gives an algorithm that is able to compute an
upper bound on the network size. Specifically, [35] proposes an algorithm
that, using an upper bound $d$ on the maximum degree that each process will
ever have in the network, calculates an upper bound $U$ on the size of the
network; this upper bound may be exponential in the actual network size
($U\leq d^{n}$).

Assuming the knowledge of an upper bound on the degree, [19] given a counting
algorithm that computes $n$. Such an algorithm is really costly in terms of
rounds; it has been shown in [12] to be doubly exponential in the network
size. The algorithm proposes a mass distribution approach akin to local
averaging [44].

An experimental evaluation of the algorithm in [19] can be found in [21]. The
result of [19] has been improved in [12], where, again assuming knowledge of
an upper bound $d$ on the maximum degree of a node, an algorithm is given that
terminates in $O\left(n(2d)^{n+1}\frac{\log n}{\log{d}}\right)$ rounds. A
later paper [20] has shown that counting is possible when each process knows
its degree before starting the round (for example, by means of an oracle). In
this case, no prior global upper bound on the degree of processes is needed.
[20] only show that the algorithm eventually terminates but does not bound the
termination time.

We remark that all the above works assume some knowledge on the dynamic
network, as an upper bound on the possible degrees, or as a local oracle.
Moreover, all of these works give exponential-time algorithms.

#### Counting without knowledge on the degrees.

The first work proposing an algorithm that does not require any knowledge of
the network was [18]. The paper proposed an exponential-time algorithm that
terminates in $O\left(n^{n+4}\right)$ rounds. Moreover, it also gives an
asymptotically optimal algorithm for a particular category of networks (called
persistent-distance). In this type of network, a node never changes its
distance from the leader.

This result was improved in [25, 27], which presented a polynomial-time
counting algorithm. The paper proposes Methodical Counting, an algorithm that
counts in $O(n^{5}\log^{2}(n))$ rounds. Similar to [19, 20], the paper uses a
mass-distribution process that is coupled with a refined analysis of
convergence time and clever techniques to detect termination. The paper also
notes that, using the same algorithm, all algebraic and boolean functions that
depend on the initial number of processes in a given state can be computed.
The authors of [25, 27] extended their result to work in networks where $l\geq
1$ leaders are present (with $l$ known in advance) in [29]. They create an
algorithm that terminates in
$O\left(\frac{n^{4+\epsilon}}{l}\log^{3}(n)\right)$ rounds, for any
$\epsilon>0$. In particular, when $l=1$, this results improves the running
time of [25, 27].

Finally, in [28], they show a counting algorithm parameterized by the
isoperimetric number of the dynamic network. The technique used is similar to
[25, 27], and it uses the knowledge of the isoperimetric number to shorten the
termination time. Specifically, for adversarial graphs (i.e., with non-random
topology) with $l$ leaders ($l$ is assumed to be known in advance), they give
an algorithm terminating in
$O\left(\frac{n^{3+\epsilon}}{l{i_{min}}^{2}}\log^{3}(n)\right)$ rounds, where
$i_{min}$ is a known lower bound on the isoperimetric number of the network.
This improves the work in [29], but only in graphs where $i_{min}$ is
$\omega({1}/{\sqrt{n}})$. The authors also study various types of graphs with
stochastic dynamism; we remark that in this case they always obtain
superlinear results, as well. The best case is that of Erdős–Rényi, graphs
where their algorithm terminates in
$O\left(\frac{n^{1+\epsilon}}{l{p_{min}}^{2}}\log^{5}(n)\right)$ rounds; here
$p_{min}$ is the smallest among the probabilities of creating an arc on all
rounds. Specifically, if $p_{min}=O({1}/{n})$, their algorithm is at least
cubic.

Summarizing, to the best of our knowledge, no linear-time algorithm is known
for anonymous dynamic networks, even when additional knowledge is provided
(e.g., the isoperimetric number [28]), or when the topology of the network is
random and not worst-case. Notice that a random topology is a really powerful
assumption in anonymous networks, as it is likely to greatly help in breaking
symmetry.

We stress that our algorithms run in linear time without requiring any prior
knowledge, and works for worst-case dynamic topologies (and thus, also in the
case of a random dynamicity).

#### Lower bounds on counting.

From [31], a trivial lower bound of $n-1$ rounds can be derived, as counting
obviously requires information from each node to be spread in the network.
Interestingly, prior to our work, little was known apart from this result. The
only other lower bound is in [17], which shows a specific category of
anonymous dynamic networks with constant temporal diameter (the time needed to
spread information from a node to all others is at most 3 rounds), but where
counting requires $\Omega(\log n)$ rounds. Therefore, our lower bound of
roughly $2n$ rounds greatly improves on the previously known lower bounds for
the general case (networks that have an arbitrary temporal diameter).

###  D.4 Average Consensus

Counting is deeply related to the average consensus problem. In this problem,
each process $v_{i}$ starts with an input value $x_{i}(0)$, and processes must
calculate the average of these initial values. Note that the Generalized
Counting trivially leads to a solution for the average consensus.

The first paper to propose a decentralized solution was [44]. It introduced an
approach called “local averaging”, where each process updates its local value
$x_{i}(r)$ at every round $r$ as follows:

$\displaystyle x_{i}(r)=\sum_{\forall{v_{j}\in
N(r,v_{i})\cup\\{v_{i}\\}}}a_{ij}(r)\cdot x_{j}(r-1).$

The value $a_{ij}(r)$ is taken from a weight matrix that can model a dynamic
graph. The $\epsilon$-convergence of this algorithm is defined as the time it
takes to be sure that the maximum discrepancy between the local value of a
node and the mean is at most $\epsilon$ times the initial discrepancy. That
is, if the mean is $m=\sum_{i\in V}x_{i}(0)/{|V|}$, the following should hold:

$\frac{\text{max}_{i}\left\\{|x_{i}(r)-m|\right\\}}{\text{max}_{i}\left\\{|x_{i}(0)-m|\right\\}}\leq\epsilon.$

The local averaging approach has been studied in depth, and several upper and
lower bounds for $\epsilon$-convergence are known for both static and dynamic
networks [39, 40]. The procedure $\epsilon$-converges in
$O(|V|^{3}\log(1/{\epsilon}))$ rounds if, at every round, the weight matrix
$A(r)$ such that $(A(r))_{ij}=a_{ij}(r)$ is doubly stochastic (i.e., the sum
of the values on rows and columns is $1$) [37]. In a dynamic network, it is
possible to have doubly stochastic weight matrices when an upper bound on the
node degree is known [16]. We remark that local averaging algorithms do not
need unique IDs, and thus work in anonymous dynamic networks; we also note
that the process does not explicitly terminate, but just converges to the
average of the inputs.

To the best of our knowledge, there is no solution to average consensus based
on local averaging or other techniques with a linear convergence time. Our
algorithm shows that solving the average consensus in 1-interval-connected
anonymous networks with a leader is possible in linear time with strict
termination and perfect convergence ($\epsilon=0$). Moreover, our lower bound
on counting is also a lower bound on average consensus (if the leader starts
with a value of $1$ and all other processes with $0$’s, the average converges
to the inverse of the size). Thus, our paper shows that a lower bound on
convergence of any average consensus algorithm is roughly $2n$ in anonymous
dynamic networks.

## References

  * [1] D. Angluin.  Local and Global Properties in Networks of Processors (Extended Abstract).  In Proceedings of the 12th ACM Symposium on Theory of Computing (STOC ’80), pages 82–93, 1980.
  * [2] D. Angluin, J. Aspnes, and D. Eisenstat.  Fast Computation by Population Protocols with a Leader.  Distributed Computing, 21(3):61–75, 2008.
  * [3] J. Aspnes, J. Beauquier, J. Burman, and D. Sohier.  Time and Space Optimal Counting in Population Protocols.  In Proceedings of the 20th International Conference on Principles of Distributed Systems (OPODIS ’16), pages 13:1–13:17, 2016.
  * [4] L. Baumgärtner, A. Dmitrienko, B. Freisleben, A. Gruler, J. Höchst, J. Kühlberg, M. Mezini, R. Mitev, M. Miettinen, A. Muhamedagic, T. Nguyen, A. Penning, D. Pustelnik, F. Roos, A. Sadeghi, M. Schwarz, and C. Uhl.  Mind the GAP: Security & Privacy Risks of Contact Tracing Apps.  In Proceedings of the 19th IEEE International Conference on Trust, Security and Privacy in Computing and Communications (TrustCom ’20), pages 458–467, 2020.
  * [5] J. Beauquier, J. Burman, S. Clavière, and D. Sohier.  Space-Optimal Counting in Population Protocols.  In Proceedings of the 29th International Symposium on Distributed Computing (DISC ’15), pages 631–646, 2015.
  * [6] J. Beauquier, J. Burman, and S. Kutten.  A Self-stabilizing Transformer for Population Protocols with Covering.  Theoretical Computer Science, 412(33):4247–4259, 2011.
  * [7] P. Boldi and S. Vigna.  An Effective Characterization of Computability in Anonymous Networks.  In Proceedings of the 15th International Conference on Distributed Computing (DISC ’01), pages 33–47, 2001.
  * [8] P. Boldi and S. Vigna.  Fibrations of Graphs.  Discrete Mathematics, 243:21–66, 2002.
  * [9] A. Casteigts, F. Flocchini, B. Mans, and N. Santoro.  Shortest, Fastest, and Foremost Broadcast in Dynamic Networks.  International Journal of Foundations of Computer Science, 26(4):499–522, 2015.
  * [10] A. Casteigts, P. Flocchini, W. Quattrociocchi, and N. Santoro.  Time-Varying Graphs and Dynamic Networks.  International Journal of Parallel, Emergent and Distributed Systems, 27(5):387–408, 2012.
  * [11] M. Chakraborty, A. Milani, and M. A. Mosteiro.  Counting in Practical Anonymous Dynamic Networks Is Polynomial.  In Proceedings of the 4th International Conference on Networked Systems (NETYS ’16), pages 131–136, 2016.
  * [12] M. Chakraborty, A. Milani, and M. A. Mosteiro.  A Faster Exact-Counting Protocol for Anonymous Dynamic Networks.  Algorithmica, 80(11):3023–3049, 2018.
  * [13] J. Chalopin, S. Das, and N. Santoro.  Groupings and Pairings in Anonymous Networks.  In Proceedings of the 20th International Conference on Distributed Computing (DISC ’06), pages 105–119, 2006.
  * [14] J. Chalopin, E. Godard, and Y. Métivier.  Local Terminations and Distributed Computability in Anonymous Networks.  In Proceedings of the 22nd International Symposium on Distributed Computing (DISC ’08), pages 47–62, 2008.
  * [15] J. Chalopin, Y. Métivier, and T. Morsellino.  Enumeration and Leader Election in Partially Anonymous and Multi-hop Broadcast Networks.  Fundamenta Informaticae, 120(1):1–27, 2012.
  * [16] B. Chazelle.  The Total s-Energy of a Multiagent System.  SIAM Journal on Control and Optimization, 49(4):1680–1706, 2011\.
  * [17] G. A. Di Luna and G. Baldoni.  Brief Announcement: Investigating the Cost of Anonymity on Dynamic Networks.  In Proceedings of the 34th ACM Symposium on Principles of Distributed Computing (PODC ’15), pages 339–341, 2015.
  * [18] G. A. Di Luna and G. Baldoni.  Non Trivial Computations in Anonymous Dynamic Networks.  In Proceedings of the 19th International Conference on Principles of Distributed Systems (OPODIS ’15), pages 1–16, 2016.
  * [19] G. A. Di Luna, R. Baldoni, S. Bonomi, and I. Chatzigiannakis.  Conscious and Unconscious Counting on Anonymous Dynamic Networks.  In Proceedings of the 15th International Conference on Distributed Computing and Networking (ICDCN ’14), pages 257–271, 2014.
  * [20] G. A. Di Luna, R. Baldoni, S. Bonomi, and I. Chatzigiannakis.  Counting in Anonymous Dynamic Networks Under Worst-Case Adversary.  In Proceedings of the 34th IEEE International Conference on Distributed Computing Systems (ICDCS ’14), pages 338–347, 2014.
  * [21] G. A. Di Luna, S. Bonomi, I. Chatzigiannakis, and R. 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 (ALGOSENSORS ’13), pages 139–154, 2013.
  * [22] G. A. Di Luna, P. Flocchini, T. Izumi, T. Izumi, N. Santoro, and G. Viglietta.  Population Protocols with Faulty Interactions: The Impact of a Leader.  Theoretical Computer Science, 754:35–49, 2019.
  * [23] P. Fraigniaud, A. Pelc, D. Peleg, and S. Pérennes.  Assigning Labels in Unknown Anonymous Networks.  In Proceedings of the 19th ACM Symposium on Principles of Distributed Computing (PODC ’00), pages 101–111, 2000.
  * [24] M. Ghaffari, C. Musco, T. Radeva, and N. Lynch.  Distributed House-Hunting in Ant Colonies.  In Proceedings of the 34th ACM Symposium on Principles of Distributed Computing (PODC ’15), pages 57–66, 2015.
  * [25] D. R. Kowalski and M. A. Mosteiro.  Polynomial Counting in Anonymous Dynamic Networks with Applications to Anonymous Dynamic Algebraic Computations.  In Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (ICALP ’18), pages 156:1–156:14, 2018.
  * [26] D. R. Kowalski and M. A. Mosteiro.  Polynomial Anonymous Dynamic Distributed Computing Without a Unique Leader.  In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP ’19), pages 147:1–147:15, 2019.
  * [27] D. R. Kowalski and M. A. Mosteiro.  Polynomial Counting in Anonymous Dynamic Networks with Applications to Anonymous Dynamic Algebraic Computations.  Journal of the ACM, 67(2):11:1–11:17, 2020.
  * [28] D. R. Kowalski and M. A. Mosteiro.  Supervised Average Consensus in Anonymous Dynamic Networks.  In Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA ’21), pages 307–317, 2021.
  * [29] D. R. Kowalski and M. A. Mosteiro.  Polynomial Anonymous Dynamic Distributed Computing Without a Unique Leader.  Journal of Computer and System Sciences, 123:37–63, 2022.
  * [30] F. Kuhn, T. Locher, and R. Oshman.  Gradient Clock Synchronization in Dynamic Networks.  Theory of Computing Systems, 49(4):781–816, 2011.
  * [31] F. Kuhn, N. Lynch, and R. Oshman.  Distributed Computation in Dynamic Networks.  In Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC ’10), pages 513–522, 2010.
  * [32] F. Kuhn, Y. Moses, and R. Oshman.  Coordinated Consensus in Dynamic Networks.  In Proceedings of the 30th ACM Symposium on Principles of Distributed Computing (PODC ’11), pages 1–10, 2011.
  * [33] F. Kuhn and R. Oshman.  Dynamic Networks: Models and Algorithms.  SIGACT News, 42(1):82–96, 2011.
  * [34] E. Le Merrer, A.-M. Kermarrec, and L. Massoulie.  Peer to Peer Size Estimation in Large and Dynamic Networks: A Comparative Study.  In Proceedings of the 15th IEEE International Conference on High Performance Distributed Computing (HPDC ’06), pages 7–17, 2006.
  * [35] O. Michail, I. Chatzigiannakis, and P. G. Spirakis.  Naming and Counting in Anonymous Unknown Dynamic Networks.  In Proceedings of the 15th International Symposium on Stabilizing, Safety, and Security of Distributed Systems (SSS ’13), pages 281–295, 2013.
  * [36] O. Michail and P. G. Spirakis.  Elements of the Theory of Dynamic Networks.  Communications of the ACM, 61(2):72, 2018.
  * [37] A. Nedić, A. Olshevsky, A. E. Ozdaglar, and J. N. Tsitsiklis.  On Distributed Averaging Algorithms and Quantization Effects.  IEEE Transactions on Automatic Control, 54(11):2506–2517, 2009\.
  * [38] R. O’Dell and R. Wattenhofer.  Information Dissemination in Highly Dynamic Graphs.  In Proceedings of the 5th Joint Workshop on Foundations of Mobile Computing (DIALM-POMC ’05), pages 104–110, 2005.
  * [39] A. Olshevsky and J. N. Tsitsiklis.  Convergence Speed in Distributed Consensus and Averaging.  SIAM Journal on Control and Optimization, 48(1):33–55, 2009.
  * [40] A. Olshevsky and J. N. Tsitsiklis.  A Lower Bound for Distributed Averaging Algorithms on the Line Graph.  IEEE Transactions on Automatic Control, 56(11):2694–2698, 2011\.
  * [41] N. Sakamoto.  Comparison of Initial Conditions for Distributed Algorithms on Anonymous Networks.  In Proceedings of the 18th ACM Symposium on Principles of Distributed Computing (PODC ’99), pages 173–179, 1999.
  * [42] J. Seidel, J. Uitto, and R. Wattenhofer.  Randomness vs. Time in Anonymous Networks.  In Proceedings of the 29th International Symposium on Distributed Computing (DISC ’15), pages 263–275, 2015.
  * [43] T. Sharma and M. Bashir.  Use of Apps in the COVID-19 Response and the Loss of Privacy Protection.  Nature Medicine, 26(8):1165–1167, 2020.
  * [44] J. N. Tsitsiklis.  Problems in Decentralized Decision Making and Computation.  PhD thesis, Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 1984.
  * [45] M. Yamashita and T. Kameda.  Computing on an Anonymous Network.  In Proceedings of the 7th ACM Symposium on Principles of Distributed Computing (PODC ’88), pages 117–130, 1988.
  * [46] M. Yamashita and T. Kameda.  Computing on Anonymous Networks. I. Characterizing the Solvable Cases.  IEEE Transactions on Parallel and Distributed Systems, 7(1):69–89, 1996.