WorksComputer Science
Computation in Anonymous Directed Dynamic Networks: Exact Worst-Case Termination Time and Network-Wise Intractability
Abstract
We determine the exact round complexity of Counting in anonymous directed dynamic networks. Agents have no identifiers, but of them are designated as leaders. Every agent knows and its own leader status, while the population size is unknown and has to be determined by the agents. Communication proceeds in synchronous rounds; the directed communication graph may change arbitrarily and unpredictably from one round to the next, but is assumed to remain strongly connected. We solve Counting with a distributed algorithm that makes every agent output and halt after a number of rounds equal to The algorithm works even for networks with loops and parallel arcs and even when agents learn their outdegree only after sending. We prove that this bound is worst-case tight over directed multigraphs for every and with . Moreover, the local computation is polynomial (provided that each communication multigraph has at most arcs): in every round, each agent solves at most one linear system with up to variables. By standard techniques, solving Counting also enables the evaluation of any computable function of the multiset of agents' input values within communication rounds. The bound above optimizes the worst case over all networks. For an individual network, we show that even deciding whether an agent already has enough local information to determine is -complete (provided that the numbers of parallel arcs are encoded in binary). Thus, worst-case-optimal Counting admits polynomial local computation, whereas exact network-wise optimization is intractable under standard complexity assumptions.
Formal verification. Formal proofs in Lean of all results stated in this paper are available at https://github.com/gadiluna/ADN_lean.
Introduction
Modern distributed systems, including networks of wearable devices, smart devices, and sensors, are characterized by continually changing communication topologies. Understanding the computational foundations of such systems is a central motivation for the study of dynamic networks, in which communication links evolve over time [3, 6, 22]. In this abstraction, algorithms cannot rely on a fixed topology or wait for the network to become stable.
Another fundamental line of research concerns anonymous systems, in which agents have no unique identifiers [2, 26]. This abstraction makes it possible to study coordination without requiring a mechanism for assigning and maintaining global identities. This property is attractive in highly dynamic environments and in applications where identifiers raise privacy concerns. COVID-19 contact-tracing apps illustrate these concerns: even rotating random identifiers did not eliminate worries about tracking and the disclosure of personal behavior [4, 30]. Anonymous models are also used to study insect colonies and other biological systems [15].
Nonetheless, anonymity creates the obstacle of symmetry: agents cannot use identities to distinguish information originating from different participants; this limitation can make basic tasks such as leader election impossible [2]. A standard symmetry-breaking assumption is to designate one agent, or a known nonzero number of agents, as leaders; this enables non-trivial computations [13, 26].
The Counting problem consists of determining the total number of agents in the network. Knowledge of , in turn, enables the evaluation of any computable aggregate function of the agents’ input values and the design of termination conditions [22]. However, terminating Counting poses a fundamental challenge: deciding whether the information observed so far accounts for the entire network. An agent may obtain a correct estimate without being able to rule out a larger, observationally indistinguishable network; the difficulty is therefore not only to compute correctly, but to know when the available evidence excludes every other network size.
History trees were introduced to study deterministic computation in anonymous undirected dynamic networks [11]. These combinatorial structures record how agents with identical observation histories become distinguishable as communication proceeds. With a unique leader, this framework yields an algorithm that solves Counting in rounds, also enabling the computation of every deterministically computable function within the same number of rounds [11]. Subsequent work extended the framework to multiple leaders, giving polynomial-round terminating algorithms, and obtained linear-round stabilizing algorithms for leaderless Average Consensus [13]. These results established Counting as a central problem in anonymous dynamic networks.
In this paper, we extend the history-tree approach to obtain worst-case-optimal terminating Counting in anonymous directed dynamic networks. Directionality breaks the reciprocity between sending and receiving, invalidating a basic assumption used by techniques developed in previous work [11, 13]. Besides posing interesting theoretical challenges, directed communication arises in wireless sensor networks with heterogeneous transmission ranges, where one device may receive another’s messages without direct communication in the reverse direction [29].
We consider agents communicating in synchronous rounds over directed graphs that may change arbitrarily, subject only to strong connectivity in every round. This is the directed version of the 1-interval connectivity condition considered in [22]. Every agent knows the number of leaders, but not the network size , and broadcasts the same message along all outgoing arcs. We assume only late outdegree awareness: an agent learns how many outgoing arcs it has after sending its message.2 In this setting, the best previously available terminating Counting algorithm terminates in at most rounds, even when the communication graphs are simple [32].
Contributions
We close the aforementioned exponential gap by determining the exact worst-case termination time of Counting for every network size and every known nonzero number of leaders. We give a Counting algorithm that works in all anonymous directed dynamic networks of agents and has optimal worst-case complexity for every number of leaders (§ 3). Our algorithm terminates in rounds when ; in rounds when and ; and in rounds when and . The algorithm works even in multigraphs, and its local computational complexity is polynomial in , assuming that the network has at most arcs in every round. Moreover, for every combination of and , we show an exact lower-bound example that matches the upper bound given by our algorithm in the directed multigraph model (§ 3.2).
By standard history-tree techniques [11, 13, 32], our algorithm can be extended to compute the multiset of agents’ input values, and hence any computable function of it, within communication rounds in every case (Section C).
Furthermore, we consider the local decision underlying earlier termination: whether an agent has enough information to determine . We prove that this test is coNP-complete even for networks with a unique leader, provided that the numbers of parallel arcs are encoded in binary (§ 4). Thus, worst-case-optimal Counting admits polynomial local computation, whereas even the basic decision needed for exact network-wise optimization is intractable under standard complexity assumptions.
tbl:1 compares our results with the best-known results for undirected and directed networks.
Our algorithm closes the gap between the upper bound and the lower bound for single-leader terminating Counting in undirected networks left in [11, 13, 32]. It also shows that terminating Counting is possible in a linear number of rounds even in anonymous directed dynamic networks, closing the exponential termination gap left in [32].
Our upper bound for also applies to undirected networks, improving the polynomial bounds of [13, 19] to a bound linear in regardless of . In particular, it removes the quadratic dependence on in the upper bound of [13] and resolves the asymptotic dependence on asked about in [32]. In the directed model, our matching lower bound also strengthens the previous bound of roughly rounds [13] to . Thus, somewhat surprisingly, in the directed model with , a second leader saves one round, and further leaders give no additional worst-case improvement.
We remark that, in dynamic networks with unique identifiers, agents can solve Counting in rounds by repeatedly broadcasting all identifiers they know [22]. In fact, all agents terminate at round if each halts at the first round in which it knows at most identifiers. Our results show that the price of anonymity is at most additional rounds, even in directed networks. A more detailed discussion of Counting in networks with and without identifiers appears in § 5.
Technical Overview
We use the history-tree framework introduced in [11]. A history tree describes the evolution of a dynamic network through groups of agents with identical observation histories and the communication between these groups. Each node represents one such group; as new observations distinguish agents within it, the node branches into children representing the resulting groups. Each agent reconstructs a portion of the history tree from its own observations; this portion is called its vista.
Our algorithm works directly on this tree representation. Each agent tests candidate network sizes against its vista, using the recorded communication to compute candidate sizes for the represented groups and checking them against the way groups split and the known number of leaders.
The key new ingredient in the proof is a notion of credit assigned to history-tree nodes. Credit provides a common budget for the rounds examined by the test and the branching in a vista. We
| Network model | Leaders | Termination bound | Reference |
| Undirected multigraphs | [11] | ||
| Undirected multigraphs | [13] | ||
| Directed simple graphs | [32] | ||
| Directed multigraphs | This work | ||
| Directed multigraphs | This work | ||
| Directed multigraphs | This work |
caption: Deterministic terminating Counting results in anonymous dynamic networks of unknown size and known leader count . The bounds from this work are tight; the others are upper bounds.
:::
show that an underestimated network size supplies too little credit to explain both, ruling out premature termination. Credit is used only in the analysis, not maintained by the agents.
History trees are also instrumental in proving coNP membership for the problem of deciding whether an agent’s local information determines the network size. They can serve as certificates that this information is insufficient, although establishing polynomial bounds on certificate size and verification time requires careful work.
For coNP-hardness, we reduce from the complement of Exact Cover by 3-Sets [14], constructing a network with one leader and using history trees to describe its vista. The same vista can arise in a network of a different size exactly when the instance has an exact cover.
Model and History Trees
Network. A dynamic network is a sequence of directed multigraphs on a fixed set of agents. Self-loops and parallel arcs are allowed. A fixed set consists of the leaders; write . For , let be the multiset of arcs of from to . Every is strongly connected: for each nonempty proper set ,
Computation. Every agent runs the same deterministic algorithm, receives as a common input, and starts in state if it is a leader and otherwise. An agent is either active or halted; initially, all agents are active. Communication round uses the graph . Every active agent observes a multiset containing, for every active agent , one copy of for each arc from to in . Equivalently, each active agent sends its current state along every outgoing arc. Agent learns its outdegree only after this communication. It then sets its new state to and computes , where means that it produces no output in this round. If , the agent outputs and halts; it neither communicates nor updates its state thereafter. An algorithm solves the Counting problem if, for every , every dynamic network on agents, and every nonempty leader set , all agents eventually output . Its termination time on a network is the first round by which every agent has halted. State size and local computation are unrestricted unless stated otherwise. When measuring local computation, we assume that an agent is given each distinct received state only once, together with its multiplicity written in binary.
Indistinguishability classes. Informally, two agents are indistinguishable after rounds if no deterministic algorithm can place them in different states by then. We define the *indistinguishability classes by a sequence of successively finer partitions of , where refines for every . Initially, . The partition groups agents by leader status: (or if ). For , agents and belong to the same class of precisely when they belonged to the same class of , have the same outdegree , and, for every class , have equally many incoming arcs from agents in : that is, (note that these arcs need not come from the same agents). An induction on shows that, for every deterministic algorithm, agents in the same class of necessarily have the same state after rounds. Thus an observer cannot tell agents in the same class apart by their messages.
History tree. The history-tree data structure was introduced in [11] to study how and when anonymous agents become distinguishable. The history tree of a network , with leader set , has levels . For each and each indistinguishability class , level contains one abstract node representing the agents in . The fiber of , denoted by , is the set . We denote the set of nodes at level by . For , a node is a leader node if , and a nonleader node otherwise. The anonymity of is defined as .
The parent of a node , with , is the unique node such that . These parent-child relations form a rooted tree whose edges are called the black edges. The history tree also contains red edges, which represent messages (refer to Figure 1). Conventionally, both black and red edges point away from the root. For , , and , all agents have the same number of incoming arcs from agents in . Whenever this number is positive, the history tree contains a red edge from to of multiplicity . The agents in also have a common outdegree ; we place this label on the black edge from ’s parent to .
Figure 1. Four rounds of a dynamic network and its history tree. Blue fill denotes leader agents and leader nodes; dashed blue outlines enclose nonsingleton fibers. Green shading highlights the vista of the agents represented by . Black-edge labels are outdegrees and red-edge labels are multiplicities; labels equal to 1 are omitted.
Vistas. Fix an agent at round , and let be the node whose fiber contains . The vista of is the subgraph of the history tree induced by all nodes that lie on a directed path from the root to , using black and red edges indifferently. The node itself, which is the vista’s unique node at level , is called the bottom node of . Vistas are considered up to isomorphism preserving edge types and red multiplicities, the outdegree labels on black edges, and the leader or nonleader status of every nonroot node. By construction, two agents are represented by the same node in exactly when their vistas at round are isomorphic.
As long as all agents are active, each agent can maintain its vista as its state [32]. In each round, it match-and-merges its previous vista with the vistas it observes, then adds the new bottom node, red edges, and outdegree label. The stored vista includes the edge labels and the leader or nonleader status of each nonroot node, but not the fibers or anonymities of its nodes. Since the root represents all agents, Counting amounts to determining its anonymity.
Full levels. For , let be level of , namely the set of its nodes that belong to . These nodes are visible to at level , whereas the nodes in are hidden. We call full if , that is, if it contains every history-tree node at that level.
The prefix ending at is the restriction of to the levels . Equivalently, it is obtained by match-and-merging the round- vistas of all agents represented by nodes in . This prefix is full if is full. This also makes every earlier level full, since every node on such a level has a descendant at level and every visible node brings all its ancestors into the vista.
Properties of History Trees
We list four properties of history trees and their vistas, which follow directly from their definitions. As above, denotes level of a history tree, and denotes level of a vista .
H1. Disjoint refinement. For , every has a parent in , and the fibers of the nodes in are pairwise disjoint. Consequently, for every ,
The first inequality is an equality exactly when every child of is visible; the second is an equality exactly when is full.
H2. Leader accounting. The fiber of every node at level consists entirely of leaders or entirely of nonleaders, and every child of that node has the same leader status as its parent. Therefore,
with equality on every full level.
H3. Flow-balance equations. Red multiplicities and outdegree labels count communication arcs exactly: for , , and ,
Hence, counting the arcs leaving by their heads and by their tails gives
H4. Delay until a level is full. For every vista and ,
Indeed, trace the vista backward from its bottom node. Parent edges retain all represented agents; if some agents are still unrepresented, strong connectivity gives an arc from one of them to a represented agent. The corresponding red edge makes the sender’s node visible one level earlier. Thus backward steps suffice to represent everyone, proving H4. A formal proof appears in Lemma 5 in Appendix C (see also [11 Corollary 4.3] for undirected networks).
Flat Levels
For , a level of a vista is flat if every node in has exactly one child in .
Lemma 1. Let be a full and flat level of a vista, with . The flow equations on , together with , uniquely determine the anonymities of the nodes of .
An equivalent statement is found in [32 Section 3.3]; Section A gives a self-contained proof. Note that the lemma alone does not yield a terminating Counting algorithm. An agent can check whether a level of its vista is flat, but may not know whether it is full and hence whether the lemma applies (see [13 Section 5.1] for examples where naive termination strategies fail).
Worst-Case Terminating Counting
In Section 3.1, we give the core algorithm, which terminates in rounds.3 Section 3.2 improves this bound when or , and proves matching lower bounds.
The Core Algorithm
Outline. Every agent constructs its vista and, for , tests candidate at round , using the prefix ending at . We will prove that every is rejected, whereas is accepted. The test consists of the following steps.
Check the visible structure. Reject unless contains the leader node, each with contains at most nodes, and every node in , for , has a child in . Reject if none of is flat.
Choose the anchor. Let , with , be the largest index such that is flat. We call the anchor. Clearly, and contain the same number of nodes.
Solve the anchor. Introduce one unknown for each node , and solve the flow equations for , with both sums restricted to nodes in , together with
Reject unless this system has a unique solution over . Then reject unless every in this solution is a positive integer and . We call the resulting values the candidate anonymities of the nodes of .
Propagate backward. Use disjoint refinement to propagate the candidate anonymities backward, and verify that they satisfy the flow-balance equations at every earlier level. Namely, for and , set
Reject unless, for every and ,
Check the suffix. For each , let be the number of its descendants in , counting itself when . Reject if for some . Otherwise, accept , output , and halt.
Thus a test solves only one linear system over . Everything else consists of counting nodes, following parent-child relations, and checking the flow equations already recorded in the vista.
Credit. To prove the correctness of this algorithm, we assign a credit to every node in the prefix ending at the anchor . Intuitively, this credit is the part of its candidate anonymity that can be matched with actual agents in its fiber after reserving one agent in that fiber as a representative:
The credit is used only in the proof, since the actual anonymities are unknown to the agents. For , let be the total credit on . In the following three lemmas and their proofs, we assume that candidate passes Steps 1–4; the level index ranges from 1 to . Together, the lemmas show that total credit cannot increase, and that if two consecutive levels have the same total credit.
The first lemma compares a node’s credit with the total credit of its children. It uses only disjoint refinement and backward propagation, not the flow equations.
Lemma 2. Let be the children of in . Then . If equality holds and for some child , then has exactly one child ; moreover, and .
Proof. Step 1 gives , H1 gives , and Step 4 gives . Thus,
Suppose equality holds and for some child . Then . Since every other child has credit at most its candidate anonymity, . The definition of credit therefore gives . Each visible child contributes at most units of credit, so would give total credit at most , contradicting equality. Thus has a unique visible child, ; if failed to represent an agent in , its anonymity would be at most , which would again give total credit at most . Thus represents all of , and Step 4 gives .
We now use the flow equations to study nodes with the smallest ratio of actual to candidate anonymity. For every , define its ratio as . Let , let , and let be the set of parents of nodes in . The next lemma shows that if the nodes in collectively represent the same agents as their parents, then they represent all agents in the network.
Lemma 3. If , then is full and every node in it has ratio .
Proof. Let be the common set of agents in the stated equality. Every child in of a node in must belong to , for any other child would represent agents on the parents’ side of the equality but not on the children’s side. Counting the arcs leaving gives
The first equality counts arcs by their tails using H3; the second uses the ratio of each node in . The third groups the nodes in by their unique parents in ; the fourth sums the candidate flow equations over (Step 3 for and Step 4 for ). The first inequality uses . The last inequality holds because its left-hand side counts only arcs from ending at agents in the fibers of visible nodes.
The first and last expressions of (1) are identical, so both inequalities hold with equality. The first forbids arcs from to agents in the fiber of a visible node whose ratio is larger than ; the second forbids arcs to agents in the fibers of hidden nodes. Hence every arc from ends at an agent represented by a node in , and therefore at an agent in . Since is nonempty, strong connectivity forces . Hence , proving both conclusions.
We now combine these two facts. When total credit is preserved, Lemma 2 will show that the minimum-ratio nodes and their parents represent the same agents. Lemma 3 will then make the level full, and the known leader count will force actual and candidate anonymities to agree.
Lemma 4. For every , . If equality holds for any , then .
Proof. Summing the inequalities from Lemma 2 over gives . Suppose that . Every one of these inequalities must then hold with equality, so for every ,
Let , , be as in Lemma 3. Step 3 and backward propagation make the candidate anonymities of the leader nodes on sum to , whereas H2 bounds their actual anonymities by . Thus some leader node has ratio at most 1, so . Every therefore satisfies . Its parent satisfies (2), so Lemma 2 implies that is the unique child of and . Thus each parent in and its unique child in have the same fiber.
Lemma 3 now implies that is full and every node has ratio . In particular, its leader nodes have total actual anonymity and total candidate anonymity . Since , these two sums give , hence because . All actual and candidate anonymities on therefore agree. Step 3 sets the total candidate anonymity at the anchor to , and Step 4 preserves this total at every earlier level. Since is full, its actual anonymities sum to . Thus .
The previous lemma bounds the credit that can reach the anchor. The levels after the anchor give a lower bound: the anchor must have at least one unit of credit for each additional visible node.
Theorem 1 (Core algorithm). For every , the core algorithm makes all agents output and halt at round . All local computations take time polynomial in (assuming the network has at most arcs per round).
Proof. Until the first agent halts, every agent maintains its vista. Fix a candidate . If its test reaches Step 5, Lemma 4 and integrality show that each of the first rounds loses at least one unit of credit. Step 3 gives total candidate anonymity at the anchor, and backward propagation preserves this total at every earlier level. The leader node in has actual and candidate anonymity , and hence credit . Any remaining credit comes from the single nonleader node (if it exists and is visible), and is at most the remaining candidate anonymity . Thus
For each , its descendants in have disjoint nonempty fibers. Hence , while Step 5 checks that . Therefore, observing that , we have
Every level after the anchor is nonflat, and Step 1 ensures that every node before has a child at the next level. Each of the remaining transitions therefore increases the number of visible nodes, giving . Combining the two bounds on yields , a contradiction. Thus every agent rejects all candidates and remains active.
Consequently, all agents still maintain their vistas when is tested at round . H4 implies that is full, and hence the entire prefix ending there is full, as well. Since every node before has a child at the next level, the number of nodes cannot increase in all transitions: is nonempty and no level has more than nodes. Thus some level among is flat. Lemma 1 then recovers the actual anonymities at the anchor. Disjoint refinement and flow balance make all backward checks succeed, while disjointness gives at the anchor. Hence every agent accepts and halts at round .
Under the stated arc bound, multiplicities, outdegree labels, and linear-system coefficients have polynomial bit length. Step 3 solves one linear system with at most variables by exact Gaussian elimination with fractions kept reduced, which takes time polynomial in [17 Theorem 4.10]. Up to termination, vistas have polynomially many nodes and edges; their construction and all remaining checks also take time polynomial in .
Sharp Bounds
The core algorithm leaves two opportunities to terminate earlier. We briefly sketch the sharp upper- and lower-bound arguments here. Sections C and D contain the complete technical proofs.
Upper bound: case . At round , if an agent’s vista contains no nonleader node at level , then the agent outputs and halts. Indeed, if , condition (SC) would make a nonleader visible within rounds. Thus, when , all agents correctly halt at round .
Upper bound: case . Once the previous test has failed, every agent knows that . Assume that . Each agent then tests candidates using exactly Steps 1–5 of Section 3.1, except that the test is performed at round (instead of ), with final level (instead of ). Step 1 requires children only through , Step 2 chooses , and Step 5 counts descendants in . The bound on nodes per level and the total candidate anonymity remain . At , H4 makes the prefix ending at full. Moreover, has a leader node and a nonleader node, so cannot all be nonflat. Thus the true candidate is accepted at round . Note that this part of the proof did not require . It remains to show that the algorithm does not incorrectly terminate when ; for this part, is needed. If such a candidate passes with anchor , the proof of Theorem 1 gives
Thus every inequality is tight. This forces the nodes of to have singleton fibers, which together cover all fibers of . Moreover, at round , the backward-expansion argument used for H4 guarantees at least represented agents at level . Since Step 1 permits at most nodes in , this level has exactly nodes, each representing one agent.
Every visible node from through therefore has anonymity equal to its number of descendants in . At the anchor, these descendant counts sum to . Step 5 bounds each candidate anonymity below by its descendant count, and the candidate anonymities also sum to ; hence all candidate anonymities at the anchor are correct. Let be the set of agents represented at (and hence at every subsequent level through ). Since , some agents are outside . This immediately implies that , for otherwise, in round , the agents in would only receive messages from , contradicting (SC).
Since , the leader equation of Step 3 applied to implies that contains all leaders. Now the idea is to count how many nonleaders in have become distinguishable from every agent outside . At round 0, none have: all nonleaders belong to the same fiber, including those outside . Then, the flow equations for candidate anonymities imply that agents whose whole fiber is already inside send messages only to . Strong connectivity forces a message from these fibers to someone outside their union. That recipient must still be in , but its old fiber includes outsiders. The recipient receives a message from the sender’s fiber, whereas no outsider does. Its new fiber therefore contains no outsiders.
So each round separates at least one additional nonleader in from all outsiders. Once separated, it stays separated, because fibers only split. But there are rounds and only nonleaders in . When , there are too few nonleaders for this to happen in every round. Thus, a false candidate could not have passed. Section C gives the complete argument.
Matching lower bounds. The previous combined upper bounds are tight in every case. For , consider two static bidirected paths. One consists of leaders; the other consists of a chain of leaders followed by one nonleader. The endpoint leader in each network has the same vista through round . Hence that leader cannot terminate before round .
For and , two static bidirected paths of orders and , with the leader at one endpoint and a loop at the other, give the same leader vista through round . This construction and the resulting lower bound already appear in [13].
Finally, suppose that and . We construct two dynamic networks and of orders and , respectively, each with leaders. Let and be leaders in and , respectively. We keep their vistas identical through round . We first handle , when has one nonleader and has (refer to Figure 2).
Figure 2. The basic lower-bound pair for and . Blue fill denotes leaders and yellow fill denotes nonleaders. Green rings mark and , whose vistas agree through round . Edge labels are parallel-arc multiplicities; labels equal to are omitted.
First rounds. In , every round graph is a bidirected star centered at its only nonleader. In each round, selects a different leader other than , together with a fixed nonleader. The selected leader sends to all nonleaders, the selected nonleader sends to all leaders, and every remaining agent sends only to the selected leader. With suitable parallel-arc multiplicities, after each round all leaders in and all leaders in not yet selected have the same vista, while all nonleaders in both networks also have the same vista.
Next rounds. In each round, selects its only nonleader and a different leader other than . Meanwhile, selects and a different nonleader. In each network, the selected leader sends to
all nonleaders, and the selected nonleader sends to all leaders. Every remaining agent in sends only to the selected leader; every remaining agent in sends only to the selected nonleader. Some previously selected agents may already have different histories, but their messages reach only the agent newly selected that round. This agent sends its old state before receiving their information. Parallel-arc multiplicities match the received multisets and outdegrees so that, after each round, the leaders in not yet selected in this phase have the same vista as , while the nonleaders in not yet selected in this phase have the same vista as the only nonleader in .
Final stage. Each network becomes a directed cycle through all its agents. The nonleader in and the nonleader in left unselected in the second phase send directly to and , respectively. Their identical old states give and one further round of identical vistas.
For larger , add one nonleader to each network at a time. Initially, route leader information through the new agent before it reaches the original nonleaders, gaining one extra initial round. The next two phases still take rounds each, with their wiring adjusted to preserve the same vista invariants. Then, in the directed cycle used in the final stage, insert the new agent immediately before , respectively , and repeat this cycle for one additional round: the extra communication hop keeps the vistas of and identical for one round longer. Thus adding one nonleader to each network extends the previous construction by two rounds, making vistas agree through round . Every round graph remains strongly connected and loopless; Section D gives the full construction and proof.
Theorem 2. The exact worst-case termination time for Counting over directed multigraphs is
All local computations take time polynomial in (assuming the network has at most arcs per round).
Network-Wise Complexity
The bound in Theorem 2 optimizes the worst case over all networks. However, on a particular network, an agent may have enough information to determine earlier. We now study the complexity of recognizing when this happens. Before the first agent halts, every agent can maintain its vista, as described in § 2; we ask whether this vista already determines .4
The input consists of a vista and the leader count . It lists the nodes, parents, leader statuses, outdegree labels, and red multiplicities, with numerical labels in binary; it does not include fibers or anonymities. A realization is a dynamic network with leaders in which some agent has vista . Its order is its number of agents. The order spectrum is the set of orders of all such realizations. A realizable vista determines exactly when its spectrum is a singleton: two different compatible orders require different outputs from agents with the same information.
For a decision problem on arbitrary encodings, define AtMostOneVista to ask whether , assigning empty spectrum to malformed encodings. On vistas that actually occur in a network, the spectrum is nonempty, so this is precisely the test for determining .
Theorem 3. AtMostOneVista is coNP-complete. Hardness holds even for realizable vistas with one leader.
We give the main arguments below; Sections E and F contain the complete proofs.
Membership in coNP
Membership in coNP requires some care. A given vista may be compatible with arbitrarily large networks, so we cannot simply guess two networks of different sizes and describe them explicitly. Describing them by full history-tree prefixes does not immediately solve the problem either, since these prefixes may themselves have exponentially many nodes. We show how to overcome both difficulties and obtain polynomial-size certificates based on history trees, in three steps.
Bounding the network sizes. Let be the number of nonroot nodes in the given vista, its final round, and the largest of its numerical labels and the leader count . Suppose two networks of different sizes are compatible with . In each network, choose an agent holding as the observer. An agent is influential if its information can reach the observer by round through a chain of messages sent in increasing rounds; the observer itself is influential. Tracing these dependencies backward shows that at most agents are influential in either network.
If every agent in both networks is influential, both sizes are at most and we are done. Otherwise, consider one of the networks with non-influential agents, and merge any non-influential nonleaders into a single agent. This preserves strong connectivity and the observer’s vista, and yields a network of at most agents, some of which are still non-influential.
From such a network, we can obtain a second compatible one by adding one nonleader. In each round, we use this additional agent to subdivide an arc from an influential agent to a non-influential one (which exists by strong connectivity), preserving the sender’s outdegree and leaving the vista unchanged. We thus obtain two compatible networks of consecutive sizes, both at most .
Consequently, whenever two different orders are compatible with , two can be chosen that are at most exponential in the input length (including the binary encoding of ). The binary representations of these orders therefore have polynomial length.
Bounding the history-tree size. Even a network of this bounded order might have too many distinct indistinguishability classes. We build a new history tree one level at a time, without changing the network size or the observer’s vista. At each new level, we preserve the visible nodes and their fibers. For each node at the previous level, we group the agents in its fiber not represented by visible children into at most one hidden child. If there are hidden agents, we give one of them a singleton fiber, adding at most one extra hidden node at that level. The main difficulty is to preserve strong connectivity without changing visible observations. We achieve this by carefully redirecting communication through that singled-out agent. The resulting prefix through level has polynomially many nodes, and all its numerical labels have polynomial bit length.
Verifying the certificates. Thus, for each of the two chosen orders, we guess a small history-tree prefix through level matching and , including its anonymities and communication multiplicities. We check refinement and anonymity conservation, flow balance, and strong connectivity of a graph describing possible communication between history classes.
These checks can be performed directly on the polynomial-size prefix and do not require constructing the actual network. To prove realizability, we temporarily route messages through an auxiliary vertex for each indistinguishability class. The flow equations ensure that the incoming and outgoing arcs at these vertices can be paired; the main technical step is to choose these pairings so that replacing each pair by a direct arc preserves strong connectivity.
The two history-tree prefixes therefore provide polynomial-size certificates for two different compatible orders, proving membership in coNP. The full proof appears in Appendix § 11.
coNP-Hardness
We reduce from the complement of Exact Cover by 3-Sets (X3C) [14 Problem SP2]. An instance consists of triples over elements; an exact cover consists of triples containing each element exactly once. We may assume , by adding disjoint triples on fresh elements if necessary. We construct a one-leader network and output its leader’s vista. This vista will admit a realization of a different order precisely when the instance has an exact cover (refer to Figure 3).
Figure 3. The X3C reduction for and the exact cover , . Here and . Blue fill marks the leader ; yellow fill marks nonleaders. Shaded sectors identify the special group 0 and groups 1, 2, corresponding to , . In rounds 1–4, each group forms a directed path ending at . In every round, the leader has parallel outgoing arcs to each agent in group . Each triple is encoded by for , giving and ; the special coefficient is . The reference and alternative group sizes are and , respectively. Thus the leader’s outdegree is in both networks, although their orders are 17 and 18. The right panel shows their common leader vista after round 5. At level 4, represents the last one or two agents of group ; a blue dashed outline in a network marks the corresponding two-agent fiber. The round-5 return arcs give the leader the same receipts: two copies of the state represented by and one from every other level-4 nonleader node. In the vista, black-edge labels are outdegrees and red-edge labels are multiplicities; unit labels are omitted throughout.
The reference network. Set . We construct a reference network with one leader and groups of nonleaders: group corresponds to triple , and group 0 is an additional special group. Each triple group contains agents, while group 0 contains , giving agents altogether. Within each group, arrange the agents along a directed path whose last agent sends to the leader. The leader also sends parallel messages to every agent in group . We choose these multiplicities to encode the triples. Number the universe elements , and define
In base , each triple coefficient has three element digits equal to 1, together with a leading digit 1. The target has every element digit equal to 1 and leading digit . Thus the coefficients of selected triples sum to exactly when they form an exact cover: the element digits require every element to occur once, and carries are prevented due to .
Use the communication graph described above for the first rounds. In round , keep the leader’s outgoing arcs, but replace the path arcs by one arc from every nonleader directly to the leader. Let be the leader’s vista after this final round. Thus, the reference network is always a realization of , regardless of whether the instance has an exact cover.
The alternative network. Suppose the X3C instance has an exact cover. Remove one agent from group 0, and add one agent to each of the triple groups in the cover. As before, in every round the leader has parallel outgoing arcs to every agent in group . Because the selected triples cover every element exactly once, their coefficients sum to . The leader therefore loses outgoing arcs through the removal and gains exactly through the additions. Its outdegree is unchanged, although the network now has agents.
For the first rounds, arrange each group as a directed path ending at the leader, as in the reference network. In round , replace the path arcs as follows. The last agent of group 0 has two parallel arcs to the leader. In each selected triple group, put one arc from the second-to-last agent to the last agent, and one from the last agent to the leader. Every other nonleader has one arc directly to the leader. Section F shows that after rounds the leader has the same vista in both networks, with visible nodes per group at level .
The converse. It remains to prove that if the X3C instance has no exact cover, every realization of has exactly agents. The visible nodes of each group at level require at least agents, while the leader’s prescribed outdegree permits at most additional agents to be represented at level one. If level one were not full, strong connectedness would force the number of represented agents to decrease at each of the transitions to level . Only agents can be lost while retaining per group, so level one must be full. All outgoing arcs of the leader are then accounted for. In the absence of an exact cover, the coefficients force the reference group sizes, and hence order . Section F gives the complete argument.
Related Work
Static networks and local computation. In a static anonymous network, an agent’s view is a rooted tree recording all information it can learn by exchanging messages. Tani [31] shows how to construct and compare compressed views with polynomial local computation and communication complexity when the size of a static anonymous network is known. Other work studies the complexity of recognizing which networks admit a given task. Yamashita and Kameda [33] prove coNP-completeness for recognizing whether a graph admits election or naming in the port-to-port model; Chalopin and Paulusma [7] classify these recognition problems across message-passing and local-computation models. Their input is a fully specified graph. In our coNP-complete problem, the input is an agent’s local history, and the question is whether all compatible dynamic networks have the same size.
Dynamic networks with IDs. Kuhn, Lynch, and Oshman [22] study exact Counting in synchronous dynamic networks with unique identifiers and unknown size. In undirected networks connected in every round, their algorithms terminate in rounds using -bit messages, or in rounds using -bit messages. Both bounds also hold for directed networks that are strongly connected in every round. For undirected networks with unrestricted message size, Kuhn, Moses, and Oshman [23] improve the stopping criterion of identifier flooding: agents recognize when they have received information originating from every node, instead of waiting for a worst-case time bound. Their criterion is optimal on every dynamic network and enables Counting in rounds, where is the dynamic diameter, the maximum time needed for information to travel between any pair of agents. For strongly connected directed dynamic networks with unique identifiers and -bit messages, Abshof et al. [1] relate Counting to two-party token dissemination. They show that transmitting tokens between two designated nodes can be reduced to Counting in a network with nodes.
Counting with randomization. Kuhn, Lynch, and Oshman [22] also give a randomized algorithm for approximate Counting in dynamic networks connected in every round. Their algorithm assumes a known upper bound on the network size and a topology chosen independently of the algorithm’s random choices. For any fixed , it terminates in rounds and returns an estimate satisfying with high probability in . It estimates the size by propagating minima of random values generated by the agents. Randomized size estimation has also been studied in peer-to-peer networks. Jelasity and Montresor [16] use gossip-based aggregation to estimate global quantities, including network size. Massoulié et al. [25] develop estimators based on random-walk return times and repeated samples of the same peer. Le Merrer, Kermarrec, and Massoulié [24] compare random-walk, probabilistic-polling, and gossip-based estimators, evaluating their accuracy, communication cost, and response to nodes joining and leaving the network. These works concern approximate size estimation; here we seek exact Counting with deterministic termination guarantees.
Anonymous undirected dynamic networks (mass distribution). Michail, Chatzigiannakis, and Spirakis [26] initiated the study of Counting in anonymous undirected networks whose topology may change arbitrarily while remaining connected in every round. Early work by Di Luna et al. [9, 10] included an energy-transfer algorithm that lets the leader detect completion under a degree bound. Kowalski and Mosteiro [18] obtained the first polynomial-round algorithm with a unique leader, terminating in . Their subsequent work [19] extended the approach to a known number of leaders and improved the bound to , for every fixed . These algorithms only work in undirected networks and use mass distribution, reminiscent of average-consensus techniques [27, 28], together with tests that detect incorrect estimates of the network size.
Anonymous undirected dynamic networks (history trees). Di Luna and Viglietta [11] introduced history trees and obtained the first linear-round terminating Counting algorithm for anonymous undirected dynamic networks with a unique leader, with a bound of rounds. A successive work [13] handles a known number of leaders and, when the network is connected in every round, gives a termination bound of . It also gives a -round stabilizing algorithm for Counting and input-multiset computation, as well as linear-round algorithms for leaderless Average Consensus. We remark that a stabilizing algorithm need not terminate: agents eventually produce the correct answer but may not know when it has become correct. The same work proves a termination lower bound for a unique leader using static paths with a self-loop [13].
Anonymous undirected dynamic networks (communication and memory restrictions). In undirected dynamic networks, Di Luna and Viglietta [12] give polynomial-round algorithms using -bit messages, including a terminating Counting algorithm with a unique leader that takes rounds. Blanc, Di Luna, and Viglietta [5] study one-bit broadcasts; with a unique leader, their Counting algorithm stabilizes in rounds, and a known upper bound on also enables termination. Kowalski and Mosteiro [20] study anonymous dynamic networks with a known nonzero number of leaders, logarithmic message size, and logarithmic internal working memory. They allow temporary disconnections subject to a connectivity condition over bounded windows, and give polynomial-round algorithms for Counting and for disseminating all inputs with their multiplicities.
Anonymous directed dynamic networks. Charron-Bost and Lambein-Monette [8] study anonymous directed dynamic networks without parallel arcs and with finite dynamic diameter : information from any agent can reach every other agent within rounds. Their method uses a deterministic broadcast version of the Push-Sum averaging algorithm. Their algorithm requires early outdegree awareness: each agent knows its current outdegree before sending. With a known number of leaders, their approach can be used to estimate the fraction of leaders. Rounding , where is the current estimate, then yields a Counting algorithm whose output eventually stabilizes at . Applying the convergence analysis in the proof of Theorem 5.2 of the full version of [8] to this reduction gives a stabilization bound of rounds. When the network is strongly connected in every round, holds, and so this bound is . The algorithm provides no criterion for recognizing when the estimate is correct and terminating.
For directed networks with late outdegree awareness, Viglietta [32] extends history trees by incorporating outdegrees and using linear equations to recover the sizes of indistinguishability classes. This yields Counting algorithms that stabilize in rounds, whereas the terminating algorithm has a bound for simple round graphs. Our algorithm closes this gap between stabilization and termination by attaining the exact worst-case termination bound with polynomial local computation, including when loops and parallel arcs are allowed.
Conclusions
Counting in anonymous directed dynamic networks (allowing loops and parallel arcs) has an exact worst-case termination bound, attainable with local computation polynomial in if the network has at most arcs in every round. For a specific network, however, recognizing whether the available information already determines its size is coNP-complete (for binary-encoded arc multiplicities), even with a unique leader.
One open question is whether the termination bound for Counting remains tight for simple directed round graphs, with no loops or parallel arcs, when (for one leader, a lower bound even for static simple undirected networks follows by adapting the construction of Krebs and Verbitsky [21 Section III]).
Another direction concerns stabilizing Counting: agents may revise their outputs and continue communicating, but all outputs must eventually remain equal to , without agents having to detect when this happens. We ask for exact worst-case stabilization bounds and a corresponding analysis of network-wise optimization for algorithms that never overestimate .
Finally, we ask whether AtMostOneVista remains coNP-complete for simple round graphs. The complexity of AtMostOneVista with unary-encoded arc multiplicities is also open.
Acknowledgments. We thank Jérémie Chalopin and Federico Poloni for discussions concerning a preliminary version of the proof of Lemma 1 using Perron–Frobenius theory.
Disclosure of AI assistance. We used the AI assistant GPT-6 Astra to refine and validate the multi-leader lower-bound construction (§ 3.2 and Section D) and to produce formal proofs in the Lean proof assistant for all results in this paper. The Lean code is available at https://github.com/gadiluna/ADDN_lean.
Solving a Flat Level
We will now prove Lemma 1 on flat levels. In the terminology of [32], the level preceding a flat level is called non-branching, and an equivalent statement to Lemma 1 is proved there in Section 3.3. A closely related statement appears in Section 4.2 of the full version of [8]. In the following, we prove it within our framework; notably, our proof does not use Perron–Frobenius theory and is self-contained.
Lemma 1. Let be a full and flat level of a vista, with . The flow equations on , together with , uniquely determine the anonymities of the nodes of .
Proof. Because is flat, every has a unique child ; since is full, . Let , and index these parent-child pairs as , for .
Form the square matrix whose row corresponds to and whose column corresponds to , with entries
Let be the vector of anonymities, with for . Since is full, the flow equation (Flow) gives , with .
For , the entry is nonnegative and is positive exactly when has an arc from to . Thus the digraph with arcs whenever and is obtained from by contracting these fibers and discarding loops. It is therefore strongly connected.
We prove that every solution is proportional to . Put and . Then , , and some coordinate is zero. The equation in row gives
Every summand is nonnegative, so for every with . Repeating this argument along directed paths shows that every coordinate is zero. Hence , and the nullspace of is spanned by .
Finally, since is full, H2 gives
Since , the entries of corresponding to leader nodes sum to . If also satisfies the leader-count equation above, this sum equals . Since , we obtain and hence . Thus the flow equations together with the leader-count equation uniquely determine the anonymities.
Causal Support
Fix an agent at round . Its causal support is the sequence defined by
Thus consists of the agents whose round- states are used, directly or through later states, to construct the round- vista of . For , a node belongs to this vista precisely when
This follows by backward induction from the bottom node: a preceding node enters the vista as a parent or as the tail of a red edge, corresponding to the two terms in the recurrence for .
Sharp Upper Bounds
We prove the two improvements summarized in § 3.2. The first detects that every agent is a leader. For the second, we count the nonleader fibers contained in a fixed proper set of agents to show why two or more leaders permit termination one round earlier.
Lemma 5. In a vista , the fibers of the nodes in , where , together contain at least agents.
Proof. Use the causal support from Section B, starting with . Whenever , strong connectivity gives an arc from its complement into it in round , so . Hence , and every agent of belongs to a visible fiber.
Case . At round , if an agent’s level contains no nonleader node, it outputs and halts. If , Lemma 5 places at least agents in the visible level-zero fibers, so a nonleader node is visible. Thus the test succeeds exactly when , and all agents then halt at round .
To analyze the multiple-leader case, we use the following fact about the full history tree. If a proper set contains all leaders and every fiber contained in that set sends only within it, strong connectivity forces another nonleader fiber to become contained in the set at each round.
Lemma 6. Let contain every leader. Suppose that, for each , every node in whose fiber is contained in has no outgoing arc from that fiber to in round . Then .
Proof. Count the nonleader fibers contained in . There are none at level zero, because the sole nonleader fiber contains . Every child fiber of a counted fiber is still contained in , so this count cannot decrease.
In round , let be the union of the fibers at level contained in . It contains every leader and is a nonempty proper subset of . Strong connectivity gives an arc from an agent to an agent . The hypothesis forces . Let be the old fiber containing . The agent receives an arc from , whereas no agent outside does. The definition of indistinguishability therefore places ’s new fiber wholly inside , although its old fiber was not contained in . This is a new nonleader fiber, distinct from all children of the previously counted fibers; it cannot be a leader fiber because all old leader fibers were already contained in .
The count increases by at least one per round and is at most , proving the bound.
Case . Assume that the all-leader test has failed and . At round , test candidate by Steps 1–5 of Section 3.1, with final level . Thus Step 1 requires children only through , Step 2 chooses , and Step 5 counts descendants in , including the node itself when . The bound on nodes per level and the total candidate anonymity remain . The credit lemmas apply unchanged, since the test checks the same refinement and flow equations up to the anchor.
Lemma 7. For , this test rejects every candidate and accepts at round .
Proof. Suppose passes with anchor . The proof of Theorem 1 gives
Every inequality is tight. For each anchor node , let count its descendants in . Disjoint refinement and Step 5 give . Equality in (3) gives , so . Its descendants have disjoint nonempty fibers contained in ; they must therefore have singleton fibers whose union is . By Lemma 5 and the total candidate anonymity,
Thus at the anchor. Its fibers form a set of exactly agents, also represented by the singleton fibers at level . The leader equation shows that contains all leaders.
If , the union of visible fibers is at level as well: it lies between the identical unions at levels and . Strong connectivity gives an arc from into in round , making a predecessor outside visible at level , a contradiction. Hence .
Every earlier node whose fiber meets is visible, because each agent of has a visible descendant at level . Backward propagation from these singleton fibers gives for every , . Fix and whose fiber is contained in . The node and all its children are visible, so the checked flow equation gives
Thus every old fiber contained in sends only to in each of the first rounds. Lemma 6 now gives , contradicting .
Finally, when , H4 makes the prefix ending at full at round . Level has one leader node and one nonleader node. If the next levels were all nonflat, the last would have at least nodes. Hence a flat level exists; Lemma 1 recovers its actual anonymities, and every remaining check succeeds.
Perform the all-leader test first. After it fails, use the appropriate test, depending on whether or , testing . Every false candidate is rejected at every agent, so all agents remain active until they halt together at the round stated in Theorem 2.
Input multisets. Assume that each agent is given an input value and must evaluate a fixed computable function of the multiset of all inputs. Neither nor the other agents’ input values are initially given. Following [11, 13, 32], each agent labels its initial bottom node and every new bottom node with its input value. Match-and-merge preserves these labels and leader status, so the agents in each nonroot node’s fiber have the same input. Perform the core algorithm’s candidate tests, interpreting Step 1 as requiring at least one visible leader node at level zero. For a candidate passing Steps 1–4, the visible level-zero leader nodes together have credit at most : their fibers contain at most agents, and each node contributes at most its anonymity minus one. Nonleader nodes contribute at most the remaining candidate anonymity , so . The rest of the correctness proof of Theorem 1 applies unchanged. Thus is accepted at round , and the anchor anonymities are correct. Summing these anonymities over nodes with each input value gives its multiplicity. Each agent then evaluates the function, outputs its value, and halts.
Termination Lower Bounds
The lower bounds compare designated leaders in dynamic networks of different orders but with the same number of leaders. Equal round- vistas therefore give equal states after rounds, so the two leaders make the same terminal decision. They cannot both terminate correctly by that round.
Case . Let the smaller network be the static bidirected path , with every agent a leader. The larger network is the static bidirected path , where the ’s are leaders and is a nonleader. Both networks have leaders. Observe in both networks.
The states of the two copies of agree through every round with . This follows by induction on . Initially the two agents have the same leader status. In the induction step, the relevant copies have the same outdegree and receive the same multiset of states from corresponding neighbors. The different degree of is learned only after the first communication round. Taking shows that the two endpoint leaders have the same vista through round . Therefore the smaller network cannot terminate before round . This also covers , when the initial vistas are identical.
Case . For , let be the static bidirected path . Its unique leader is , and has one self-loop. Run the vista-construction algorithm on and . At round , all agents farther than edges from their leader have the same vista: initially they are nonleaders, and at each step they have degree two and receive two copies of the preceding common vista. Corresponding agents therefore agree through round : until then, the loop at the shorter endpoint returns the same vista as the continuing edge in the longer path. A difference can first arise there at round , then needs another rounds to reach the leader. Thus the leader vistas agree through round , and termination requires rounds. This construction and bound already appear in [13].
Case . We first describe a strongly connected graph in which every agent except one receives information from a single sender.
Lemma 8. Let be disjoint nonempty sets of agents, with . Choose , , and . An arrow denotes arcs from each agent of to each agent of ; an agent may replace a singleton set. The graph on consisting of exactly the arcs
is loopless and strongly connected. Each agent of receives only ’s old vista and has outdegree ; each agent of receives copies of ’s old vista and has outdegree .
Proof. Every agent other than reaches directly. Conversely, reaches directly and through , proving strong connectivity. The sets are disjoint and the return bundles exclude as a sender, so there are no loops. The listed arcs give exactly the stated incoming vistas and outdegrees. □
The construction uses an agent’s matching history for one last round: its current incoming information and outdegree cannot change the state it has already sent. Two phases apply this observation to the leaders and nonleaders in turn. A path of added nonleaders then supplies one initial and one final round of delay per added agent.
Theorem 4. For every , there are dynamic networks of orders and , each with exactly leaders, whose designated leaders have identical vistas through round . Every round graph is a strongly connected loopless directed multigraph, with arc multiplicities at most and outdegrees at most .
Proof. We first describe two phases for , using networks with and agents. We call these networks the cores: for larger , we add nonleaders to each and adjust the communication arcs. The smaller core has leaders and one nonleader ; the larger has leaders and nonleaders . We compare the vistas of . Two agents are matched when their current vistas are isomorphic. They remain matched if their previous vistas, current outdegrees, and received multisets of previous vistas agree.
In each application of Lemma 8, partition the core and remain fixed throughout the phase, even after an agent has been selected as a center.
First phase: rounds. Keep the smaller core a unit bidirected star centered at . In round of this phase, the larger core uses the graph of Lemma 8 with its leaders, , , and . After round , all smaller leaders and share one vista, while share another.
By the lemma and the smaller star, the leaders being compared receive one matching nonleader vista and have outdegree one. The nonleaders being compared receive copies of a matching leader vista and have outdegree . In the smaller star these copies come from different leaders; in the larger graph they come from parallel arcs of . This proves the assertion by induction from the initial leader and nonleader classes. We no longer compare after its round.
Second phase: rounds. Apply Lemma 8 with on both sides. In round of this phase, the smaller core has its leaders, , and ; the larger core has its nonleaders, , and . After round , share one vista, while share another.
The lemma gives the observations for this induction: each compared leader receives one matching nonleader vista, and each compared nonleader receives one matching leader vista; all have outdegree . In both phases, a newly selected center sends its matching old vista before receiving potentially different information or learning its new outdegree. Previously selected agents send only to this new center. Their different histories therefore do not affect the agents still being compared. After the two phases, match and match.
Adding nonleaders. Add to the smaller core and to the larger one. We call these added nonleaders relays, and each pair , for , a relay pair. We describe the initial delay, the changes to the two phases, and the final delay. For , omit the initial delay and leave the two phases unchanged.
For , begin with repetitions of one fixed graph on each side. Put the nonleaders on the directed cycles
and join every leader bidirectionally to , respectively . All these arcs have multiplicity one. Each cycle has at least two agents, so the graphs are loopless; attaching the leaders preserves strong connectivity.
After round , all original nonleaders and all with share one vista, all leaders share one vista, and every pair is matched. To see this, receive the same leader vistas and one matching cycle-predecessor vista, with outdegree . Every other nonleader has outdegree one and receives its predecessor’s vista. The distinction first created at thus advances one position per round, reaching no original nonleader before round . The leaders receive the matching vistas of and have outdegree one. This proves all three assertions by induction.
In each round of the two -round phases, let be the nonleader with one outgoing arc to each leader: in the smaller network, in the larger network’s first phase, and in round of its second phase. For , replace these arcs by
using instead of in the larger network. All other core arcs remain unchanged. Every original outdegree is preserved, and every relay has outdegree . Each replaced arc still has a directed path with the same endpoints, and every relay lies on these paths, so strong connectivity is preserved.
The phase inductions now include the assertion that every relay pair is matched. The two agents serving as have matching old vistas, even when the larger one is the newly selected . Thus corresponding relays receive copies of matching predecessor vistas and remain matched. Each compared leader receives the last relay’s matching vista instead of ’s vista; the compared original nonleaders have unchanged incoming arcs and outdegrees. The two phase invariants therefore still hold. At their end, , and every relay pair match.
Final cycle. On the smaller and larger sides, respectively, use the directed cycles
For , send directly to the observers. Repeat these graphs forever. Every agent has indegree and outdegree one. Initially the consecutive agents match their counterparts, so a difference can advance toward the observers by only one position per round. Their vistas remain identical for final rounds.
In fact, first differ in the first final round: their predecessors are and , whose initial leader statuses differ. This difference reaches the observers in final round . The common interval therefore has exactly
rounds. In particular, the core has one common final-cycle round; the next repetition shows the first difference.
All graphs are loopless. During the two -round phases, arc multiplicities are at most , and a selected center sends at most arcs to each of at most agents, giving outdegree at most . All other middle agents have outdegree at most . The initial maximum outdegree is , and the final outdegree is one. This proves the stated structural bounds.
Membership in coNP
We now ask whether a finite vista determines the network size, namely the number of agents. The input is the abstract structure stored by an agent, which does not include its unknown fibers. A negative answer requires two networks of different orders that produce the same vista. Their orders may be exponentially large, so an NP certificate cannot list their agents individually. We first bound the orders needed for such a certificate, then describe each network by polynomially many history-tree nodes and binary anonymities.
The AtMostOneVista Problem
An explicit vista lists its levels , with one bottom node in . The root at level is implicit. Each node at level zero has its leader or nonleader status. For every , the encoding gives the parent and outdegree label of each , and all positive multiplicities with . Unlisted multiplicities are zero; all numerical labels are encoded in binary. The positive leader count is also part of the input.
The encoding must have at most one node of each status at level zero, distinct signatures for children of the same parent, and exactly the nodes reached by following parents and positive red edges backward from the bottom. These conditions are checkable in polynomial time. Note that these conditions describe the syntax of a vista, but do not assert that a network realizes it.
A realization is a finite prefix of a dynamic network, with a leader set of size , whose round- vista at some agent is isomorphic to . We use the isomorphisms defined in Section 2. Its order is the number of agents. Define the order spectrum
Malformed encodings have empty spectrum. The problem AtMostOneVista asks whether this spectrum has at most one element. On realizable inputs, this is exactly the question whether the agent’s vista determines .
Small Realizations
Use the causal support from Section B. In particular, is the set of agents that have influenced the observer by round . This concerns individual agents, not whether a vista level is full: a visible node may have agents in its fiber outside .
Let be the binary length of , let , and let be the largest of , the outdegree labels, and the red multiplicities in . Put .
Lemma 9. If admits two different compatible orders, two can be chosen at most , with polynomial bit length in .
Proof. An agent represented by a node of at level constructs its vista from its own previous state, the states received in round , and its outdegree label. Its node has at most red predecessors, each of multiplicity at most . Unfolding the previous and received states backward for rounds therefore gives . If two different compatible orders have realizations with , both orders are at most .
Otherwise, take a realization with . Retain all agents in and all leaders; merge the remaining nonleaders, if any, into a single nonleader. Replace each arc by the arc between the images of its endpoints, retaining every parallel copy. Contraction preserves strong connectivity and every retained agent’s outdegree. No merged agent sends into in round , since such a sender would belong to . Thus all states needed for remain unchanged. The resulting realization has at most agents and still has an agent outside the causal support. Loops created by contraction are allowed.
Now add one nonleader. In each round , strong connectivity gives an arc from the nonempty proper set to its complement. Replace one copy by a two-arc path through the new agent. This preserves the original tail’s outdegree and changes no incoming arc at any agent in . Induction through the rounds preserves every state needed for , and the new agent remains outside the causal support. We have obtained two different compatible orders, both at most .
Finally, , , and are bounded by , so has polynomial bit length in .
Corollary 1. Let be a vista with leaders. If it has a realization of order whose observer has a proper initial causal support , then
Moreover, with as above, either all compatible orders are at most , or there is an integer such that
In particular, every order spectrum is finite or cofinite.
Proof. For the first assertion, repeat the arc-subdivision construction in the proof of Lemma 9. Each added nonleader leaves the observer’s vista unchanged and remains outside its initial causal support. Thus every order at least is compatible.
If no realization has a proper initial causal support, every compatible order is at most . Otherwise, the contraction construction in the same proof gives a realization of order with proper initial causal support. The first assertion then makes every order at least compatible. Hence the spectrum is finite in the first case and cofinite in the second.
Constructing the Network
A certificate will describe a full history-tree prefix, including nodes absent from the input vista. It gives each node a positive binary anonymity and specifies its parent, outdegree, and incoming multiplicities. To verify that these tables come from strongly connected round graphs, we need the following elementary construction.
Lemma 10. Let be a directed multigraph on , with . Suppose every ordered pair of vertices in is joined by a directed path, has no loop, and . The arcs at can be paired so that replacing each pair by leaves a strongly connected graph on .
Proof. Pair the arcs arbitrarily and call the resulting graph . If it is not strongly connected, choose distinct strongly connected components , , with no arc entering and no arc leaving . Reachability in forces an arc from into . Its paired shortcut lies wholly in , since no arc of enters . Similarly, an arc from to gives a paired shortcut wholly in .
Switch these pairings, replacing the shortcuts by and . Simple paths within and within avoid the removed shortcuts. The removed arcs therefore have replacement paths
No old reachability is lost, and , merge. Repeat until only one component remains. A shortcut that is a loop uses an empty internal path in this argument.
Lemma 11. Let be the old and new node sets of a proposed full history-tree prefix, with parent map . New node has anonymity and outdegree . Each agent in its fiber must receive arcs from the fiber of old node . Assume the flow equations
Put . For , these data have a strongly connected round realization exactly when every new node has positive outdegree and positive incoming degree, and the digraph on with arcs whenever and is strongly connected. For , balance alone suffices.
Proof. Necessity follows by projecting physical paths onto their nodes. For sufficiency, create the agents and an auxiliary vertex for each old node with positive flow total. An agent in the fiber of has arcs to ; vertex has arcs to each agent in the fiber of . Equation (10) makes each auxiliary vertex balanced. Every arc of the stated digraph lifts to a two-arc path between any agents in the corresponding fibers. Positive degrees and strong connectivity of that digraph make the auxiliary graph strongly connected.
Apply Lemma 10 to remove the auxiliary vertices one at a time. There are no arcs between them, so removing one leaves all others balanced. Each replacement preserves its source’s outdegree and its target’s receipt from the specified old fiber. Loops and parallel arcs are permitted. For , pair the single agent’s outgoing arcs and incoming requirements directly as loops.
The flow equation in the previous lemma is exactly (Flow), with both visible and hidden nodes included. The verifier checks the lemma’s conditions directly on the binary-encoded node tables, without constructing the potentially exponentially large network.
Compressing the History Tree
We must still show that any realization of can be replaced by one of the same order whose full history-tree prefix through level has only polynomially many nodes. We do this by rewiring arcs ending at agents in hidden fibers, while preserving all visible fibers and observations and keeping every round graph strongly connected.
Lemma 12. If has a realization of order , it has one of the same order and leader count whose full levels satisfy
Its anonymities, outdegrees, and multiplicities have bits. The entire full-prefix description has length polynomial in .
Proof. Fix a realization of . We keep the same agents and leader statuses, but rebuild the round graphs one round at a time. At each level, we partition the agents into sets called blocks, which the construction will make into the fibers of the new history-tree nodes. Blocks may split from one level to the next, but never merge. Every visible fiber remains an unchanged block; the other blocks will be fibers of hidden nodes. At level zero, use one block for all leaders and, if nonempty, one for all nonleaders.
Suppose the partition at level has been constructed. Within each block , retain each original visible fiber at level as a separate block, and put all remaining agents of into one block , omitting it if empty. A hidden block at level contains no visible fiber at level , since every visible node has a visible parent. If there are no hidden agents at level , keep the original round graph: all blocks at level are then unchanged visible fibers.
Otherwise, strong connectivity gives an original round- arc from an agent outside the visible fibers at level to an agent inside them. The original node at level whose fiber contains is therefore visible. Since visible fibers are preserved, this fiber is also a block of the new partition at level . Split into and , omitting the latter if empty.
Keep all original arcs ending at visible new agents. No agent in a hidden old block has such an arc, since its old node would otherwise be visible. For each ordered pair supported by an original arc with a hidden target, retain one arc from its source but redirect it to . For a source with visible new node , these retained arcs are a subset of its original outgoing arcs. Add arcs to until its outdegree again equals the displayed value . Choose larger than all currently retained degrees and all displayed new degrees. Give every hidden agent other than outdegree , by adding arcs to . Add one arc from to each other hidden agent, then pad ’s outdegree with loops to a value exceeding its current degree. Every block other than now has one uniform signature: its agents have degree , receive one state from old block , and receive nothing else. These degrees distinguish hidden children from visible siblings and distinguish from its hidden siblings. Visible children retain their incoming multiplicities and displayed degrees. Thus the new partition is exactly the partition into histories for this round, and the observer’s vista is unchanged.
The round remains strongly connected. Every hidden agent other than has an arc to and one from . To reach from a visible agent, follow an original path until its first hidden target; that arc was redirected to . To reach a visible agent from , take an original path and its last hidden vertex . The remaining visible suffix was retained; if , prepend the added arc . All visible incoming records are preserved, and no hidden old block sends to a visible new block, so no additional predecessor enters the vista. This proves the induction invariant.
The new partition has at most visible blocks, one hidden block per old block, and the extra singleton . Starting with at most two blocks gives the claimed node bound. For bit lengths, all retained arcs to visible targets total at most per source, and at most distinct hidden-target arcs per source are retained. Choose by adding one to the required maxima. All new degrees and incoming multiplicities are polynomially bounded in , and hence have bits. Since every vista level is nonempty, ; the tables have nodes and multiplicity entries.
Lemma 13. Whether is in NP, with certificate length polynomial in .
Proof. Guess the full-prefix tables of Lemma 12, a node at level to serve as the vista’s bottom node, and an identification of the input vista with the backward closure of . Check positive integer anonymities, total anonymity at each level, and exactly leaders. Check disjoint refinement: each parent’s anonymity must equal the sum of its children’s anonymities. At level zero, check that each occurring status has exactly one node. At later levels, check that each node has the same leader status as its parent (H2), and check nonnegative degrees and multiplicities, the full flow equations (10), distinct sibling signatures, and the realizability conditions of Lemma 11. Finally, check that the supplied identification preserves all edge types, labels, and statuses and maps exactly the backward closure of onto the input vista.
All checks take time polynomial in the binary table length. Disjoint refinement allows us to partition the same set of agents into fibers at successive levels, dividing each parent’s fiber among its children. Lemma 11 realizes every round on those agents, while distinct sibling signatures ensure that the resulting history tree has exactly the proposed nodes. Thus every accepted certificate gives a realization of . Conversely, Lemma 12 supplies a certificate for every compatible order.
Proof of Membership
Theorem 5. In the model of § 2, AtMostOneVista belongs to coNP.
Proof. For the complementary problem, guess two different compatible orders and their certificates from Lemma 13. By Lemma 9, the orders can be chosen at most , with polynomial bit length in . Both certificates therefore have polynomial length. Reject malformed inputs, whose spectra are empty. Taking complements proves the theorem.
There is also a network-level version. An input explicitly lists the agents, leader set, and round graphs through round , with binary arc multiplicities. The problem SomeAgentKnows asks whether at least one round- vista determines the network size.
Theorem 6. SomeAgentKnows belongs to coNP.
Proof. Construct all round- vistas by computing the successive partitions and history-tree labels. This takes polynomial time in the explicitly listed network prefix. Its order is compatible with every one of these vistas.
If no agent’s vista determines , each vista has at least two compatible orders. By Lemma 9, two can be chosen with polynomial bit length, and at least one differs from . Guess one such alternative order and its fixed-order certificate for every listed agent. The constructed vistas have polynomial length in the network input, so the whole list has polynomial length. Verify the certificates using Lemma 13.
coNP-Hardness
We prove hardness for AtMostOneVista, defined in Section 4, and SomeAgentKnows, defined in Appendix E. We do not require a second compatible realization to have smaller order. The construction uses binary-encoded parallel arcs, as allowed by the input model, and produces loopless, strongly connected round graphs.
Encoding Exact Cover
Reduce from the complement of Exact Cover by 3-Sets (X3C) [14 Problem SP2]. Let , and let be distinct three-element subsets of . We may assume : duplicate triples can be deleted, and adding three fresh elements with their unique triple increases by one without changing whether an exact cover exists.
Set
and define
We have , all , and . The are distinct: the triples have distinct base- digit vectors, and
Lemma 14. For nonnegative integers , the equation
has the reference solution , . Every other solution has , and its nonzero coordinates select an exact cover. Conversely, every exact cover gives such a solution. In every solution, .
Proof. Since every coefficient is at least and , the sum of the coordinates is at most . Equation (5) gives ; if , positivity of the other coefficients gives the reference solution.
If , write
Then
Here $0 \le d_e \le k \le q < B$, so no carries occur in base . The digit at position $3q$ gives , and the remaining digits give for every . Each is consequently zero or one, and the selected triples form an exact cover. The converse follows by summing the coefficients of a cover.
The Reference Network
There is one leader and groups of nonleaders. Write
The reference group sizes are
Thus the reference network has agents and .
More generally, for group sizes with , list group as . The path graph has the arcs
one copy of each, together with parallel arcs for every group member. Use this same graph for rounds . Every nonleader has outdegree one, and the leader has outdegree . The graph is loopless and strongly connected: the leader reaches every agent directly, and every agent has a path back to the leader.
In round of the reference network, replace the path arcs by one arc from every nonleader to the leader. Keep the same leader-to-agent arcs. Call this the ordinary star. Let be this -round reference prefix, and let be its final leader vista. These are the outputs for the network and vista reductions, respectively.
Lemma 15. For any sizes with , the labeled history-tree prefix through round , without fiber cardinalities, is the same. After round , for , group has the singleton classes
and the single nonempty suffix class . All groups have distinct histories.
Proof. In round one, the first path member receives only leader states; every other member also receives one nonleader state. The leader receives copies of the initial nonleader state. Its outdegree is . Hence all these records are independent of the group sizes, and the distinct distinguish the groups. Inductively, previously distinct classes cannot merge, since the previous history is retained. At round , the first member of the old suffix receives the previous state of the singleton at position , while every remaining suffix member receives the old suffix state. This separates one further position. Every member still receives copies of the same previous leader state and has outdegree one. The last member of each path is in its old suffix, so the leader receives exactly one old suffix state from each group and still has outdegree . These records are independent of the lengths. This proves both the partition and the equality of its labels.
In particular, at level there are exactly nonleader nodes per group and one leader node, for a total of nodes. The reference network’s ordinary star makes every one of those nodes visible in : every nonleader sends to the leader, so every nonleader node is a red-edge predecessor of the new leader node. The old leader node is its parent. All earlier nodes are visible by following parents.
Polynomial size. The reference network has agents and rounds, with nonzero arc entries over all round graphs. The numbers have bits, and has bits. The vista has nodes and edges. It can be computed by successive history partitions, using binary multiplicities throughout. Both outputs are therefore computable in polynomial time; parallel arcs are not expanded into individual input entries.
The Possible Network Sizes
Fix any one-leader realization of , on any agent set . We do not assume that its groups are paths or that nodes with singleton fibers in the reference network still have singleton fibers in this realization.
For each , let be the union of the fibers of the nodes visible at level of . Parents are visible, so . The unique leader belongs to every .
At level one, each group is represented by two nodes, its first-position node and its suffix node. Let be the sum of the cardinalities of these two fibers in the arbitrary realization. Their visible descendants at level include disjoint nonempty fibers. Therefore
Both first-level nodes of group prescribe incoming copies of the unique initial leader state. The visible leader’s first-round outdegree is , so
This is only an inequality until we prove that level one is full. Writing gives
where the second bound again uses and . Hence
Lemma 16. In every realization of , .
Proof. Suppose is proper. Every is then proper and nonempty. If , strong connectivity of round gives an arc from into this set. Its head lies in a visible level- fiber, so its tail’s level- history must be a visible incoming predecessor. The tail would belong to , a contradiction. Thus every inclusion is strict.
There are such transitions between levels 1 and . Consequently (12) gives
a contradiction.
Since level one is full, the first-round leader outdegree is now accounted for exactly by the displayed nonleader fibers; the leader’s displayed incoming record contains no leader state, so there is no leader loop. Thus
Lemma 14 applies. If there is no exact cover, it forces and all other coordinates zero, so every realization has order . If any other solution occurs, the source instance has an exact cover, and its order is .
Combining this converse with the constructions below will give
This argument shows that level one is full. It does not require later visible levels to be full, or the actual order to be known in advance.
The Alternative Networks
Suppose the source instance has an exact cover , with . Define alternative group sizes by
Their order is
Moreover,
By Lemma 15, these sizes realize exactly the same labeled path prefix through round . At its last level, every reference nonleader class is a singleton except group 0’s suffix, which has two members. In the alternative prefix, group 0’s suffix is a singleton, each selected group’s suffix has two members, and every other class is a singleton.
The leader’s vista. Keep the usual leader-to-agent arcs in the alternative final round, and set the nonleader arcs as follows. The single member of group 0’s suffix sends two parallel arcs to the leader. Within each selected group’s two-member suffix, choose one member to send to the other, and let the other send one arc to the leader. Every remaining nonleader sends one arc to the leader.
The leader receives two copies of group 0’s old suffix state, one copy of each selected group’s old suffix state, and one copy of every other old nonleader state. These are exactly its receipts in the reference network’s ordinary star. Its previous history and current outdegree also agree. Thus its final vista is .
This alternative graph is loopless and strongly connected. The leader reaches every agent directly, and every agent reaches it in at most two arcs. The doubled return arc changes that sender’s current outdegree, but not the previous history it sends; this is exactly where late outdegree awareness is used.
The nonleaders’ vistas. For this purpose, instead use the ordinary star on the alternative prefix. Every reference nonleader has a counterpart in the same old history class, because every class is nonempty in both prefixes. Such a counterpart has the same previous history, current outdegree one, and incoming multiset consisting of copies of the previous leader history. Their final vistas therefore agree.
A single ordinary-star alternative reproduces every reference nonleader vista simultaneously. Its leader need not reproduce the reference leader; the preceding alternative final graph does that. No one-to-one correspondence between the two agent sets is required.
Theorem 7. AtMostOneVista is coNP-complete, even on realizable vistas with one leader.
Proof. Output . It always has the reference realization of order . If the source instance has no exact cover, Lemma 16 and the exact integer equation show that every realization has order . If it has an exact cover, the adjusted alternative final round above gives a realization of order . Thus the complement of X3C reduces to AtMostOneVista. Membership follows from Theorem 5.
Theorem 8. SomeAgentKnows is coNP-complete, even for one-leader inputs whose round graphs are loopless.
Proof. Output the explicit reference prefix , with its ordinary-star final round. If the source instance has no exact cover, the leader has only the compatible order , so the output is a yes-instance.
If an exact cover exists, the adjusted alternative final round gives the reference leader a compatible order , while the ordinary-star alternative gives every reference nonleader the same compatible order . Since all their vistas are also realized by the reference order , no reference agent knows the order. This reduces the complement of X3C to SomeAgentKnows. Membership follows from Theorem 6.
Both reductions use loopless, strongly connected round graphs. The leader-to-agent multiplicities may be exponentially large, but have polynomial binary length.
References
- [1]Sebastian Abshoff, Markus Benter, Manuel Malatyali, and Friedhelm Meyer auf der Heide. On two-party communication through dynamic networks. In Principles of Distributed Systems (OPODIS 2013), volume 8304 of Lecture Notes in Computer Science, pages 11–22. Springer, 2013. doi:10.1007/978-3-319-03850-6_2.DOI
- [2]Dana Angluin. Local and global properties in networks of processors (extended abstract). In Proceedings of the 12th Annual ACM Symposium on Theory of Computing (STOC 1980), pages 82–93. ACM, 1980. doi:10.1145/800141.804655.
- [3]John Augustine, Gopal Pandurangan, and Peter Robinson. Distributed algorithmic foundations of dynamic networks. ACM SIGACT News, 47(1):69–98, 2016. doi:10.1145/2902945.2902959.DOI
- [4]Lars Baumgärtner, Alexandra Dmitrienko, Bernd Freisleben, Alexander Gruler, Jonas Höchst, Joshua Kühlberg, Mira Mezini, Richard Mitev, Markus Miettinen, Anel Muhamedagic, Thien Duc Nguyen, Alvar Penning, Dermot Pustelnik, Filipp Roos, Ahmad-Reza Sadeghi, Michael Schwarz, and Christian 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 2020), pages 458–467. IEEE, 2020. doi:10.1109/TrustCom50675.2020.00069.DOI
- [5]Thibaut Blanc, Giuseppe A. Di Luna, and Giovanni Viglietta. Computing in anonymous dynamic networks with one-bit communications. arXiv preprint, 2026. arXiv:2607.08358, doi:10.48550/arXiv.2607.08358.DOI
- [6]Arnaud Casteigts, Paola Flocchini, Walter Quattrociocchi, and Nicola Santoro. Time-varying graphs and dynamic networks. International Journal of Parallel, Emergent and Distributed Systems, 27(5):387–408, 2012. doi:10.1080/17445760.2012.668546.
- [7]Jérémie Chalopin and Daniël Paulusma. Graph labelings derived from models in distributed computing: A complete complexity classification. Networks, 58(3):207–231, 2011. doi:10.1002/net.20432.DOI
- [8]Bernadette Charron-Bost and Patrick Lambein-Monette. Brief announcement: Know Your Audience: Communication model and computability in anonymous networks. In Proceedings of the 43rd ACM Symposium on Principles of Distributed Computing (PODC 2024), pages 243–246. ACM, 2024. Full version: https://arxiv.org/abs/2311.17728. doi:10.1145/3662158.3662784.
- [9]Giuseppe A. Di Luna, Roberto Baldoni, Silvia Bonomi, and Ioannis Chatzigiannakis. Conscious and unconscious counting on anonymous dynamic networks. In Distributed Computing and Networking (ICDCN 2014), volume 8314 of Lecture Notes in Computer Science, pages 257–271. Springer, 2014. doi:10.1007/978-3-642-45249-9_17.DOI
- [10]Giuseppe A. Di Luna, Roberto Baldoni, Silvia Bonomi, and Ioannis Chatzigiannakis. Counting in anonymous dynamic networks under worst-case adversary. In Proceedings of the 34th IEEE International Conference on Distributed Computing Systems (ICDCS 2014), pages 338–347. IEEE, 2014. doi:10.1109/ICDCS.2014.42.DOI
- [11]Giuseppe A. Di Luna and Giovanni Viglietta. Computing in anonymous dynamic networks is linear. In Proceedings of the 63rd IEEE Symposium on Foundations of Computer Science (FOCS 2022), pages 1122–1133. IEEE, 2022. doi:10.1109/FOCS54457.2022.00108.DOI
- [12]Giuseppe A. Di Luna and Giovanni Viglietta. Efficient computation in congested anonymous dynamic networks. Distributed Computing, 38(2):95–112, 2025. doi:10.1007/s00446-025-00481-z.DOI
- [13]Giuseppe A. Di Luna and Giovanni Viglietta. Optimal computation in anonymous dynamic networks. Journal of the ACM, 73(5):30:1–30:50, 2026. doi:10.1145/3837064.DOI
- [14]Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979.
- [15]Mohsen Ghaffari, Cameron Musco, Tsvetomira Radeva, and Nancy Lynch. Distributed house-hunting in ant colonies. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC 2015), pages 57–66. ACM, 2015. doi:10.1145/2767386.2767426.DOI
- [16]Márk Jelasity and Alberto Montresor. Epidemic-style proactive aggregation in large overlay networks. In Proceedings of the 24th IEEE International Conference on Distributed Computing Systems (ICDCS 2004), pages 102–109. IEEE Computer Society, 2004. doi:10.1109/ICDCS.2004.1281573.DOI
- [17]Bernhard Korte and Jens Vygen. Combinatorial Optimization: Theory and Algorithms, volume 21 of Algorithms and Combinatorics. Springer, 5th edition, 2012. doi:10.1007/978-3-642-24488-9.DOI
- [18]Dariusz R. Kowalski and Miguel 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. doi:10.1145/3385075.DOI
- [19]Dariusz R. Kowalski and Miguel A. Mosteiro. Polynomial anonymous dynamic distributed computing without a unique leader. Journal of Computer and System Sciences, 123:37–63, 2022. doi:10.1016/j.jcss.2021.07.002.DOI
- [20]Dariusz R. Kowalski and Miguel A. Mosteiro. Anonymous adversarial dynamic networks with logarithmic memory and communication. Theoretical Computer Science, 1066:115740, 2026. doi:10.1016/j.tcs.2025.115740.DOI
- [21]Andreas Krebs and Oleg Verbitsky. Universal covers, color refinement, and two-variable counting logic: Lower bounds for the depth. In Proceedings of the 30th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2015), pages 689–700. IEEE, 2015. doi:10.1109/LICS.2015.69.DOI
- [22]Fabian Kuhn, Nancy A. Lynch, and Rotem Oshman. Distributed computation in dynamic networks. In Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC 2010), pages 513–522. ACM, 2010. doi:10.1145/1806689.1806760.DOI
- [23]Fabian Kuhn, Yoram Moses, and Rotem Oshman. Coordinated consensus in dynamic networks. In Proceedings of the 30th ACM Symposium on Principles of Distributed Computing (PODC 2011), pages 1–10. ACM, 2011. doi:10.1145/1993806.1993808.DOI
- [24]Erwan Le Merrer, Anne-Marie Kermarrec, and Laurent Massoulié. Peer to peer size estimation in large and dynamic networks: A comparative study. In Proceedings of the 15th IEEE International Symposium on High Performance Distributed Computing (HPDC 2006), pages 7–17. IEEE, 2006. doi:10.1109/HPDC.2006.1652131.DOI
- [25]Laurent Massoulié, Erwan Le Merrer, Anne-Marie Kermarrec, and Ayalvadi Ganesh. Peer counting and sampling in overlay networks: Random walk methods. In Proceedings of the 25th ACM Symposium on Principles of Distributed Computing (PODC 2006), pages 123–132. ACM, 2006. doi:10.1145/1146381.1146402.DOI
- [26]Othon Michail, Ioannis Chatzigiannakis, and Paul G. Spirakis. Naming and counting in anonymous unknown dynamic networks. In Stabilization, Safety, and Security of Distributed Systems (SSS 2013), volume 8255 of Lecture Notes in Computer Science, pages 281–295. Springer, 2013. doi:10.1007/978-3-319-03089-0_20.DOI
- [27]Angelìa Nedić, Alex Olshevsky, Asuman Ozdaglar, and John N. Tsitsiklis. On distributed averaging algorithms and quantization effects. IEEE Transactions on Automatic Control, 54(11):2506–2517, 2009. doi:10.1109/TAC.2009.2031203.DOI
- [28]Alex Olshevsky and John N. Tsitsiklis. Convergence speed in distributed consensus and averaging. SIAM Journal on Control and Optimization, 48(1):33–55, 2009. doi:10.1137/060678324.DOI
- [29]Joongseok Park and Sartaj Sahni. Power assignment for symmetric communication in wireless sensor networks. International Journal of Distributed Sensor Networks, 5(2):185–200, 2009. doi:10.1080/15501320701343992.DOI
- [30]Tansuree Sharma and Masooda Bashir. Use of apps in the COVID-19 response and the loss of privacy protection. Nature Medicine, 26(8):1165–1167, 2020. doi:10.1038/s41591-020-0928-y.DOI
- [31]Seiichiro Tani. Compression of view on anonymous networks—folded view—. IEEE Transactions on Parallel and Distributed Systems, 23(2):255–262, 2012. doi:10.1109/TPDS.2011.142.DOI
- [32]Giovanni Viglietta. History trees and their applications. In Structural Information and Communication Complexity (SIROCCO 2024), volume 14662 of Lecture Notes in Computer Science, pages 3–23. Springer, 2024. doi:10.1007/978-3-031-60603-8_1.DOI
- [33]Masafumi Yamashita and Tsunehiko Kameda. Computing on anonymous networks: Part II—decision and membership problems. IEEE Transactions on Parallel and Distributed Systems, 7(1):90–96, 1996. doi:10.1109/71.481600.DOI


