Universal Finite-State and Self-Stabilizing Computation in Anonymous Dynamic Networks¹¹1Both authors contributed equally to this research.

The rise of technologies such as wireless sensor networks, software-defined networks, and ad-hoc networks of smart devices has led to the prevalence of network topologies characterized by frequent and continuous dynamism. In the algorithmic study of these dynamic networks, the most common model of computation considers a system of agents that communicate synchronously through broadcast, where the network topology is always connected but the communication links can change unpredictably.

A classic assumption is that each agent has a unique ID, and efficient algorithms are known for solving many problems in this context [3, 11, 12, 13, 14, 16]. An alternative model is where agents are anonymous, and are therefore initially indistinguishable. The study of anonymous networks is both practically and theoretically significant, with prolific research spanning several decades [1, 4, 5, 6, 10, 17, 19].

Recent work introduced the use of history trees for studying anonymous dynamic networks with a unique leader [8]. This structure can be constructed using the local views of agents; unlike similar structures, it has a temporal dimension that completely captures a network’s dynamism. The theory of history trees was later extended to networks with no leader and networks with multiple leaders [9].

The introduction of history trees enabled the design of optimal linear-time universal algorithms for all the aforementioned network scenarios (in a sense that will be elucidated in Section 2). However, an important difference between networks with leaders and without leaders is that in the latter it is impossible to perform terminating computations without additional knowledge about the network (such as the number of its agents). In leaderless networks, algorithms can only stabilize on the correct output without explicitly terminating.

In real systems, temporary faults such as memory corruption or message losses are unavoidable; algorithms that withstand such faults are called self-stabilizing. In static anonymous networks, universal self-stabilizing algorithms exist [2]. However, to the best of our knowledge, a similar result for dynamic networks has never appeared in the literature. It is therefore desirable to adapt the techniques in [8, 9] to achieve self-stabilization.²²2Note that terminating algorithms cannot be self-stabilizing, because an adversary could corrupt the initial memory states of all agents, causing them to erroneously terminate with an arbitrary output.

We remark that the stabilizing algorithms from previous work on anonymous dynamic networks use unlimited local memory.³³3Terminating algorithms use a bounded amount of memory, and thus are automatically finite-state. For instance, if history trees are used, all agents are required to continually expand this data structure in their internal memory. It would be beneficial to develop a version of the stabilizing algorithms in [8, 9] that uses finite memory, polynomially dependent on network size, which is crucial for implementation in real systems with limited memory.

A dynamic network is defined as an infinite sequence $𝒢={(G_t)}_{t\ge 1}$, where $G_t=(V,E_t)$ is an undirected multigraph, $V=\{p_1,p_2,\mathrm{\dots },p_n\}$ is a system of $n$ anonymous agents, and $E_t$ is a multiset of edges representing links between agents.⁴⁴4The parallel links in multigraphs can serve as a model for the multi-path propagation of radio waves. Of course, all the results in this paper also apply to networks modeled as simple graphs.

Each agent is assigned an input at round $0$. Agents also have internal states, which are initially determined by their inputs (thus, agents with the same input start in the same state). At every round $t\ge 1$, each agent sends a message to its neighbors in $G_t$ through all its incident links. Every agent creates its message as a function of its current state and sends the same message to all its current neighbors. During round $t$, each agent reads all messages coming from its neighbors (in no particular order). Based on the information therein, the agent updates its internal state according to a local algorithm, the same for all agents. An agent may also return an output at the end of a round. After that, the next round starts.

Note that our network model is synchronous, i.e., all agents are assumed to send and receive their messages simultaneously, and a new round starts at the same time for all agents.

If the outputs of all agents remain unchanged starting at round $t$, the system is said to stabilize in $t$ rounds. If executing a certain algorithm causes a system to stabilize regardless of the inputs assigned to its $n$ agents, we view such an algorithm as computing a function from an $n$-tuple of inputs to an $n$-tuple of outputs.

Not all functions can be computed by a system of anonymous agents. It is known that, without making extra assumptions on the network, the agents can essentially only compute the Input Frequency function, which is the function that returns the percentage of agents that have each input value [9]. Once this fundamental function has been computed, the system can then immediately compute any frequency-based function, i.e., any function that depends only on input percentages, such as the weighted average of the inputs, etc.⁵⁵5If the network has a unique leader or the number of agents is known, computing the Input Frequency function also allows the system to determine the exact number of agents that were assigned each input.

For this reason, any algorithm that allows a system to compute the Input Frequency function for any multiset of inputs assigned to the agents is said to be universal.

History trees were introduced in [8] as a tool of investigation for anonymous dynamic networks; an example is found in Figure 1. A history tree is a representation of a dynamic network given some inputs to its agents. It is an infinite graph whose nodes are partitioned into levels $L_t$, with $t\ge -1$; each node in $L_t$ represents a class of agents that are indistinguishable at the end of round $t$ (with the exception of $L_{-1}$, which contains a single root node $r$ representing all agents). The definition of distinguishability is inductive: At the end of round $0$, two agents are distinguishable if and only if they have different inputs. At the end of round $t\ge 1$, two agents are distinguishable if and only if they were already distinguishable at round $t-1$ or if they have received different multisets of messages during round $t$. (We refer to “multisets” of messages, as opposed to sets, because multiple copies of identical messages may be received; thus, each message has a multiplicity.) The anonymity of a node $v$ in a history tree is the number of agents represented by $v$, denoted as $𝐚(v)$.

Every node (other than the root $r$) has a label indicating the input of the agents it represents. There are also two types of edges connecting nodes in adjacent levels. The black edges induce an infinite tree spanning all nodes, rooted at node $r\in L_{-1}$. The presence of 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 agents represented by the parent node $v$. The red multi-edges represent communications between agents. The presence of 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 agent represented by $v^{\prime }$ receives $m$ (identical) messages from agents represented by $v$.

The view $𝒱$ of an agent $p$ at round $t\ge 0$ is the subgraph of the history tree that is spanned by all the shortest paths (using black and red edges indifferently) from the root $r$ to the node in $L_t$ representing $p$ (Figure 1 shows an example of a view). The node in $𝒱$ representing $p$ at round $t$ is the bottom node of the view; this is the node of $𝒱$ farthest from $r$.

It was shown in [8] that each agent can construct its view of the history tree in real time. To achieve this, each agent is required to send its current view to all its neighbors at every round, and then match-and-merge it with all the views it receives from them. An example of this operation is shown in Figure 2. At every round, the bottom node $v$ of the view also receives a new child $v^{\prime }$, which becomes the new bottom node. After merging an incoming view, a red edge is added from the bottom node of this view to $v^{\prime }$. The multiplicities of such red edges match the number of isomorphic views that are being merged.

As proved in [9], if the network is connected at every round, then the view of any agent at round $2n-2$ contains enough information to compute the Input Frequency function. This is done by finding a counting level, which is a level in the history tree where every node has exactly one child; level $L_2$ in Figure 1 is an example.

For any red edge with multiplicity $m_1>0$ directed from a node $v$ in a counting level $L_t$ to the child of another node $u\in L_t$, there must be a red edge with multiplicity $m_2>0$ from $u$ to the child of $v$. Then, we have $m_1𝐚(v)=m_2𝐚(u)$. By writing the system of such linear equations for the entire level $L_t$ and solving it in terms of a single free variable, we can easily compute the Input Frequency function. Note that the first counting level $L_t$ occurs when $t\le n-2$, and it takes at most $t+n$ rounds for all the nodes in $L_t$ and their children to appear in the views of all agents. Thus, this algorithm stabilizes in at most $2n-2$ rounds.

An algorithm computes a function in a self-stabilizing manner if it does so regardless of the initial states of the agents. That is, even if the states of the agents consist of incorrect history trees, a self-stabilizing algorithm is able to eventually erase all errors and stabilize on the correct output. Clearly, the above algorithm is not self-stabilizing.

An algorithm is finite-state if the states of the $n$ agents in a system executing such an algorithm can be encoded by at most $f(n)$ bits throughout the execution. Since the above algorithm constructs ever-growing views, it is not finite-state.

The algorithm is based on an operation on history tree views called chop, illustrated in Figure 3. Given a view, eliminate the nodes in level $L_0$ (as well as their incident black and red edges) and connect the root to all nodes in level $L_1$ via black edges. As a result, all non-root nodes are shifted by one level: those that were in $L_1$ are now in $L_0$, etc.

After that, we have to ensure that the resulting view is well-formed. Note that every node $v$ in a view $𝒱$ is the bottom node of a maximal view ${𝒱}_v\subseteq 𝒱$, called the sub-view of $𝒱$ at $v$. To complete the chop operation, we repeatedly merge the nodes whose sub-views are isomorphic. This is done level by level, starting from the nodes in $L_0$, then the nodes in $L_1$, etc. As a consequence, when two nodes $u,v\in L_t$ are found whose sub-views ${𝒱}_u$ and ${𝒱}_v$ are isomorphic, they must be siblings. This is because the parents of $u$ and $v$ have isomorphic sub-views as well, and therefore they have already been merged as nodes of $L_{t-1}$.

Merging $u$ and $v$ is done as follows. First we delete one of them, say $u$. The children of $u$ now become children of $v$. The red edges inbound to $u$ are simply eliminated, while the red edges outbound from $u$ are now redirected as outbound from $v$. Specifically, for every $w\in L_{t+1}$, if the red edge $(v,w)$ originally has multiplicity $m\ge 0$ and the red edge $(u,w)$ has multiplicity $m^{\prime }\ge 0$, after merging $u$ and $v$ the red edge $(v,w)$ will have multiplicity $m+m^{\prime }$.

This is justified by the fact that the agents represented by $u$ and $v$ have received identical multisets of messages and are therefore indistinguishable; hence the need to merge the two nodes. Thus, all messages received from agents represented by $u$ and $v$ are now considered identical, and the multiplicities of the corresponding red edges must be added together.

The significance of the chop operation is given by the following result, whose proof is found in [7]. Essentially, chopping a view is equivalent to “forgetting” the first communication round of the network that originated that view.

The pseudocode of our algorithm is found in [7]. The goal is for each agent to construct a coherent view of the history tree of the $2n-2$ most recent rounds, which enables the stabilizing algorithm from [9] to correctly compute the Input Frequency function based on the first visible counting level (cf. Section 2).

If the state of an agent $p$ does not represent a well-formed view of a history tree or represents a view with more than $2n-2$ levels, it is simply re-initialized to a view containing a root and a single child labeled as the input of $p$. When $p$ receives the views of its neighbors, it determines the view with smallest height (including its own) and trims all other views by repeatedly performing the chop operation on them, until all views have the same height. Then, the resulting views are match-and-merged into $p$’s view as usual. After that, if the current view of $p$ has $2n-1$ levels, the oldest level is removed via a chop operation. Finally, if the resulting view contains a counting level, this is used to output the frequencies of all inputs; otherwise, $p$ returns a default output consisting of its own input with $100\%$ frequency.

We will prove that the above algorithm satisfies the required conditions. Observe that, since the network is connected at every round, it takes at most $n-1$ rounds for all agents to have states representing views of the same height. In fact, trimming one’s view to match the shortest incoming view is akin to broadcasting the smallest height of a view across the whole network.⁶⁶6It is well known that the dynamic diameter of a connected network is $d\le n-1$; see [8, 12].

Due to Lemma 1, if the algorithm alternately performs update and chop operations on non-trivial views for $k$ times, the result is the same as chopping all views $k$ times first, and then doing all the update operations. Since all views are kept within $2n-2$ levels, it takes as many initial chops to eliminate all incorrect levels. At the same time, $2n-2$ update operations result in all agents constructing views correctly representing the previous $2n-2$ communication rounds. If follows that all agents return the correct output at any round $t\ge 2n-2$.

The algorithm is finite-state because every (non-initial) state always consists of $O(n)$ levels of a view. If this view is correct, its size is $O(n^3\log n)$ bits. If the view is not correct and exceeds $O(n^3\log n)$ bits in size, the algorithm can chop it until it is sufficiently small. $◀$

The stabilization time of this algorithm is asymptotically optimal, since a lower bound of $2n-O(1)$ rounds was proved in [9], even for algorithms that are not self-stabilizing.

Recall that a self-stabilizing algorithm should tolerate any amount of incorrect data initially present in the agents’ local memory. If such initial data does not encode the view of a history tree, it is definitely incorrect and can be discarded immediately. However, even if an initial state does encode a well-formed view, the information therein may be incorrect and possibly deceiving. We define the garbage coefficient of an agent as the height of the view encoded by its initial state. If its initial state does not encode a well-formed view, its garbage coefficient is defined to be $0$.

We will now describe our self-stabilizing algorithm. Its pseudocode is found in [7]. The structure of this algorithm is similar to the one in Section 3; in particular, the same chop operation is used to gradually eliminate all incorrect levels from every view of the history tree. The main difficulty is that, without knowledge of $n$, it is impossible to determine whether a view has the desired number of $2n-2$ levels.

To overcome this difficulty, our strategy is to chop each agent’s view once every two rounds. As a result, the views grow by one level every two rounds, and eventually acquire the desired amount of correct levels.

To control the chopping of views, the state of each agent is augmented with a binary flag that is toggled between $0$ and $1$ at every round. Every time an agent’s flag becomes $0$, its view is chopped. Accordingly, if the current state of an agent does not encode a well-formed view augmented with a binary flag, the state is discarded and reset to a view of only two nodes (a root with a single child containing the agent’s input) and a flag set to $0$.

An agent’s binary flag is also attached to all messages it sends, alongside its view of the history tree. Upon receiving messages from its neighbors, the agent reduces all views (including its own) to the same height via chop operations, in the same way as the algorithm in Section 3 does. However, this is now extended to all flags, as well. Specifically, we define a function $\mathrm{𝐞𝐯𝐚𝐥}(𝒱,b)$, which takes a view $𝒱$ and a flag $b\in \{0,1\}$, and returns $2h_{𝒱}+b$, where $h_{𝒱}$ is the height of $𝒱$. Let the minimum pair $({𝒱}^{\ast },b^{\ast })$ be the pair that minimizes $\mathrm{𝐞𝐯𝐚𝐥}$ among the ones received from its neighbors, as well as the agent’s own pair. Then, all views received by the agent, as well as the agent’s own view, are chopped until they have the same height as ${𝒱}^{\ast }$. After that, the incoming views are match-and-merged into the agent’s view, as usual. In addition, the agent’s own flag is set to $b^{\ast }$. The flag is then toggled, and if it becomes $0$ the agent’s view is chopped once. This protocol ensures proper synchronization among agents.

Finally, if the agent’s resulting view contains a counting level, this level is used to compute and output the frequencies of all inputs (as explained in Sections 2 and 3); otherwise, the agent returns a default output consisting of its own input with $100\%$ frequency.

The correctness of this algorithm is straightforward, given the property of the chop operation established in Lemma 1 and the observations in the proof of Theorem 2. It remains to show that the stabilization time is $\max \{4n-2h,2h\}$.

Recall that the garbage coefficient of an agent $p$ is defined as the number of levels of the view initially encoded by the state of $p$. Every time a chop operation is performed on the view of $p$, the number of these levels is decreased by one unit. We define the leftover garbage of $p$ at round $t\ge 0$ as the garbage coefficient of $p$ minus the number of times the view of $p$ has been chopped up to round $t$ (or $0$ if this number is negative). Thus, the leftover garbage measures how many initial levels are still present in the view of an agent. We define $h_t$ as the minimum leftover garbage at round $t\ge 0$ across all agents. Clearly, $h_0=h$.

As already remarked in the proof of Theorem 2, it takes at most $n-1$ rounds for all agents’ views to have the same height and all their flags to be the same (essentially, the algorithm performs a broadcast of the smallest value returned by $\mathrm{𝐞𝐯𝐚𝐥}$). In fact, every time two agents communicate, their leftover garbage is equalized. Thus, within $n-1$ rounds, all agents have the same leftover garbage. Also, every two rounds the leftover garbage of any agent with smallest $\mathrm{𝐞𝐯𝐚𝐥}$ is reduced by one unit (unless it is already $0$). In other words, $h_t$ is decremented every two rounds until it reaches $0$. In particular, $h_{2h}=0$.

Let us assume that $h\le n$; we will prove that the stabilization time in this case is $\max \{4n-2h,2h\}=4n-2h$. Since $h_{2h}=0$, after $\max \{2h,n\}\le 4n-2h$ rounds all agents have no leftover garbage. We conclude that, after $2(2n-h)=4n-2h$ rounds, every view has $h+(2n-h)=2n$ levels, which are all correct. From this point onward, each agent’s view will consistently represent at least $2n$ previous communication rounds of the network, and hence every agent will return the correct output.

Let us now assume that $h>n$; we will prove that the stabilization time in this case is $\max \{4n-2h,2h\}=2h$. By the previous argument, after $\max \{2h,n\}=2h$ rounds, all agents have no leftover garbage. At this time, there are $2h>2n$ correct levels in every agent’s view, and so their outputs are all correct, and will be correct in all subsequent rounds. $◀$

Observe that our algorithm’s stabilization time exhibits a linear dependence on the minimum garbage coefficient $h$. We conjecture that this cannot be avoided in dynamic networks, and so this stabilization time is asymptotically optimal. Nonetheless, it is remarkable that the best stabilization time of our algorithm is achieved when $h=n$ (as opposed to $h=0$).

Before we state our algorithm, we first have to define a generalized notion of view. This is necessary because we will have to deal with situations where views of different heights must be match-and-merged into each other. The result of such an operation is illustrated in Figure 4. As usual, when an agent receives some views from its neighbors, it attaches a child $v^{\prime }$ to the bottom node of its own view, and then match-and-merges the incoming views, connecting their bottom nodes to $v^{\prime }$ via red edges. If the incoming views have arbitrary heights, the resulting view may not have only red edges connecting a level to the next, but also red edges spanning any number of levels, going downward or upward.

Formally, a generalized view can be defined recursively as the result of the above update operation performed on arbitrary generalized views, where the base case is the trivial view consisting of the single root node. Accordingly, we define the bottom node of a generalized view as its unique sink, i.e., the unique node with no outgoing red or black edges (where black edges are understood as being directed away from the root). By definition, the bottom node of a view represents the agents that currently possess this view.

The notion of sub-view of a generalized view $𝒱$ at a node $v$ is as in Section 3: it is the maximal view included in $𝒱$ whose bottom node is $v$. As usual, a node $v$ in $𝒱$ represents all agents that had a view isomorphic to the sub-view of $𝒱$ at $v$ at the end of some round.

From now on, when no confusion may arise, the term “generalized” will often be omitted.

Since our algorithm allows agents to skip updating their states, it follows that they are no longer constructing views of the history tree of the network as defined in Section 2. Nonetheless, it is useful to define a structure that may act as a global reference incorporating all the (generalized) views that the agents are constructing.

The collective tree at round $t$, denoted as ${\mathscr{H}}_t$, is the structure obtained by match-and-merging together all the views constructed by the agents in a network up to round $t$. Of course, ${\mathscr{H}}_t$ depends on the local algorithm being executed by the agents, which affects the way they construct their views. For example, under the standard stabilizing algorithm outlined in Section 2, the collective tree ${\mathscr{H}}_t$ is simply the history tree of the network truncated at level $L_t$. Under the finite-state algorithm that we are going to describe in this section, ${\mathscr{H}}_t$ is constructed from generalized views, and may have little in common with the history tree.

Another feature of our finite-state algorithm is the following: Even if an agent updates its state in a given round, it may still choose to selectively discard some incoming messages from certain neighbors. However, there is a caveat: The algorithm guarantees that, if two agents send each other messages for a round, either both agents discard each other’s messages or neither does.

Therefore, in any collective tree, whenever a node $v$ has an outgoing red edge of multiplicity $m_1>0$ to a child of a node $u$, then symmetrically $u$ has an outgoing red edge of multiplicity $m_2>0$ to a child of $v$. Moreover, there are a child of $v$ and a child of $u$ that appear in the collective tree at the same round, i.e., the round in which an agent represented by $v$ first exchanges messages with one represented by $u$.

With the above notation, $v$ and $u$ are said to be an exposed pair if they both have a unique child. In this case, we have the following equation, as already noted in Section 2:

The anonymity $𝐚(x)$ is defined, as usual, as the number of agents represented by the node $x$.

We will now define a generalized notion of counting level. Recall from Section 2 that a counting level is a level of the history tree where all nodes have a unique child. A counting level’s outgoing red edges describe all interactions that occur in the corresponding round, and this information can be used to compute the Input Frequency function.

We define a cut in a collective tree ${\mathscr{H}}_t$ as a set of nodes $C$ such that, for every leaf $f$ in ${\mathscr{H}}_t$, the unique black path from the root of ${\mathscr{H}}_t$ to $f$ contains exactly one node of $C$.

Let $G$ be the undirected graph on the nodes of ${\mathscr{H}}_t$ whose edges are the exposed pairs. A cut $C$ in ${\mathscr{H}}_t$ is said to be a counting cut if $C$ induces a connected subgraph of $G$. Figure 5 (left) shows two counting cuts consisting of the nodes labeled $A$ and $B$, respectively. Clearly, in the history tree of a connected network, the notions of counting level and counting cut coincide.

In a collective tree, a cut $A$ dominates a cut $B$ if every node of $B$ has an ancestor in $A$. This is the case in Figure 5 (left), where the counting cut $A$ dominates the counting cut $B$.

The asymmetric and transitive properties of the dominance relation are obvious from the definition. We only have to prove that any two distinct counting cuts $A$ and $B$ in the same collective tree are comparable, i.e., one dominates the other.

Assume the opposite for a contradiction. Then, without loss of generality, there is a node $v\in A$ with a descendant $w\in B$. Moreover, there are two nodes $u\in B$ and $z\in A$ such that either $u$ is an ancestor of $z$ or $u=z$; both cases are sketched in Figure 5 (right).

As pointed out in 4, the two children of an exposed pair make their appearance in the collective tree at the same round. Since a counting cut consists of a connected set of exposed pairs, all the children of its nodes appear in the collective tree at the same round.

Thus, the children of $v$ and $z$ are both created at round $t$, and the children of $u$ and $w$ are both created at round $t^{\prime }$. Since the child of $v$ is unique, it is an ancestor of the child of $w$, and therefore . Similarly, the child of $u$ is either an ancestor of the child of $z$ or they coincide (if $u=z$). As a consequence, $t^{\prime }\le t$, which yields , a contradiction. $◀$

Due to Lemma 5, if a collective tree has at least one counting cut, then there is a well-defined dominant one, whose nodes are closest to the root.

The definitions of counting cut and dominance extend verbatim to generalized views. However, if an agent has a counting cut $C$ in its view $𝒱$, the nodes of $C$ as embedded in the collective tree ${\mathscr{H}}_t$ are not necessarily a counting cut. For instance, although every node of $C$ has a unique child in $𝒱$, it may have multiple children in ${\mathscr{H}}_t$, as some of them may be missing from $𝒱$. Thus, Equation 1, which we established for exposed pairs in a collective tree, may not hold in a view. Similarly, 4 and 5 may not hold in a view.

We are finally ready to provide our finite-state algorithm. Its pseudocode is in [7]. Each agent sends its view to all its neighbors and updates its own view by match-and-merging incoming views as usual, with one exception: If the view of an agent contains a dominant counting cut (i.e., a counting cut that dominates all others in the view), then all incoming views that contain the same dominant counting cut are discarded. Moreover, if all incoming views are discarded, the agents skips updating its own view altogether for that round (hence it does not even add a child to the bottom node).

The rationale is that an agent with a dominant counting cut “believes” that this cut is dominant for all agents and is sufficient to compute the Input Frequency function. Therefore, this agent deems unnecessary to further update its view, unless its belief is proven incorrect.

To make our algorithm more precise, we have to define the concept of isomorphism between counting cuts in different views. A counting cut $C$ in a view $𝒱$ is isomorphic to a counting cut $C^{\prime }$ in a view ${𝒱}^{\prime }$ if there is a bijection $f:C\to C^{\prime }$ such that, for every $v\in C$, the sub-view of the unique child of $v$ in $𝒱$ is isomorphic to the sub-view of the unique child of $f(v)$ in ${𝒱}^{\prime }$. This definition extends verbatim to collective trees.

According to the algorithm, if two agents have dominant counting cuts in their respective views, and these cuts are isomorphic, both agents discard each other’s messages. In all other cases (i.e., if either of them does not have a counting cut, or does not have a dominant counting cut, or both have dominant counting cuts which are not isomorphic), the agents use each other’s messages to update their respective views. Hence 4, which relies on the fact that interactions between pairs of agents occur symmetrically and simultaneously, is indeed correct, and so are its consequences, such as Lemma 5.

If, due to this rule, an agent ends up discarding all messages incoming from its neighbors, it does not update its view at all, i.e., it does not even add a child to the bottom node of its view (cf. Figure 2). There is only one trivial exception: If an agent’s view consists of a single node $r$, then this is necessarily round $0$; the agent does not receive any messages in this round, but it still updates its view by adding a child to $r$ and labeling it as its input.

At the end of every round, if an agent’s view has a dominant counting cut, this cut is used to compute the Input Frequency function by repeated application of Equation 1; the result is then returned as output by the agent. Otherwise, the agent simply returns the default output: its own input with a frequency of $100\%$.

There are several challenges to proving the correctness of this relatively simple algorithm. Even if an agent has a dominant counting cut in its view, using it to compute the Input Frequency function may lead to incorrect results, because Equation 1 might not hold in that view. Additionally, the rule that permits agents to discard messages could potentially result in a situation where all agents have an incorrect dominant counting cut, yet none of them updates its view, preventing any progress from being made.

The next lemma addresses these difficulties (its proof is found in [7]). We say that two agents agree on a counting cut $C$ at round $t$ if both of their views at round $t$ contain isomorphic copies of $C$. There is total agreement on $C$ if all agents in the system agree on $C$.

Lemma 6 provides a sufficient condition for the algorithm to be correct. Thus, we only have to prove that eventually total agreement on a dominant counting cut is achieved.

To begin with, the collective tree does not have any counting cuts, except in the trivial case where all agents have the same input (then the root of the collective tree by itself constitutes a counting cut). We also remark that the existence of a counting cut in the collective tree does not necessarily imply the presence of a counting cut in any individual agent’s view. Next, we will study the way counting cuts are formed in the collective tree and how they eventually become counting cuts in the agents’ views.

A branch in a tree is any path from the root to a leaf. Thus, the number of branches in a tree is precisely the number of its leaves. We say that a branching occurs in the collective tree during round $t$ if ${\mathscr{H}}_t$ has more branches than ${\mathscr{H}}_{t-1}$. The collective tree loses a counting cut $C$ at round $t$ if $C$ is a counting cut in ${\mathscr{H}}_{t-1}$ but not in ${\mathscr{H}}_t$. Similarly, the collective tree acquires a counting cut $C$ at round $t$ if $C$ is a counting cut in ${\mathscr{H}}_t$ but not in ${\mathscr{H}}_{t-1}$.

The above definitions straightforwardly extend to views.

We will only prove our claim for collective trees, as the proof for views is identical. Observe that all the red edges in ${\mathscr{H}}_{t-1}$ also appear in ${\mathscr{H}}_t$. Thus, the only way a counting cut $C$ may be lost at round $t$ is if a node of $C$ acquires an additional child in ${\mathscr{H}}_t$ or if $C$ is no longer a cut in ${\mathscr{H}}_t$, which therefore has a branch that does not intersect $C$. Clearly, both scenarios imply that a branching occurs at round $t$ in the collective tree. $◀$

The proof of the next lemma is found in [7].

Suppose that two agents $p$ and $p^{\prime }$ send each other messages at round $t$, which are not discarded. Let $C$ be a counting cut in the view $𝒱$ of $p$ at the end of round $t-1$, and assume that the view ${𝒱}^{\prime }$ of $p^{\prime }$ at the end of round $t-1$ does not contain $C$. At the end of round $t$, there are four possibilities:

• $\mathrm{■}$

  The view of $p$ loses $C$ and the view of $p^{\prime }$ acquires $C$. In this case, a branching occurs in the view of $p$, due to Lemma 7.

• $\mathrm{■}$

  The view of $p$ loses $C$ and the view of $p^{\prime }$ does not acquire $C$. Also in this case, a branching occurs in the view of $p$, due to Lemma 7.

• $\mathrm{■}$

  The view of $p$ does not lose $C$ and the view of $p^{\prime }$ acquires $C$.

• $\mathrm{■}$

  The view of $p$ does not lose $C$ and the view of $p^{\prime }$ does not acquire $C$.

We will prove that, in the latter case, a branching occurs in the view of $p^{\prime }$.

Let $𝒯$ be the tree obtained by match-and-merging $𝒱$ and ${𝒱}^{\prime }$. Since the view of $p$ does not lose $C$, it follows that $𝒯$ contains $C$ as a counting cut. However, the view of $p^{\prime }$ fails to acquire $C$ as a counting cut, which implies that other agents send their views to $p^{\prime }$ at round $t$, causing $𝒯$ to lose $C$. Hence, a branching must occur in the view of $p^{\prime }$, as argued in the proof of Lemma 7. $◀$

We say that a counting cut $C$ in an agent’s view $𝒱$ at round $t$ is undominated if no counting cut in $𝒱$ dominates $C$. In other words, $C$ is a maximal element in the dominance partial order within $𝒱$.⁷⁷7As previously pointed out, Lemma 5 does not necessarily hold in a view, hence the term “partial order”.

Let the view $𝒱$ at round $t$ contain the undominated counting cut $C$, and let a view ${𝒱}^{\prime }$ at round $t^{\prime }$ contain both $C$ and a counting cut $C^{\prime }$ that dominates $C$. Then, the nodes of $C^{\prime }$ are ancestors of the nodes of $C$, and hence appear in every view that contains $C$. We infer that $𝒱$ also contains $C^{\prime }$, contradicting the assumption that $C$ is undominated in $𝒱$. $◀$

The algorithm makes $p$ and $p^{\prime }$ discard each other’s messages only if they have the same dominant counting cut at the beginning of round $t$. In this case, since $C$ is undominated in the view of $p$, then $C$ is dominant. However, by assumption the view of $p^{\prime }$ does not contain $C$, and therefore it does not have the same dominant counting cut as the view of $p$. $◀$

We conclude this section with a proof of correctness of our finite-state algorithm.

Since each agent starts with a view containing a single branch, a branching in its view may occur at most $n-1$ times (note that the leaves represent disjoint and non-empty sets of agents). Thus, in total, the agents’ views may branch at most $n(n-1)$ times. For a similar reason, a branching in the collective tree may occur at most $n-1$ times.

We classify the rounds into three types:

1. (i)

   Rounds at the beginning of which no agent’s view has a counting cut.

2. (ii)

   Rounds at the beginning of which some agents’ views have a counting cut, but there is no total agreement on any counting cut.

3. (iii)

   Rounds at the beginning of which there is total agreement on a counting cut.

During rounds of type (i), according to our algorithm, no messages are discarded. In each of these rounds, if no branching occurs in the collective tree, a new counting cut is acquired by the collective tree, due to Lemma 8. If such a counting cut $C$ already exists in the collective tree at the beginning of a round of type (i), then either $C$ is lost by the collective tree (and a branching occurs, due to Lemma 7) or progress is made toward total agreement on $C$ by the agents. Specifically, for every child $v$ of a node in $C$, at every round of type (i) where $C$ is not lost, at least one more agent’s view acquires $v$ (since the network is always connected and no messages are discarded). Thus, after $n-1$ (not necessarily consecutive) rounds of type (i) where $C$ is not lost, total agreement on $C$ is reached.

So, if no branching occurs, it takes $n$ rounds of type (i) for a counting cut to be acquired by the collective tree and then be acquired by all agents’ views. This cut may be lost during the process if a branching occurs in the collective tree, but this may happen only $n-1$ times. Therefore, there can be at most $n^2$ (not necessarily consecutive) rounds of type (i) before total agreement on a counting cut is reached.

Let us consider now the rounds of type (ii). Let $C$ be any undominated cut in an agent’s view. Due to Lemma 7, in every view that loses $C$ a branching must occur. Moreover, since the network is always connected, there is at least one agent $p$ whose view contains $C$ that exchanges messages with an agent $p^{\prime }$ whose view does not contain $C$. Due to Lemma 11, these messages are not discarded. Hence, by to our previous analysis of agent interactions and by Lemma 9, a branching occurs in the view of $p$ or in the view of $p^{\prime }$, or the counting cut $C$ is acquired by the view of $p^{\prime }$ and is not lost by the view of $p$. Recall that, by Lemma 10, $C$ remains undominated in any view that acquires it, and therefore the same argument holds for the next rounds of type (ii).

Thus, at every round of type (ii), either the number of agents whose views contain $C$ increases, or it remains stable and at least one branching occurs in the view of some agent, or it decreases by $k>0$, and at the same time at least $k$ branchings occur. $C$ may be lost by all views, but then another undominated counting cut will replace it at the next round of type (ii). Since the total number of branchings in agents’ views may be at most $n(n-1)$, we conclude that there can be at most $2b_1+n$ (not necessarily consecutive) rounds of type (ii), with $b_1\le n(n-1)$, before total agreement on a counting cut is reached. Indeed, the number of agents’ views containing a same counting cut must start from $0$ and reach $n$, and this number is decremented (and then incremented again) $b_1\le n(n-1)$ times.

It follows that, eventually, total agreement on a counting cut $C$ is reached, and the following round will be of type (iii). By Lemma 6, $C$ is also a counting cut in the collective tree. Without loss of generality, we may assume that $C$ is the dominant counting cut in the collective tree. For if it were not, the dominant counting cut (which exists by Lemma 5) would consist of ancestors of nodes of $C$, which are contained (as well as their children) in all agents’ views.

It is easy to see that $C$ is never lost by any agent’s view, and therefore all subsequent rounds will be of type (iii). Indeed, in the collective view, all agents are represented by descendants of children of nodes in $C$. Hence, none of the new nodes that are added to the collective view may ever cause $C$ to be lost as a counting cut. Similarly, no view may acquire such a node either, or the same node would also appear in the collective tree.

Observe that $C$ is undominated in all views. Indeed, assume that a counting cut $C^{\prime }$ dominates $C$ in some agent’s view. Since $C^{\prime }$ consists of ancestors of nodes of $C$, and $C$ appears in all views, it follows that $C^{\prime }$ is a counting cut in all views, and therefore it is a counting cut in the collective view as well (by Lemma 6), contradicting the fact that $C$ is dominant in the collective view.

Consider an agent’s view $𝒱$ where $C$ is not dominant. Since $C$ is undominated, there must be another counting cut $C^{\prime }$ in $𝒱$ that intersects $C$. There cannot be total agreement on $C^{\prime }$, for otherwise $C^{\prime }$ would be a counting cut in the collective tree (by Lemma 6), contradicting the fact that different counting cuts in the collective tree are disjoint (by Lemma 5).

Since $C$ is undominated in all views, no counting cut other than $C$ can be dominant. Therefore, none of the messages between agents whose view contains $C^{\prime }$ and agents whose view does not contain $C^{\prime }$ are discarded (because such views cannot have the same dominant counting cut). Thus, as we argued for rounds of type (ii), at every round either the number of agents whose views contain $C^{\prime }$ increases, or it remains stable and at least one branching occurs in some view, or it decreases by $k>0$ and at least $k$ branchings occur. Since there can never be total agreement on $C^{\prime }$, any such counting cut will be lost by all views within $2b_2+n$ rounds, where $b_2$ is the number of branchings that occur in agents’ views during these rounds. Of course, $b_1+b_2\le n(n-1)$.

Thus, eventually $C$ becomes the dominant counting cut in all views; by Lemma 6, at this point all agents return the correct output. Moreover, since all agents have now the same dominant counting cut, they stop updating their states and keep returning the same correct output. In total, this takes at most $(n^2)+(2b_1+n)+(2b_2+n)\le 3n^2$ rounds. Note that a history tree with $O(n^2)$ levels can be encoded in $O(n^4\log n)$ bits, implying that the algorithm is finite-state. $◀$