betaFeedback

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 ℓ≥1\ell\geq1 of them are designated as leaders. Every agent knows ℓ\ell and its own leader status, while the population size nn 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 nn and halt after a number of rounds equal to {nif n=ℓ2n−1if n>ℓ and ℓ=12n−2if n>ℓ and ℓ≥2.\begin{cases} n&\text{if }n=\ell\\ 2n-1&\text{if }n>\ell\text{ and }\ell=1\\ 2n-2&\text{if }n>\ell\text{ and }\ell\geq2. \end{cases} 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 nn and ℓ\ell with 1≤ℓ≤n1\leq\ell\leq n. Moreover, the local computation is polynomial (provided that each communication multigraph has at most 2poly⁡(n)2^{\operatorname{poly}(n)} arcs): in every round, each agent solves at most one linear system with up to nn variables. By standard techniques, solving Counting also enables the evaluation of any computable function of the multiset of agents' input values within 2n−12n-1 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 nn is coNP\mathsf{coNP}-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 nn of agents in the network. Knowledge of nn, 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 nn 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 3n−23n - 2 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 ℓ≥1\ell\ge1 of leaders, but not the network size nn, 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 2O(nlog⁡n)2^{O(n \log n)} 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 nn agents and has optimal worst-case complexity for every number of leaders ℓ∈[1,n]\ell\in[1,n] (§ 3). Our algorithm terminates in nn rounds when n=ℓn=\ell; in 2n−12n-1 rounds when n>ℓn>\ell and ℓ=1\ell=1; and in 2n−22n-2 rounds when n>ℓn>\ell and ℓ>1\ell>1. The algorithm works even in multigraphs, and its local computational complexity is polynomial in nn, assuming that the network has at most 2poly⁡(n)2^{\operatorname{poly}(n)} arcs in every round. Moreover, for every combination of n≥1n \ge1 and ℓ∈[1,n]\ell\in[1,n], 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 2n−12n-1 communication rounds in every case (Section C).

Furthermore, we consider the local decision underlying earlier termination: whether an agent has enough information to determine nn. 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 3n−23n-2 upper bound and the 2n−12n-1 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 2n−22n-2 upper bound for ℓ>1\ell>1 also applies to undirected networks, improving the polynomial bounds of [13, 19] to a bound linear in nn regardless of ℓ\ell. In particular, it removes the quadratic dependence on ℓ\ell in the upper bound of [13] and resolves the asymptotic dependence on ℓ\ell asked about in [32]. In the directed model, our matching lower bound also strengthens the previous bound of roughly 2n−ℓ2n-\ell rounds [13] to 2n−22n-2. Thus, somewhat surprisingly, in the directed model with n>ℓn>\ell, 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 O(n)O(n) rounds by repeatedly broadcasting all identifiers they know [22]. In fact, all agents terminate at round nn if each halts at the first round tt in which it knows at most tt identifiers. Our results show that the price of anonymity is at most n−1n-1 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 modelLeadersTermination boundReference
Undirected multigraphsℓ=1\ell= 13n−23n - 2[11]
Undirected multigraphs2≤ℓ≤n2 \le\ell\le n(ℓ2+ℓ+1)(n−1)+1(\ell^2 + \ell+ 1)(n - 1) + 1[13]
Directed simple graphs1≤ℓ≤n1 \le\ell\le n2O(nlog⁡n)2^{O(n \log n)}[32]
Directed multigraphsℓ=n\ell= nnnThis work
Directed multigraphsℓ=1<n\ell= 1 < n2n−12n - 1This work
Directed multigraphs2≤ℓ<n2 \le\ell< n2n−22n - 2This work

caption: Deterministic terminating Counting results in anonymous dynamic networks of unknown size nn and known leader count ℓ\ell. 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 G=(Gt)t≥1\mathcal{G} = (G_t)_{t \ge1} of directed multigraphs Gt=(V,Et)G_t = (V, E_t) on a fixed set VV of nn agents. Self-loops and parallel arcs are allowed. A fixed set L⊆VL \subseteq V consists of the leaders; write ℓ=∣L∣≥1\ell= |L| \ge1. For A,B⊆VA, B \subseteq V, let Et(A,B)E_t(A, B) be the multiset of arcs of GtG_t from AA to BB. Every GtG_t is strongly connected: for each nonempty proper set X⊂VX \subset V,

∣Et(X,V∖X)∣>0.(1)|E_t(X, V \setminus X)| > 0. \tag*{(1)}

Computation. Every agent runs the same deterministic algorithm, receives ℓ\ell as a common input, and starts in state s0(x)=1s_0(x) = 1 if it is a leader and s0(x)=0s_0(x) = 0 otherwise. An agent is either active or halted; initially, all agents are active. Communication round t≥1t \ge1 uses the graph Gt=(V,Et)G_t = (V, E_t). Every active agent xx observes a multiset It(x)I_t(x) containing, for every active agent yy, one copy of st−1(y)s_{t-1}(y) for each arc from yy to xx in EtE_t. Equivalently, each active agent sends its current state along every outgoing arc. Agent xx learns its outdegree dt+(x)=∣Et({x},V)∣d_t^+(x) = |E_t(\{x\}, V)| only after this communication. It then sets its new state to st(x)=update⁡(st−1(x),It(x),dt+(x))s_t(x) = \operatorname{update}(s_{t-1}(x), I_t(x), d_t^+(x)) and computes ot(x)=out⁡(st(x),ℓ)∈N∪{⊥}o_t(x) = \operatorname{out}(s_t(x), \ell) \in\mathbb{N} \cup\{\bot\}, where ⊥\bot means that it produces no output in this round. If ot(x)≠⊥o_t(x) \ne\bot, the agent outputs ot(x)o_t(x) and halts; it neither communicates nor updates its state thereafter. An algorithm A=(update⁡,out⁡)\mathcal{A} = (\operatorname{update}, \operatorname{out}) solves the Counting problem if, for every n≥1n \ge1, every dynamic network on nn agents, and every nonempty leader set L⊆VL \subseteq V, all agents eventually output nn. 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 tt rounds if no deterministic algorithm can place them in different states by then. We define the *indistinguishability classes by a sequence (Pt)t≥−1(\mathcal{P}_t)_{t\geq-1} of successively finer partitions of VV, where Pt\mathcal{P}_t refines Pt−1\mathcal{P}_{t-1} for every t≥0t\geq0. Initially, P−1={V}\mathcal{P}_{-1}=\{V\}. The partition P0\mathcal{P}_0 groups agents by leader status: P0={L,V∖L}\mathcal{P}_0=\{L,V\setminus L\} (or P0={L}\mathcal{P}_0=\{L\} if L=VL=V). For t≥1t\geq1, agents xx and yy belong to the same class of Pt\mathcal{P}_t precisely when they belonged to the same class of Pt−1\mathcal{P}_{t-1}, have the same outdegree dt+(x)=dt+(y)d_t^+(x)=d_t^+(y), and, for every class C∈Pt−1C\in\mathcal{P}_{t-1}, have equally many incoming arcs from agents in CC: that is, ∣Et(C,{x})∣=∣Et(C,{y})∣|E_t(C,\{x\})|=|E_t(C,\{y\})| (note that these arcs need not come from the same agents). An induction on tt shows that, for every deterministic algorithm, agents in the same class of Pt\mathcal{P}_t necessarily have the same state after tt 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 GG, with leader set LL, has levels −1,0,1,2,…-1,0,1,2,\ldots. For each t≥−1t\geq-1 and each indistinguishability class C∈PtC\in\mathcal{P}_t, level tt contains one abstract node vv representing the agents in CC. The fiber of vv, denoted by A(v)A(v), is the set CC. We denote the set of nodes at level tt by Ht\mathcal{H}_t. For t≥0t\geq0, a node v∈Htv\in\mathcal{H}_t is a leader node if A(v)⊆LA(v)\subseteq L, and a nonleader node otherwise. The anonymity of vv is defined as a(v)=∣A(v)∣a(v)=|A(v)|.

The parent of a node v∈Htv\in\mathcal{H}_t, with t≥0t\geq0, is the unique node u∈Ht−1u\in\mathcal{H}_{t-1} such that A(v)⊆A(u)A(v)\subseteq A(u). 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 t≥1t\geq1, u∈Ht−1u\in\mathcal{H}_{t-1}, and v∈Htv\in\mathcal{H}_t, all agents x∈A(v)x\in A(v) have the same number μt(u,v)=∣Et(A(u),{x})∣\mu_t(u,v)=|E_t(A(u),\{x\})| of incoming arcs from agents in A(u)A(u). Whenever this number is positive, the history tree contains a red edge from uu to vv of multiplicity μt(u,v)\mu_t(u,v). The agents in A(v)A(v) also have a common outdegree dt(v)=dt+(x)d_t(v)=d_t^+(x); we place this label on the black edge from vv’s parent to vv.

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 d5d_5. Black-edge labels are outdegrees and red-edge labels are multiplicities; labels equal to 1 are omitted.

Vistas. Fix an agent xx at round tt, and let v∈Htv\in\mathcal{H}_t be the node whose fiber contains xx. The vista Vt\mathcal{V}_t of xx is the subgraph of the history tree induced by all nodes that lie on a directed path from the root to vv, using black and red edges indifferently. The node vv itself, which is the vista’s unique node at level tt, is called the bottom node of Vt\mathcal{V}_t. 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 Ht\mathcal{H}_t exactly when their vistas at round tt 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 −1≤r≤t-1\leq r\leq t, let Lr\mathcal{L}_r be level rr of Vt\mathcal{V}_t, namely the set of its nodes that belong to Hr\mathcal{H}_r. These nodes are visible to xx at level rr, whereas the nodes in Hr∖Lr\mathcal{H}_r\setminus\mathcal{L}_r are hidden. We call Lr\mathcal{L}_r full if Lr=Hr\mathcal{L}_r=\mathcal{H}_r, that is, if it contains every history-tree node at that level.

The prefix ending at Lr\mathcal{L}_r is the restriction of Vt\mathcal{V}_t to the levels L−1,L0,…,Lr\mathcal{L}_{-1},\mathcal{L}_0,\ldots,\mathcal{L}_r. Equivalently, it is obtained by match-and-merging the round-rr vistas of all agents represented by nodes in Lr\mathcal{L}_r. This prefix is full if Lr\mathcal{L}_r is full. This also makes every earlier level full, since every node on such a level has a descendant at level rr 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, Hr\mathcal{H}_r denotes level rr of a history tree, and Lr\mathcal{L}_r denotes level rr of a vista Vt\mathcal{V}_t.

H1. Disjoint refinement. For r≥0r \ge0, every v∈Lrv \in\mathcal{L}_r has a parent in Lr−1\mathcal{L}_{r-1}, and the fibers of the nodes in Lr\mathcal{L}_r are pairwise disjoint. Consequently, for every u∈Lr−1u \in\mathcal{L}_{r-1},

∑w child of u in Lra(w)≤a(u)and∑v∈Lra(v)≤n.(2)\sum_{w\ \mathrm{child\ of}\ u\ \mathrm{in}\ \mathcal{L}_r} a(w) \le a(u) \qquad\text{and}\qquad \sum_{v\in\mathcal{L}_r} a(v) \le n. \tag*{(2)}

The first inequality is an equality exactly when every child of uu is visible; the second is an equality exactly when Lr\mathcal{L}_r is full.

H2. Leader accounting. The fiber of every node at level r≥0r \ge0 consists entirely of leaders or entirely of nonleaders, and every child of that node has the same leader status as its parent. Therefore,

∑v leader node in Lra(v)≤ℓ,(3)\sum_{v\ \mathrm{leader\ node\ in}\ \mathcal{L}_r} a(v) \le\ell, \tag*{(3)}

with equality on every full level.

H3. Flow-balance equations. Red multiplicities and outdegree labels count communication arcs exactly: for r≥1r \ge1, u∈Hr−1u \in\mathcal{H}_{r-1}, and v∈Hrv \in\mathcal{H}_r,

∣Er(A(u),A(v))∣=μr(u,v)a(v),∣Er(A(v),V)∣=dr(v)a(v).(4)\lvert E_r(A(u),A(v))\rvert= \mu_r(u,v)a(v), \qquad \lvert E_r(A(v),V)\rvert= d_r(v)a(v). \tag*{(4)}

Hence, counting the arcs leaving A(u)A(u) by their heads and by their tails gives

∑v∈Hrμr(u,v)a(v)=∑w child of u in Hrdr(w)a(w).(5)\sum_{v\in\mathcal{H}_r} \mu_r(u,v)a(v) = \sum_{w\ \mathrm{child\ of}\ u\ \mathrm{in}\ \mathcal{H}_r} d_r(w)a(w). \tag*{(5)}

H4. Delay until a level is full. For every vista VtV_t and r≥0r \ge0,

t≥r+n−1⟹Lr=Hr.(6)t \ge r + n - 1 \Longrightarrow\mathcal{L}_r = \mathcal{H}_r. \tag*{(6)}

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 n−1n - 1 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 r≥0r \ge0, a level Lr\mathcal{L}_r of a vista is flat if every node in Lr−1\mathcal{L}_{r-1} has exactly one child in Lr\mathcal{L}_r.

Lemma 1. Let Lr\mathcal{L}_r be a full and flat level of a vista, with r≥1r \ge1. The flow equations on Lr\mathcal{L}_r, together with ℓ\ell, uniquely determine the anonymities of the nodes of Lr\mathcal{L}_r.

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 2n−12n - 1 rounds.3 Section 3.2 improves this bound when n=ℓn = \ell or ℓ>1\ell> 1, and proves matching lower bounds.

The Core Algorithm

Outline. Every agent constructs its vista and, for m=ℓ,ℓ+1,…m = \ell, \ell+ 1, \ldots, tests candidate mm at round 2m−12m - 1, using the prefix ending at Lm\mathcal{L}_m. We will prove that every m<nm < n is rejected, whereas m=nm = n is accepted. The test consists of the following steps.

  1. Check the visible structure. Reject mm unless L0\mathcal{L}_0 contains the leader node, each Lr\mathcal{L}_r with 0≤r≤m0 \le r \le m contains at most mm nodes, and every node in Lr\mathcal{L}_r, for 0≤r<m0 \le r < m, has a child in Lr+1\mathcal{L}_{r+1}. Reject mm if none of L1,…,Lm\mathcal{L}_1, \ldots, \mathcal{L}_m is flat.

  1. Choose the anchor. Let hh, with 1≤h≤m1 \le h \le m, be the largest index such that Lh\mathcal{L}_h is flat. We call Lh\mathcal{L}_h the anchor. Clearly, Lh\mathcal{L}_h and Lh−1\mathcal{L}_{h-1} contain the same number of nodes.

  1. Solve the anchor. Introduce one unknown b(v)b(v) for each node v∈Lhv \in\mathcal{L}_h, and solve the flow equations for u∈Lh−1u \in\mathcal{L}_{h-1}, with both sums restricted to nodes in Lh\mathcal{L}_h, together with

∑v leader node in Lhb(v)=ℓ.\sum_{v\ \text{leader node in }\mathcal{L}_h} b(v) = \ell.

Reject mm unless this system has a unique solution over Q\mathbb{Q}. Then reject mm unless every b(v)b(v) in this solution is a positive integer and ∑v∈Lhb(v)=m\sum_{v \in\mathcal{L}_h} b(v) = m. We call the resulting values the candidate anonymities of the nodes of Lh\mathcal{L}_h.

  1. 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 r=h−1,h−2,…,−1r=h-1,h-2,\ldots,-1 and u∈Lru\in\mathcal{L}_r, set

b(u)=∑v child of u in Lr+1b(v).\mathbf{b}(u)=\sum_{v\text{ child of }u\text{ in }\mathcal{L}_{r+1}}\mathbf{b}(v).

Reject mm unless, for every 1≤r<h1\le r<h and u∈Lr−1u\in\mathcal{L}_{r-1},

∑v∈Lrμr(u,v)b(v)=∑w child of u in Lrdr(w)b(w).\sum_{v\in\mathcal{L}_r}\mu_r(u,v)\mathbf{b}(v)=\sum_{w\text{ child of }u\text{ in }\mathcal{L}_r}d_r(w)\mathbf{b}(w).
  1. Check the suffix. For each v∈Lhv\in\mathcal{L}_h, let q(v)q(v) be the number of its descendants in Lm\mathcal{L}_m, counting vv itself when h=mh=m. Reject mm if q(v)>b(v)q(v)>\mathbf{b}(v) for some vv. Otherwise, accept mm, output mm, and halt.

Thus a test solves only one linear system over Q\mathbb{Q}. 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 vv in the prefix ending at the anchor Lh\mathcal{L}_h. 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:

c(v)=min⁡{a(v)−1,b(v)}.c(v)=\min\{\mathbf{a}(v)-1,\mathbf{b}(v)\}.

The credit is used only in the proof, since the actual anonymities are unknown to the agents. For 0≤r≤h0\le r\le h, let Φr=∑v∈Lrc(v)\Phi_r=\sum_{v\in\mathcal{L}_r}c(v) be the total credit on Lr\mathcal{L}_r. In the following three lemmas and their proofs, we assume that candidate mm passes Steps 1–4; the level index rr ranges from 1 to hh. Together, the lemmas show that total credit cannot increase, and that m=nm=n 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 v1,…,vkv_1,\ldots,v_k be the children of u∈Lr−1u\in\mathcal{L}_{r-1} in Lr\mathcal{L}_r. Then ∑i=1kc(vi)≤c(u)\sum_{i=1}^{k}c(v_i)\le c(u). If equality holds and a(vj)≤b(vj)\mathbf{a}(v_j)\le\mathbf{b}(v_j) for some child vjv_j, then uu has exactly one child v1v_1; moreover, A(v1)=A(u)\mathbf{A}(v_1)=\mathbf{A}(u) and b(v1)=b(u)\mathbf{b}(v_1)=\mathbf{b}(u).

Proof. Step 1 gives k≥1k\ge1, H1 gives ∑ia(vi)≤a(u)\sum_i\mathbf{a}(v_i)\le\mathbf{a}(u), and Step 4 gives ∑ib(vi)=b(u)\sum_i\mathbf{b}(v_i)=\mathbf{b}(u). Thus,

∑i=1kc(vi)=∑i=1kmin⁡{a(vi)−1,b(vi)}≤min⁡{∑i=1k(a(vi)−1),∑i=1kb(vi)}≤min⁡{a(u)−1,b(u)}=c(u).\sum_{i=1}^{k}c(v_i)=\sum_{i=1}^{k}\min\{\mathbf{a}(v_i)-1,\mathbf{b}(v_i)\}\le\min\left\{\sum_{i=1}^{k}(\mathbf{a}(v_i)-1),\sum_{i=1}^{k}\mathbf{b}(v_i)\right\}\le\min\{\mathbf{a}(u)-1,\mathbf{b}(u)\}=c(u).

Suppose equality holds and a(vj)≤b(vj)\mathbf{a}(v_j)\le\mathbf{b}(v_j) for some child vjv_j. Then c(vj)=a(vj)−1<b(vj)c(v_j)=\mathbf{a}(v_j)-1<\mathbf{b}(v_j). Since every other child has credit at most its candidate anonymity, c(u)=∑ic(vi)<∑ib(vi)=b(u)c(u)=\sum_i c(v_i)<\sum_i\mathbf{b}(v_i)=\mathbf{b}(u). The definition of credit therefore gives c(u)=a(u)−1c(u)=\mathbf{a}(u)-1. Each visible child viv_i contributes at most a(vi)−1\mathbf{a}(v_i)-1 units of credit, so k≥2k\ge2 would give total credit at most a(u)−2<c(u)\mathbf{a}(u)-2<c(u), contradicting equality. Thus uu has a unique visible child, v1v_1; if v1v_1 failed to represent an agent in A(u)\mathbf{A}(u), its anonymity would be at most a(u)−1\mathbf{a}(u)-1, which would again give total credit at most a(u)−2<c(u)\mathbf{a}(u)-2<c(u). Thus v1v_1 represents all of A(u)\mathbf{A}(u), and Step 4 gives b(v1)=b(u)\mathbf{b}(v_1)=\mathbf{b}(u).

We now use the flow equations to study nodes with the smallest ratio of actual to candidate anonymity. For every v∈Lr−1∪Lrv\in\mathcal{L}_{r-1}\cup\mathcal{L}_r, define its ratio as ρ(v)=a(v)/b(v)\rho(v)=\mathbf{a}(v)/\mathbf{b}(v). Let α=min⁡v∈Lrρ(v)\alpha=\min_{v\in\mathcal{L}_r}\rho(v), let D={v∈Lr:ρ(v)=α}\mathcal{D}=\{v\in\mathcal{L}_r:\rho(v)=\alpha\}, and let QQ be the set of parents of nodes in D\mathcal{D}. The next lemma shows that if the nodes in D\mathcal{D} collectively represent the same agents as their parents, then they represent all agents in the network.

Lemma 3. If ⋃u∈QA(u)=⋃v∈DA(v)\bigcup_{u\in Q} A(u)=\bigcup_{v\in D} A(v), then Lr\mathcal{L}_r is full and every node in it has ratio α\alpha.

Proof. Let SS be the common set of agents in the stated equality. Every child in Hr\mathcal{H}_r of a node in QQ must belong to DD, 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 SS gives

∣Er(S,V)∣=∑v∈Ddr(v)a(v)=α∑v∈Ddr(v)b(v)=α∑u∈Q∑w∈Lrw child of udr(w)b(w)=α∑u∈Q∑w∈Lrμr(u,w)b(w)≤∑u∈Q∑w∈Lrμr(u,w)a(w)≤∣Er(S,V)∣.(7)\begin{aligned} |E_r(S,V)| &= \sum_{v\in D}d_r(v)a(v)=\alpha\sum_{v\in D}d_r(v)b(v)=\alpha\sum_{u\in Q}\sum_{\substack{w\in\mathcal{L}_r\\ w\text{ child of }u}}d_r(w)b(w)\\ &=\alpha\sum_{u\in Q}\sum_{w\in\mathcal{L}_r}\mu_r(u,w)b(w)\leq\sum_{u\in Q}\sum_{w\in\mathcal{L}_r}\mu_r(u,w)a(w)\leq|E_r(S,V)|. \tag*{(7)} \end{aligned}

The first equality counts arcs by their tails using H3; the second uses the ratio α\alpha of each node in DD. The third groups the nodes in DD by their unique parents in QQ; the fourth sums the candidate flow equations over QQ (Step 3 for r=hr=h and Step 4 for r<hr<h). The first inequality uses αb(w)≤a(w)\alpha b(w)\leq a(w). The last inequality holds because its left-hand side counts only arcs from SS 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 SS to agents in the fiber of a visible node whose ratio is larger than α\alpha; the second forbids arcs to agents in the fibers of hidden nodes. Hence every arc from SS ends at an agent represented by a node in DD, and therefore at an agent in SS. Since SS is nonempty, strong connectivity forces S=VS=V. Hence D=HrD=\mathcal{H}_r, proving both conclusions. □\square

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 1≤r≤h1\leq r\leq h, Φr≤Φr−1\Phi_r\leq\Phi_{r-1}. If equality holds for any rr, then m=nm=n.

Proof. Summing the inequalities from Lemma 2 over Lr−1\mathcal{L}_{r-1} gives Φr≤Φr−1\Phi_r\leq\Phi_{r-1}. Suppose that Φr=Φr−1\Phi_r=\Phi_{r-1}. Every one of these inequalities must then hold with equality, so for every u∈Lr−1u\in\mathcal{L}_{r-1},

∑v child of uv∈Lrc(v)=c(u).(8)\sum_{\substack{v\text{ child of }u\\ v\in\mathcal{L}_r}}c(v)=c(u). \tag*{(8)}

Let α\alpha, DD, QQ be as in Lemma 3. Step 3 and backward propagation make the candidate anonymities of the leader nodes on Lr\mathcal{L}_r sum to ℓ\ell, whereas H2 bounds their actual anonymities by ℓ\ell. Thus some leader node has ratio at most 1, so α≤1\alpha\leq1. Every v∈Dv\in D therefore satisfies a(v)≤b(v)a(v)\leq b(v). Its parent uu satisfies (2), so Lemma 2 implies that vv is the unique child of uu and A(v)=A(u)A(v)=A(u). Thus each parent in QQ and its unique child in DD have the same fiber.

Lemma 3 now implies that Lr\mathcal{L}_r is full and every node has ratio α\alpha. In particular, its leader nodes have total actual anonymity ℓ\ell and total candidate anonymity ℓ\ell. Since a(v)=αb(v)a(v)=\alpha b(v), these two sums give ℓ=αℓ\ell=\alpha\ell, hence α=1\alpha=1 because ℓ>0\ell>0. All actual and candidate anonymities on Lr\mathcal{L}_r therefore agree. Step 3 sets the total candidate anonymity at the anchor to mm, and Step 4 preserves this total at every earlier level. Since Lr\mathcal{L}_r is full, its actual anonymities sum to nn. Thus n=∑v∈Lra(v)=∑v∈Lrb(v)=mn=\sum_{v\in\mathcal{L}_r}a(v)=\sum_{v\in\mathcal{L}_r}b(v)=m. □\square

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 1≤ℓ≤n1\leq\ell\leq n, the core algorithm makes all agents output nn and halt at round 2n−12n-1. All local computations take time polynomial in nn (assuming the network has at most 2poly⁡(n)2^{\operatorname{poly}(n)} arcs per round).

Proof. Until the first agent halts, every agent maintains its vista. Fix a candidate m<nm<n. If its test reaches Step 5, Lemma 4 and integrality show that each of the first hh rounds loses at least one unit of credit. Step 3 gives total candidate anonymity mm at the anchor, and backward propagation preserves this total at every earlier level. The leader node in L0\mathcal{L}_0 has actual and candidate anonymity ℓ\ell, and hence credit ℓ−1\ell-1. Any remaining credit comes from the single nonleader node (if it exists and is visible), and is at most the remaining candidate anonymity m−ℓm-\ell. Thus

Φh≤Φ0−h≤(ℓ−1)+(m−ℓ)−h=m−h−1.\Phi_h \le\Phi_0-h \le(\ell-1)+(m-\ell)-h=m-h-1.

For each v∈Lhv\in\mathcal{L}_h, its q(v)q(v) descendants in Lm\mathcal{L}_m have disjoint nonempty fibers. Hence q(v)≤a(v)q(v)\le a(v), while Step 5 checks that q(v)≤b(v)q(v)\le b(v). Therefore, observing that ∑v∈Lhq(v)=∣Lm∣\sum_{v\in\mathcal{L}_h}q(v)=|\mathcal{L}_m|, we have

Φh=∑v∈Lhc(v)=∑v∈Lhmin⁡{a(v)−1,b(v)}≥∑v∈Lh(q(v)−1)=∣Lm∣−∣Lh∣.\Phi_h=\sum_{v\in\mathcal{L}_h}c(v)=\sum_{v\in\mathcal{L}_h}\min\{a(v)-1,b(v)\}\ge\sum_{v\in\mathcal{L}_h}(q(v)-1)=|\mathcal{L}_m|-|\mathcal{L}_h|.

Every level after the anchor is nonflat, and Step 1 ensures that every node before Lm\mathcal{L}_m has a child at the next level. Each of the m−hm-h remaining transitions therefore increases the number of visible nodes, giving ∣Lm∣−∣Lh∣≥m−h|\mathcal{L}_m|-|\mathcal{L}_h|\ge m-h. Combining the two bounds on Φh\Phi_h yields m−h≤m−h−1m-h\le m-h-1, a contradiction. Thus every agent rejects all candidates m<nm<n and remains active.

Consequently, all agents still maintain their vistas when m=nm=n is tested at round 2n−12n-1. H4 implies that Ln\mathcal{L}_n is full, and hence the entire prefix ending there is full, as well. Since every node before Ln\mathcal{L}_n has a child at the next level, the number of nodes cannot increase in all nn transitions: L0\mathcal{L}_0 is nonempty and no level has more than nn nodes. Thus some level among L1,…,Ln\mathcal{L}_1,\ldots,\mathcal{L}_n 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 q(v)≤a(v)=b(v)q(v)\le a(v)=b(v) at the anchor. Hence every agent accepts nn and halts at round 2n−12n-1.

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 nn variables by exact Gaussian elimination with fractions kept reduced, which takes time polynomial in nn [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 nn.

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 n=ℓn=\ell. At round ℓ\ell, if an agent’s vista contains no nonleader node at level L0\mathcal{L}_0, then the agent outputs ℓ\ell and halts. Indeed, if n>ℓn>\ell, condition (SC) would make a nonleader visible within ℓ\ell rounds. Thus, when n=ℓn=\ell, all agents correctly halt at round nn.

Upper bound: case ℓ>1\ell>1. Once the previous test has failed, every agent knows that n>ℓn>\ell. Assume that ℓ>1\ell>1. Each agent then tests candidates m=ℓ+1,ℓ+2,…m=\ell+1,\ell+2,\ldots using exactly Steps 1–5 of Section 3.1, except that the test is performed at round 2m−22m-2 (instead of 2m−12m-1), with final level Lm−1\mathcal{L}_{m-1} (instead of Lm\mathcal{L}_m). Step 1 requires children only through Lm−2\mathcal{L}_{m-2}, Step 2 chooses 1≤h≤m−11\le h\le m-1, and Step 5 counts descendants in Lm−1\mathcal{L}_{m-1}. The bound on nodes per level and the total candidate anonymity remain mm. At m=nm=n, H4 makes the prefix ending at Ln−1\mathcal{L}_{n-1} full. Moreover, L0\mathcal{L}_0 has a leader node and a nonleader node, so L1,…,Ln−1\mathcal{L}_1,\ldots,\mathcal{L}_{n-1} cannot all be nonflat. Thus the true candidate is accepted at round 2n−22n-2. Note that this part of the proof did not require ℓ>1\ell>1. It remains to show that the algorithm does not incorrectly terminate when ℓ<m<n\ell< m < n; for this part, ℓ≥2\ell\ge2 is needed. If such a candidate mm passes with anchor Lh\mathcal{L}_h, the proof of Theorem 1 gives

m−1−h≥Φh≥∣Lm−1∣−∣Lh∣≥m−1−h.m - 1 - h \ge\Phi_h \ge\lvert\mathcal{L}_{m-1} \rvert- \lvert\mathcal{L}_h \rvert\ge m - 1 - h.

Thus every inequality is tight. This forces the nodes of Lm−1\mathcal{L}_{m-1} to have singleton fibers, which together cover all fibers of Lh\mathcal{L}_h. Moreover, at round 2m−22m - 2, the backward-expansion argument used for H4 guarantees at least mm represented agents at level Lm−1\mathcal{L}_{m-1}. Since Step 1 permits at most mm nodes in Lm−1\mathcal{L}_{m-1}, this level has exactly mm nodes, each representing one agent.

Every visible node from Lh\mathcal{L}_h through Lm−1\mathcal{L}_{m-1} therefore has anonymity equal to its number of descendants in Lm−1\mathcal{L}_{m-1}. At the anchor, these descendant counts sum to mm. Step 5 bounds each candidate anonymity below by its descendant count, and the candidate anonymities also sum to mm; hence all candidate anonymities at the anchor are correct. Let SS be the set of agents represented at Lh\mathcal{L}_h (and hence at every subsequent level through Lm−1\mathcal{L}_{m-1}). Since ∣S∣=m<n\lvert S\rvert= m < n, some agents are outside SS. This immediately implies that h=m−1h = m - 1, for otherwise, in round h+1h + 1, the agents in SS would only receive messages from SS, contradicting (SC).

Since h=m−1h = m - 1, the leader equation of Step 3 applied to Lh=Lm−1\mathcal{L}_h = \mathcal{L}_{m-1} implies that SS contains all ℓ\ell leaders. Now the idea is to count how many nonleaders in SS have become distinguishable from every agent outside SS. At round 0, none have: all nonleaders belong to the same fiber, including those outside SS. Then, the flow equations for candidate anonymities imply that agents whose whole fiber is already inside SS send messages only to SS. Strong connectivity forces a message from these fibers to someone outside their union. That recipient must still be in SS, 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 SS from all outsiders. Once separated, it stays separated, because fibers only split. But there are m−1m - 1 rounds and only m−ℓm - \ell nonleaders in SS. When ℓ≥2\ell\ge2, there are too few nonleaders for this to happen in every round. Thus, a false candidate m<nm < n could not have passed. Section C gives the complete argument.

Matching lower bounds. The previous combined upper bounds are tight in every case. For n=ℓn = \ell, consider two static bidirected paths. One consists of nn leaders; the other consists of a chain of nn leaders followed by one nonleader. The endpoint leader in each network has the same vista through round n−1n - 1. Hence that leader cannot terminate before round nn.

For n>ℓn > \ell and ℓ=1\ell= 1, two static bidirected paths of orders nn and n+1n + 1, with the leader at one endpoint and a loop at the other, give the same leader vista through round 2n−22n - 2. This construction and the resulting lower bound already appear in [13].

Finally, suppose that n>ℓn > \ell and ℓ≥2\ell\ge2. We construct two dynamic networks G\mathcal{G} and G′\mathcal{G}' of orders nn and n+ℓ−1n + \ell- 1, respectively, each with ℓ\ell leaders. Let xx and x′x' be leaders in G\mathcal{G} and G′\mathcal{G}', respectively. We keep their vistas identical through round 2n−32n - 3. We first handle n=ℓ+1n = \ell+ 1, when G\mathcal{G} has one nonleader and G′\mathcal{G}' has ℓ\ell (refer to Figure 2).

Figure 2. The basic lower-bound pair for ℓ=3\ell= 3 and n=4n = 4. Blue fill denotes leaders and yellow fill denotes nonleaders. Green rings mark xx and x′x', whose vistas agree through round 5=2n−35 = 2n - 3. Edge labels are parallel-arc multiplicities; labels equal to 11 are omitted.

  • First ℓ−1\ell- 1 rounds. In G\mathcal{G}, every round graph is a bidirected star centered at its only nonleader. In each round, G′\mathcal{G}' selects a different leader other than x′x', 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 G\mathcal{G} and all leaders in G′\mathcal{G}' not yet selected have the same vista, while all nonleaders in both networks also have the same vista.

  • Next ℓ−1\ell- 1 rounds. In each round, G\mathcal{G} selects its only nonleader and a different leader other than xx. Meanwhile, G′\mathcal{G}' selects x′x' 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 G\mathcal{G} sends only to the selected leader; every remaining agent in G′\mathcal{G}' 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 G\mathcal{G} not yet selected in this phase have the same vista as x′x', while the nonleaders in G′\mathcal{G}' not yet selected in this phase have the same vista as the only nonleader in G\mathcal{G}.

  • Final stage. Each network becomes a directed cycle through all its agents. The nonleader in G\mathcal{G} and the nonleader in G′\mathcal{G}' left unselected in the second phase send directly to xx and x′x', respectively. Their identical old states give xx and x′x' one further round of identical vistas.

For larger nn, 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 ℓ−1\ell- 1 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 xx, respectively x′x', and repeat this cycle for one additional round: the extra communication hop keeps the vistas of xx and x′x' identical for one round longer. Thus adding one nonleader to each network extends the previous construction by two rounds, making vistas agree through round 2n−32n - 3. 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

T(n,ℓ)={nif n=ℓ,2n−1if n>ℓ and ℓ=1,2n−2if n>ℓ and ℓ≥2.T(n,\ell) = \begin{cases} n & \text{if } n = \ell,\\ 2n - 1 & \text{if } n > \ell\text{ and } \ell= 1,\\ 2n - 2 & \text{if } n > \ell\text{ and } \ell\ge2. \end{cases}

All local computations take time polynomial in nn (assuming the network has at most 2poly⁡(n)2^{\operatorname{poly}(n)} 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 nn 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 nn.4

The input consists of a vista V\mathcal{V} and the leader count ℓ\ell. 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 ℓ\ell leaders in which some agent has vista V\mathcal{V}. Its order is its number of agents. The order spectrum Spec⁡ℓ(V)\operatorname{Spec}_{\ell}(\mathcal{V}) is the set of orders of all such realizations. A realizable vista determines nn 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 ∣Spec⁡ℓ(V)∣≤1|\operatorname{Spec}_{\ell}(\mathcal{V})| \le1, 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 nn.

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 ν\nu be the number of nonroot nodes in the given vista, tt its final round, and MM the largest of its numerical labels and the leader count ℓ\ell. Suppose two networks of different sizes are compatible with V\mathcal{V}. In each network, choose an agent holding V\mathcal{V} as the observer. An agent is influential if its information can reach the observer by round tt through a chain of messages sent in increasing rounds; the observer itself is influential. Tracing these dependencies backward shows that at most K=(1+νM)tK=(1+\nu M)^t agents are influential in either network.

If every agent in both networks is influential, both sizes are at most KK 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 K+ℓ+1K+\ell+1 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 K+ℓ+2K+\ell+2.

Consequently, whenever two different orders are compatible with V\mathcal{V}, two can be chosen that are at most exponential in the input length (including the binary encoding of ℓ\ell). 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 tt 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 tt matching V\mathcal{V} and ℓ\ell, 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 S1,…,SmS_1,\ldots,S_m over 3q3q elements; an exact cover consists of qq triples containing each element exactly once. We may assume q≥2q \ge2, 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 U={0,…,5}U = \{0,\ldots,5\} and the exact cover S1={0,1,2}S_1 = \{0,1,2\}, S2={3,4,5}S_2 = \{3,4,5\}. Here q=2q = 2 and B=q+3=5B = q + 3 = 5. Blue fill marks the leader λ\lambda; yellow fill marks nonleaders. Shaded sectors identify the special group 0 and groups 1, 2, corresponding to S1S_1, S2S_2. In rounds 1–4, each group forms a directed path ending at λ\lambda. In every round, the leader has cic_i parallel outgoing arcs to each agent in group ii. Each triple is encoded by ci=B6+∑e∈SiBec_i = B^6 + \sum_{e \in S_i} B^e for i=1,2i = 1, 2, giving c1=15656c_1 = 15656 and c2=19500c_2 = 19500; the special coefficient is c0=2B6+∑e=05Be=35156=c1+c2c_0 = 2B^6 + \sum_{e=0}^{5} B^e = 35156 = c_1 + c_2. The reference and alternative group sizes are (6,5,5)(6,5,5) and (5,6,6)(5,6,6), respectively. Thus the leader’s outdegree is C=6c0+5c1+5c2=5c0+6c1+6c2=386716C = 6c_0 + 5c_1 + 5c_2 = 5c_0 + 6c_1 + 6c_2 = 386716 in both networks, although their orders are 17 and 18. The right panel shows their common leader vista after round 5. At level 4, viv_i represents the last one or two agents of group ii; 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 v0v_0 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 B=q+3B=q+3. We construct a reference network with one leader and m+1m+1 groups of nonleaders: group j≥1j \ge1 corresponds to triple SjS_j, and group 0 is an additional special group. Each triple group contains BB agents, while group 0 contains B+1B+1, giving N0=2+(m+1)BN_0=2+(m+1)B agents altogether. Within each group, arrange the agents along a directed path whose last agent sends to the leader. The leader also sends cic_i parallel messages to every agent in group ii. We choose these multiplicities to encode the triples. Number the universe elements 0,…,3q−10,\ldots,3q-1, and define

cj=B3q+∑e∈SjBe(1≤j≤m),c0=A=qB3q+∑e=03q−1Be.c_j = B^{3q} + \sum_{e\in S_j} B^e \quad(1\le j\le m), \qquad c_0 = A = qB^{3q} + \sum_{e=0}^{3q-1} B^e.

In base BB, each triple coefficient has three element digits equal to 1, together with a leading digit 1. The target AA has every element digit equal to 1 and leading digit qq. Thus the coefficients of qq selected triples sum to AA exactly when they form an exact cover: the element digits require every element to occur once, and carries are prevented due to q<Bq<B.

Use the communication graph described above for the first B−1B-1 rounds. In round BB, keep the leader’s outgoing arcs, but replace the path arcs by one arc from every nonleader directly to the leader. Let V\mathcal{V} be the leader’s vista after this final round. Thus, the reference network is always a realization of V\mathcal{V}, 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 qq triple groups in the cover. As before, in every round the leader has cic_i parallel outgoing arcs to every agent in group ii. Because the selected triples cover every element exactly once, their coefficients sum to AA. The leader therefore loses AA outgoing arcs through the removal and gains exactly AA through the additions. Its outdegree is unchanged, although the network now has N0+q−1>N0N_0 + q - 1 > N_0 agents.

For the first B−1B - 1 rounds, arrange each group as a directed path ending at the leader, as in the reference network. In round BB, 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 BB rounds the leader has the same vista V\mathcal{V} in both networks, with BB visible nodes per group at level B−1B - 1.

The converse. It remains to prove that if the X3C instance has no exact cover, every realization of V\mathcal{V} has exactly N0N_0 agents. The BB visible nodes of each group at level B−1B - 1 require at least BB agents, while the leader’s prescribed outdegree permits at most qq 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 B−2=q+1B - 2 = q + 1 transitions to level B−1B - 1. Only qq agents can be lost while retaining BB 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 N0N_0. 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 O(n)O(n) rounds using O(nlog⁡n)O(n \log n)-bit messages, or in O(n2)O(n^2) rounds using O(log⁡n)O(\log n)-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 O(D)O(D) rounds, where DD 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 O(log⁡n)O(\log n)-bit messages, Abshof et al. [1] relate Counting to two-party token dissemination. They show that transmitting Θ(n)\Theta(n) tokens between two designated nodes can be reduced to Counting in a network with O(n)O(n) 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 NN on the network size and a topology chosen independently of the algorithm’s random choices. For any fixed 0<ε<1/20 < \varepsilon< 1/2, it terminates in O(n)O(n) rounds and returns an estimate n~\widetilde{n} satisfying ∣n~−n∣≤εn|\widetilde{n}-n| \le\varepsilon n with high probability in NN. 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 O(n8log⁡2n)O(n^8 \log^2 n). Their subsequent work [19] extended the approach to a known number ℓ≥1\ell\ge1 of leaders and improved the bound to O(n4+εlog⁡3n/ℓ)O(n^{4+\varepsilon} \log^3 n/\ell), for every fixed ε>0\varepsilon> 0. 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 3n−23n-2 rounds. A successive work [13] handles a known number ℓ≥1\ell\ge1 of leaders and, when the network is connected in every round, gives a termination bound of (ℓ2+ℓ+1)(n−1)+1(\ell^2+\ell+1)(n-1)+1. It also gives a 2n−22n-2-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 2n−12n-1 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 O(log⁡n)O(\log n)-bit messages, including a terminating Counting algorithm with a unique leader that takes O(n3)O(n^3) rounds. Blanc, Di Luna, and Viglietta [5] study one-bit broadcasts; with a unique leader, their Counting algorithm stabilizes in O(n3log⁡2n)O(n^3 \log^2 n) rounds, and a known upper bound on nn 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 DD: information from any agent can reach every other agent within DD 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 ℓ≥1\ell\ge1 of leaders, their approach can be used to estimate the fraction p=ℓ/np = \ell/n of leaders. Rounding ℓ/p^\ell/\hat{p}, where p^\hat{p} is the current estimate, then yields a Counting algorithm whose output eventually stabilizes at nn. 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 O(Dn2Dlog⁡n)O(Dn^{2D}\log n) rounds. When the network is strongly connected in every round, D≤n−1D \le n - 1 holds, and so this bound is 2O(nlog⁡n)2^{O(n\log n)}. 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 2n−22n - 2 rounds, whereas the terminating algorithm has a 2O(nlog⁡n)2^{O(n\log n)} 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 nn if the network has at most 2poly⁡(n)2^{\operatorname{poly}(n)} 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 2n−22n - 2 termination bound for Counting remains tight for simple directed round graphs, with no loops or parallel arcs, when 2≤ℓ<n2 \le\ell< n (for one leader, a (2−o(1))n(2 - o(1))n 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 nn, 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 nn.

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 Lr\mathcal{L}_r be a full and flat level of a vista, with r≥1r \ge1. The flow equations on Lr\mathcal{L}_r, together with ℓ\ell, uniquely determine the anonymities of the nodes of Lr\mathcal{L}_r.

Proof. Because Lr\mathcal{L}_r is flat, every u∈Lr−1u \in\mathcal{L}_{r-1} has a unique child v∈Lrv \in\mathcal{L}_r; since Lr\mathcal{L}_r is full, A(u)=A(v)A(u) = A(v). Let k=∣Lr∣k = |\mathcal{L}_r|, and index these parent-child pairs as (ui,vi)(u_i, v_i), for 1≤i≤k1 \le i \le k.

Form the square matrix MM whose row ii corresponds to uiu_i and whose column jj corresponds to vjv_j, with entries

Mij={μr(ui,vj)−dr(vj)if i=j,μr(ui,vj)otherwise.M_{ij} = \begin{cases} \mu_r(u_i,v_j) - d_r(v_j) & \text{if } i = j,\\ \mu_r(u_i,v_j) & \text{otherwise.} \end{cases}

Let xx be the vector of anonymities, with xi=a(vi)>0x_i = a(v_i) > 0 for 1≤i≤k1 \le i \le k. Since Lr\mathcal{L}_r is full, the flow equation (Flow) gives Mx=0Mx = 0, with x>0x > 0.

For i≠ji \ne j, the entry MijM_{ij} is nonnegative and is positive exactly when GrG_r has an arc from A(vi)A(v_i) to A(vj)A(v_j). Thus the digraph with arcs i→ji \to j whenever i≠ji \ne j and Mij>0M_{ij} > 0 is obtained from GrG_r by contracting these fibers and discarding loops. It is therefore strongly connected.

We prove that every solution Mz=0Mz = 0 is proportional to xx. Put λ=max⁡izi/xi\lambda= \max_i z_i/x_i and w=λx−zw = \lambda x - z. Then w≥0w \ge0, Mw=0Mw = 0, and some coordinate wiw_i is zero. The equation in row ii gives

∑j≠iMijwj=0.\sum_{j \ne i} M_{ij}w_j = 0.

Every summand is nonnegative, so wj=0w_j = 0 for every j≠ij \ne i with Mij>0M_{ij} > 0. Repeating this argument along directed paths shows that every coordinate is zero. Hence z=λxz = \lambda x, and the nullspace of MM is spanned by xx.

Finally, since Lr\mathcal{L}_r is full, H2 gives

∑v leader node in Lra(v)=ℓ.\sum_{v\ \text{leader node in }\mathcal{L}_r} a(v) = \ell.

Since z=λxz = \lambda x, the entries of zz corresponding to leader nodes sum to λℓ\lambda\ell. If zz also satisfies the leader-count equation above, this sum equals ℓ\ell. Since ℓ>0\ell> 0, we obtain λ=1\lambda= 1 and hence z=xz = x. Thus the flow equations together with the leader-count equation uniquely determine the anonymities. □\square

Causal Support

Fix an agent xx at round tt. Its causal support is the sequence Γ0,…,Γt\Gamma_0, \ldots, \Gamma_t defined by

Γt={x},Γr−1=Γr∪{y∈V:∣Er({y},Γr)∣>0}(1≤r≤t).\Gamma_t = \{x\}, \qquad\Gamma_{r-1} = \Gamma_r \cup\{y \in V : |E_r(\{y\}, \Gamma_r)| > 0\} \qquad(1 \le r \le t).

Thus Γr\Gamma_r consists of the agents whose round-rr states are used, directly or through later states, to construct the round-tt vista of xx. For 0≤r≤t0 \le r \le t, a node v∈Hrv \in\mathcal{H}_r belongs to this vista precisely when

A(v)∩Γr≠∅.A(v) \cap\Gamma_r \ne\varnothing.

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 Γr−1\Gamma_{r-1}.

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 VtV_t, the fibers of the nodes in Lr\mathcal{L}_r, where 0≤r≤t0 \le r \le t, together contain at least min⁡{n,t−r+1}\min\{n,t-r+1\} agents.

Proof. Use the causal support from Section B, starting with Γt={x}\Gamma_t=\{x\}. Whenever Γj≠V\Gamma_j \ne V, strong connectivity gives an arc from its complement into it in round jj, so ∣Γj−1∣>∣Γj∣|\Gamma_{j-1}| > |\Gamma_j|. Hence ∣Γr∣≥min⁡{n,t−r+1}|\Gamma_r| \ge\min\{n,t-r+1\}, and every agent of Γr\Gamma_r belongs to a visible fiber.

Case n=ℓn=\ell. At round ℓ\ell, if an agent’s level L0\mathcal{L}_0 contains no nonleader node, it outputs ℓ\ell and halts. If n>ℓn > \ell, Lemma 5 places at least ℓ+1\ell+1 agents in the visible level-zero fibers, so a nonleader node is visible. Thus the test succeeds exactly when n=ℓn=\ell, and all agents then halt at round nn.

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 S⊊VS \subsetneq V contain every leader. Suppose that, for each 1≤r≤h1 \le r \le h, every node in Hr−1\mathcal{H}_{r-1} whose fiber is contained in SS has no outgoing arc from that fiber to V∖SV \setminus S in round rr. Then h≤∣S∣−ℓh \le|S|-\ell.

Proof. Count the nonleader fibers contained in SS. There are none at level zero, because the sole nonleader fiber contains V∖SV \setminus S. Every child fiber of a counted fiber is still contained in SS, so this count cannot decrease.

In round rr, let TT be the union of the fibers at level r−1r-1 contained in SS. It contains every leader and is a nonempty proper subset of VV. Strong connectivity gives an arc from an agent a∈Ta \in T to an agent b∉Tb \notin T. The hypothesis forces b∈S∖Tb \in S \setminus T. Let A⊆TA \subseteq T be the old fiber containing aa. The agent bb receives an arc from AA, whereas no agent outside SS does. The definition of indistinguishability therefore places bb’s new fiber wholly inside SS, although its old fiber was not contained in SS. 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 TT.

The count increases by at least one per round and is at most ∣S∣−ℓ|S|-\ell, proving the bound.

Case ℓ>1\ell> 1. Assume that the all-leader test has failed and ℓ≥2\ell\ge2. At round 2m−22m-2, test candidate m>ℓm>\ell by Steps 1–5 of Section 3.1, with final level Lm−1\mathcal{L}_{m-1}. Thus Step 1 requires children only through Lm−2\mathcal{L}_{m-2}, Step 2 chooses 1≤h≤m−11 \le h \le m-1, and Step 5 counts descendants in Lm−1\mathcal{L}_{m-1}, including the node itself when h=m−1h=m-1. The bound on nodes per level and the total candidate anonymity remain mm. The credit lemmas apply unchanged, since the test checks the same refinement and flow equations up to the anchor.

Lemma 7. For ℓ≥2\ell\ge2, this test rejects every candidate ℓ<m<n\ell< m < n and accepts m=n>ℓm=n>\ell at round 2n−22n-2.

Proof. Suppose m<nm<n passes with anchor Lh\mathcal{L}_h. The proof of Theorem 1 gives

m−1−h≥Φh≥∣Lm−1∣−∣Lh∣≥m−1−h.(9)m-1-h \ge\Phi_h \ge|\mathcal{L}_{m-1}|-|\mathcal{L}_h| \ge m-1-h. \tag*{(9)}

Every inequality is tight. For each anchor node vv, let q(v)q(v) count its descendants in Lm−1\mathcal{L}_{m-1}. Disjoint refinement and Step 5 give a(v),b(v)≥q(v)a(v), b(v) \ge q(v). Equality in (3) gives c(v)=q(v)−1c(v) = q(v) - 1, so a(v)=q(v)a(v) = q(v). Its q(v)q(v) descendants have disjoint nonempty fibers contained in A(v)A(v); they must therefore have singleton fibers whose union is A(v)A(v). By Lemma 5 and the total candidate anonymity,

m≤∣Lm−1∣=∑v∈Lhq(v)≤∑v∈Lhb(v)=m.m \leq\lvert\mathcal{L}_{m-1}\rvert= \sum_{v\in\mathcal{L}_h} q(v) \leq\sum_{v\in\mathcal{L}_h} b(v) = m.

Thus a(v)=b(v)=q(v)a(v) = b(v) = q(v) at the anchor. Its fibers form a set SS of exactly mm agents, also represented by the singleton fibers at level m−1m - 1. The leader equation shows that SS contains all ℓ\ell leaders.

If h<m−1h < m - 1, the union of visible fibers is SS at level h+1h + 1 as well: it lies between the identical unions at levels hh and m−1m - 1. Strong connectivity gives an arc from V∖SV \setminus S into SS in round h+1h + 1, making a predecessor outside SS visible at level hh, a contradiction. Hence h=m−1h = m - 1.

Every earlier node whose fiber meets SS is visible, because each agent of SS has a visible descendant at level m−1m - 1. Backward propagation from these singleton fibers gives b(v)=∣A(v)∩S∣b(v) = \lvert A(v) \cap S\rvert for every v∈Lrv \in\mathcal{L}_r, 0≤r≤m−10 \leq r \leq m - 1. Fix 1≤r≤m−11 \leq r \leq m - 1 and u∈Hr−1u \in\mathcal{H}_{r-1} whose fiber A=A(u)A = A(u) is contained in SS. The node uu and all its children are visible, so the checked flow equation gives

∣Er(A,V)∣=∑v child of uin Lrdr(v)b(v)=∑v∈Lrμr(u,v)b(v)=∣Er(A,S)∣.\lvert E_r(A,V)\rvert= \sum_{\substack{v\ \text{child of }u\\ \text{in }\mathcal{L}_r}} d_r(v)b(v) = \sum_{v\in\mathcal{L}_r} \mu_r(u,v)b(v) = \lvert E_r(A,S)\rvert.

Thus every old fiber contained in SS sends only to SS in each of the first m−1m - 1 rounds. Lemma 6 now gives m−1≤∣S∣−ℓ=m−ℓm - 1 \leq\lvert S\rvert- \ell= m - \ell, contradicting ℓ≥2\ell\geq2.

Finally, when m=n>ℓm = n > \ell, H4 makes the prefix ending at Ln−1\mathcal{L}_{n-1} full at round 2n−22n - 2. Level L0\mathcal{L}_0 has one leader node and one nonleader node. If the next n−1n - 1 levels were all nonflat, the last would have at least n+1n + 1 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 ℓ=1\ell= 1 or ℓ≥2\ell\geq2, testing m=ℓ+1,ℓ+2,…m = \ell+ 1, \ell+ 2, \ldots. 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 nn 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 mm passing Steps 1–4, the visible level-zero leader nodes together have credit at most ℓ−1\ell- 1: their fibers contain at most ℓ\ell agents, and each node contributes at most its anonymity minus one. Nonleader nodes contribute at most the remaining candidate anonymity m−ℓm - \ell, so Φ0≤m−1\Phi_0 \leq m - 1. The rest of the correctness proof of Theorem 1 applies unchanged. Thus nn is accepted at round 2n−12n - 1, 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 ℓ\ell of leaders. Equal round-tt vistas therefore give equal states after tt rounds, so the two leaders make the same terminal decision. They cannot both terminate correctly by that round.

Case n=ℓn = \ell. Let the smaller network be the static bidirected path x0,x1,…,xn−1x_0, x_1, \ldots, x_{n-1}, with every agent a leader. The larger network is the static bidirected path x0,x1,…,xn−1,yx_0, x_1, \ldots, x_{n-1}, y, where the xix_i’s are leaders and yy is a nonleader. Both networks have ℓ=n\ell= n leaders. Observe x0x_0 in both networks.

The states of the two copies of xix_i agree through every round tt with i+t≤n−1i + t \le n - 1. This follows by induction on tt. 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 xn−1x_{n-1} is learned only after the first communication round. Taking i=0i = 0 shows that the two endpoint leaders have the same vista through round n−1n - 1. Therefore the smaller network cannot terminate before round nn. This also covers n=1n = 1, when the initial vistas are identical.

Case ℓ=1\ell= 1. For m≥2m \ge2, let PmoP_m^o be the static bidirected path x0,x1,…,xm−1x_0, x_1, \ldots, x_{m-1}. Its unique leader is x0x_0, and xm−1x_{m-1} has one self-loop. Run the vista-construction algorithm on PmoP_m^o and Pm+1oP_{m+1}^o. At round tt, all agents farther than tt 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 m−1m - 1: 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 mm, then needs another m−1m - 1 rounds to reach the leader. Thus the leader vistas agree through round 2m−22m - 2, and termination requires 2m−12m - 1 rounds. This construction and bound already appear in [13].

Case ℓ>1\ell> 1. We first describe a strongly connected graph in which every agent except one receives information from a single sender.

Lemma 8. Let U,WU, W be disjoint nonempty sets of agents, with ∣U∣=ℓ|U| = \ell. Choose z∈Uz \in U, z′∈Wz' \in W, and c∈{1,ℓ}c \in\{1,\ell\}. An arrow X→dYX \xrightarrow{d} Y denotes dd arcs from each agent of XX to each agent of YY; an agent may replace a singleton set. The graph on U∪WU \cup W consisting of exactly the arcs

z→cW,z′→1U,U∖{z}→ℓ/cz,W∖{z′}→ℓzz \xrightarrow{c} W,\qquad z' \xrightarrow{1} U,\qquad U \setminus\{z\} \xrightarrow{\ell/c} z,\qquad W \setminus\{z'\} \xrightarrow{\ell} z

is loopless and strongly connected. Each agent of U∖{z}U \setminus\{z\} receives only z′z'’s old vista and has outdegree ℓ/c\ell/c; each agent of WW receives cc copies of zz’s old vista and has outdegree ℓ\ell.

Proof. Every agent other than zz reaches zz directly. Conversely, zz reaches WW directly and UU through z′z', proving strong connectivity. The sets are disjoint and the return bundles exclude zz 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 n>ℓ≥2n > \ell\ge2, there are dynamic networks of orders nn and n+ℓ−1n + \ell- 1, each with exactly ℓ\ell leaders, whose designated leaders have identical vistas through round 2n−32n - 3. Every round graph is a strongly connected loopless directed multigraph, with arc multiplicities at most ℓ\ell and outdegrees at most ℓ2\ell^2.

Proof. We first describe two phases for n=ℓ+1n = \ell+ 1, using networks with ℓ+1\ell+ 1 and 2ℓ2\ell agents. We call these networks the cores: for larger nn, we add nonleaders to each and adjust the communication arcs. The smaller core has leaders x1,…,xℓ=xx_1,\ldots,x_\ell=x and one nonleader yy; the larger has leaders x1′,…,xℓ′=x′x'_1,\ldots,x'_\ell=x' and nonleaders y1′,…,yℓ′=y′y'_1,\ldots,y'_\ell=y'. We compare the vistas of x,x′x,x'. 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, U,WU,W partition the core and remain fixed throughout the phase, even after an agent has been selected as a center.

First phase: ℓ−1\ell-1 rounds. Keep the smaller core a unit bidirected star centered at yy. In round tt of this phase, the larger core uses the graph of Lemma 8 with UU its leaders, z=xt′z=x'_t, z′=y′z'=y', and c=ℓc=\ell. After round tt, all smaller leaders and xt+1′,…,xℓ′x'_{t+1},\ldots,x'_\ell share one vista, while y,y1′,…,yℓ′y,y'_1,\ldots,y'_\ell 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 ℓ\ell copies of a matching leader vista and have outdegree ℓ\ell. In the smaller star these copies come from different leaders; in the larger graph they come from parallel arcs of xt′x'_t. This proves the assertion by induction from the initial leader and nonleader classes. We no longer compare xt′x'_t after its round.

Second phase: ℓ−1\ell-1 rounds. Apply Lemma 8 with c=1c=1 on both sides. In round tt of this phase, the smaller core has UU its leaders, z=xtz=x_t, and z′=yz'=y; the larger core has UU its nonleaders, z=yt′z=y'_t, and z′=x′z'=x'. After round tt, xt+1,…,xℓ,x′x_{t+1},\ldots,x_\ell,x' share one vista, while y,yt+1′,…,yℓ′y,y'_{t+1},\ldots,y'_\ell 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 ℓ\ell. 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, x,x′x,x' match and y,y′y,y' match.

Adding g=n−ℓ−1g=n-\ell-1 nonleaders. Add z1,…,zgz_1,\ldots,z_g to the smaller core and z1′,…,zg′z'_1,\ldots,z'_g to the larger one. We call these added nonleaders relays, and each pair (zi,zi′)(z_i,z'_i), for 1≤i≤g1\le i\le g, a relay pair. We describe the initial delay, the changes to the two phases, and the final delay. For g=0g=0, omit the initial delay and leave the two phases unchanged.

For g>0g>0, begin with gg repetitions of one fixed graph on each side. Put the nonleaders on the directed cycles

z1→⋯→zg→y→z1,z1′→⋯→zg′→y1′→⋯→yℓ′→z1′z_1\to\cdots\to z_g\to y\to z_1,\qquad z'_1\to\cdots\to z'_g\to y'_1\to\cdots\to y'_\ell\to z'_1

and join every leader bidirectionally to z1z_1, respectively z1′z'_1. 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 t≤gt\le g, all original nonleaders and all zj,zj′z_j,z'_j with j>tj>t share one vista, all leaders share one vista, and every pair zj,zj′z_j,z'_j is matched. To see this, z1,z1′z_1,z'_1 receive the same leader vistas and one matching cycle-predecessor vista, with outdegree ℓ+1\ell+1. Every other nonleader has outdegree one and receives its predecessor’s vista. The distinction first created at z1,z1′z_1,z'_1 thus advances one position per round, reaching no original nonleader before round g+1g+1. The leaders receive the matching vistas of z1,z1′z_1,z'_1 and have outdegree one. This proves all three assertions by induction.

In each round of the two (ℓ−1)(\ell-1)-round phases, let y∗y_* be the nonleader with one outgoing arc to each leader: yy in the smaller network, y′y' in the larger network’s first phase, and yt′y'_t in round tt of its second phase. For g>0g>0, replace these arcs by

y∗→ℓz1→ℓ⋯→ℓzg→1{all leaders},y_* \xrightarrow{\ell} z_1 \xrightarrow{\ell} \cdots\xrightarrow{\ell} z_g \xrightarrow{1} \{\text{all leaders}\},

using z1′,…,zg′z'_1,\ldots,z'_g instead of z1,…,zgz_1,\ldots,z_g in the larger network. All other core arcs remain unchanged. Every original outdegree is preserved, and every relay has outdegree ℓ\ell. 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 y∗y_* have matching old vistas, even when the larger one is the newly selected yt′y'_t. Thus corresponding relays receive ℓ\ell copies of matching predecessor vistas and remain matched. Each compared leader receives the last relay’s matching vista instead of y∗y_*’s vista; the compared original nonleaders have unchanged incoming arcs and outdegrees. The two phase invariants therefore still hold. At their end, x,x′,y,y′x,x',y,y', and every relay pair match.

Final cycle. On the smaller and larger sides, respectively, use the directed cycles

x→x1→⋯→xℓ−1→y→z1→⋯→zg→x,x \to x_1 \to\cdots\to x_{\ell-1} \to y \to z_1 \to\cdots\to z_g \to x,
x′→x1′→⋯→xℓ−1′→y1′→⋯→yℓ−1′→y′→z1′→⋯→zg′→x′.x' \to x'_1 \to\cdots\to x'_{\ell-1} \to y'_1 \to\cdots\to y'_{\ell-1} \to y' \to z'_1 \to\cdots\to z'_g \to x'.

For g=0g=0, y,y′y,y' send directly to the observers. Repeat these graphs forever. Every agent has indegree and outdegree one. Initially the consecutive agents y,z1,…,zg,xy,z_1,\ldots,z_g,x match their counterparts, so a difference can advance toward the observers by only one position per round. Their vistas remain identical for g+1g+1 final rounds.

In fact, y,y′y,y' first differ in the first final round: their predecessors are xℓ−1x_{\ell-1} and yℓ−1′y'_{\ell-1}, whose initial leader statuses differ. This difference reaches the observers in final round g+2g+2. The common interval therefore has exactly

g+(ℓ−1)+(ℓ−1)+(g+1)=2n−3g+(\ell-1)+(\ell-1)+(g+1)=2n-3

rounds. In particular, the core g=0g=0 has one common final-cycle round; the next repetition shows the first difference.

All graphs are loopless. During the two (ℓ−1)(\ell-1)-round phases, arc multiplicities are at most ℓ\ell, and a selected center sends at most ℓ\ell arcs to each of at most ℓ\ell agents, giving outdegree at most ℓ2\ell^2. All other middle agents have outdegree at most ℓ\ell. The initial maximum outdegree is ℓ+1≤ℓ2\ell+1\le\ell^2, and the final outdegree is one. This proves the stated structural bounds. □\square

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 V\mathcal{V} lists its levels L0,…,Lt\mathcal{L}_0,\ldots,\mathcal{L}_t, with one bottom node in Lt\mathcal{L}_t. The root at level −1-1 is implicit. Each node at level zero has its leader or nonleader status. For every 1≤r≤t1 \le r \le t, the encoding gives the parent and outdegree label of each v∈Lrv \in\mathcal{L}_r, and all positive multiplicities μr(u,v)\mu_r(u,v) with u∈Lr−1u \in\mathcal{L}_{r-1}. Unlisted multiplicities are zero; all numerical labels are encoded in binary. The positive leader count ℓ\ell is also part of the input.

The encoding must have at most one node of each status at level zero, distinct signatures (dr(v),(μr(u,v))u)(d_r(v),(\mu_r(u,v))_u) 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 ℓ\ell, whose round-tt vista at some agent is isomorphic to V\mathcal{V}. We use the isomorphisms defined in Section 2. Its order is the number of agents. Define the order spectrum

Spec⁡ℓ(V)={N≥ℓ:V has a realization of order N}.\operatorname{Spec}_{\ell}(\mathcal{V})=\{N \ge\ell:\mathcal{V}\text{ has a realization of order }N\}.

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 nn.

Small Realizations

Use the causal support Γ0,…,Γt\Gamma_0,\ldots,\Gamma_t from Section B. In particular, Γ0\Gamma_0 is the set of agents that have influenced the observer by round tt. This concerns individual agents, not whether a vista level is full: a visible node may have agents in its fiber outside Γ0\Gamma_0.

Let ss be the binary length of ⟨V,ℓ⟩\langle\mathcal{V},\ell\rangle, let ν=∑r=0t∣Lr∣\nu=\sum_{r=0}^{t}|\mathcal{L}_r|, and let MM be the largest of ℓ\ell, the outdegree labels, and the red multiplicities in V\mathcal{V}. Put K=(1+νM)tK=(1+\nu M)^t.

Lemma 9. If V\mathcal{V} admits two different compatible orders, two can be chosen at most K+ℓ+2K+\ell+2, with polynomial bit length in ss.

Proof. An agent represented by a node of V\mathcal{V} at level r≥1r \ge1 constructs its vista from its own previous state, the states received in round rr, and its outdegree label. Its node has at most ν\nu red predecessors, each of multiplicity at most MM. Unfolding the previous and received states backward for tt rounds therefore gives ∣Γ0∣≤(1+νM)t=K|\Gamma_0| \le(1+\nu M)^t=K. If two different compatible orders have realizations with Γ0=V\Gamma_0=\mathcal{V}, both orders are at most KK.

Otherwise, take a realization with Γ0≠V\Gamma_0\ne\mathcal{V}. Retain all agents in Γ0\Gamma_0 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 Γr\Gamma_r in round rr, since such a sender would belong to Γr−1⊆Γ0\Gamma_{r-1}\subseteq\Gamma_0. Thus all states needed for V\mathcal{V} remain unchanged. The resulting realization has at most K+ℓ+1K+\ell+1 agents and still has an agent outside the causal support. Loops created by contraction are allowed.

Now add one nonleader. In each round rr, strong connectivity gives an arc from the nonempty proper set Γr\Gamma_r 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 Γr\Gamma_r. Induction through the rounds preserves every state needed for V\mathcal{V}, and the new agent remains outside the causal support. We have obtained two different compatible orders, both at most K+ℓ+2K+\ell+2.

Finally, tt, ν\nu, and log⁡M\log M are bounded by ss, so K+ℓ+2K+\ell+2 has polynomial bit length in ss.

Corollary 1. Let V\mathcal{V} be a vista with ℓ\ell leaders. If it has a realization of order NN whose observer has a proper initial causal support Γ0≠V\Gamma_0 \ne\mathcal{V}, then

{N,N+1,N+2,…}⊆Spec⁡ℓ(V).\{N,N+1,N+2,\ldots\} \subseteq\operatorname{Spec}_{\ell}(\mathcal{V}).

Moreover, with K=(1+νM)tK=(1+\nu M)^t as above, either all compatible orders are at most KK, or there is an integer N∗≤K+ℓ+1N_* \le K+\ell+1 such that

{N∗,N∗+1,N∗+2,…}⊆Spec⁡ℓ(V).\{N_*,N_*+1,N_*+2,\ldots\} \subseteq\operatorname{Spec}_{\ell}(\mathcal{V}).

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 NN is compatible.

If no realization has a proper initial causal support, every compatible order is at most KK. Otherwise, the contraction construction in the same proof gives a realization of order N∗≤K+ℓ+1N_* \le K+\ell+1 with proper initial causal support. The first assertion then makes every order at least N∗N_* 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 DD be a directed multigraph on V∪{z}V \cup\{z\}, with V≠∅V \ne\varnothing. Suppose every ordered pair of vertices in VV is joined by a directed path, zz has no loop, and d−(z)=d+(z)d^{-}(z)=d^{+}(z). The arcs at zz can be paired so that replacing each pair a→z→ba \to z \to b by a→ba \to b leaves a strongly connected graph on VV.

Proof. Pair the arcs arbitrarily and call the resulting graph GG. If it is not strongly connected, choose distinct strongly connected components AA, BB, with no arc entering AA and no arc leaving BB. Reachability in DD forces an arc from zz into AA. Its paired shortcut a→ba \to b lies wholly in AA, since no arc of GG enters AA. Similarly, an arc from BB to zz gives a paired shortcut c→dc \to d wholly in BB.

Switch these pairings, replacing the shortcuts by a→da \to d and c→bc \to b. Simple paths b⇝ab \leadsto a within AA and d⇝cd \leadsto c within BB avoid the removed shortcuts. The removed arcs therefore have replacement paths

a→d⇝c→b,c→b⇝a→d.a \to d \leadsto c \to b,\qquad c \to b \leadsto a \to d.

No old reachability is lost, and AA, BB merge. Repeat until only one component remains. A shortcut that is a loop uses an empty internal path in this argument.

Lemma 11. Let Tr−1,Tr\mathcal{T}_{r-1},\mathcal{T}_r be the old and new node sets of a proposed full history-tree prefix, with parent map π:Tr→Tr−1\pi:\mathcal{T}_r \to\mathcal{T}_{r-1}. New node vv has anonymity a(v)≥1a(v) \ge1 and outdegree d(v)d(v). Each agent in its fiber must receive μ(u,v)\mu(u,v) arcs from the fiber of old node uu. Assume the flow equations

∑v:π(v)=ua(v)d(v)=∑w∈Tra(w)μ(u,w)(u∈Tr−1).(10)\sum_{v:\pi(v)=u} a(v)d(v)=\sum_{w\in\mathcal{T}_r} a(w)\mu(u,w)\qquad(u\in\mathcal{T}_{r-1}). \tag*{(10)}

Put N=∑va(v)N=\sum_v a(v). For N>1N>1, these data have a strongly connected round realization exactly when every new node has positive outdegree and positive incoming degree, and the digraph on Tr\mathcal{T}_r with arcs v→wv \to w whenever d(v)>0d(v)>0 and μ(π(v),w)>0\mu(\pi(v),w)>0 is strongly connected. For N=1N=1, balance alone suffices.

Proof. Necessity follows by projecting physical paths onto their nodes. For sufficiency, create the NN agents and an auxiliary vertex zuz_u for each old node uu with positive flow total. An agent in the fiber of vv has d(v)d(v) arcs to zπ(v)z_{\pi(v)}; vertex zuz_u has μ(u,w)\mu(u,w) arcs to each agent in the fiber of ww. 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 N=1N=1, 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 V\mathcal{V} can be replaced by one of the same order whose full history-tree prefix through level tt 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 V\mathcal{V} has a realization of order NN, it has one of the same order and leader count whose full levels T0,…,Tt\mathcal{T}_0,\ldots,\mathcal{T}_t satisfy

∣Tr∣≤∑j=0r∣Cj∣+r+2.|\mathcal{T}_r| \le\sum_{j=0}^{r}|\mathcal{C}_j|+r+2.

Its anonymities, outdegrees, and multiplicities have O(s+log⁡N)O(s+\log N) bits. The entire full-prefix description has length polynomial in s+log⁡Ns+\log N.

Proof. Fix a realization of V\mathcal{V}. 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 r−1r-1 has been constructed. Within each block CC, retain each original visible fiber at level rr as a separate block, and put all remaining agents of CC into one block HCH_C, omitting it if empty. A hidden block at level r−1r-1 contains no visible fiber at level rr, since every visible node has a visible parent. If there are no hidden agents at level rr, keep the original round graph: all blocks at level r−1r-1 are then unchanged visible fibers.

Otherwise, strong connectivity gives an original round-rr arc from an agent qq outside the visible fibers at level rr to an agent inside them. The original node at level r−1r-1 whose fiber contains qq is therefore visible. Since visible fibers are preserved, this fiber is also a block PP of the new partition at level r−1r-1. Split HPH_P into {q}\{q\} and HP∖{q}H_P\setminus\{q\}, 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 qq. For a source with visible new node vv, these retained arcs are a subset of its original outgoing arcs. Add arcs to qq until its outdegree again equals the displayed value dr(v)d_r(v). Choose DD larger than all currently retained degrees and all displayed new degrees. Give every hidden agent other than qq outdegree DD, by adding arcs to qq. Add one arc from qq to each other hidden agent, then pad qq’s outdegree with loops to a value Dq>DD_q>D exceeding its current degree. Every block HCH_C other than {q}\{q\} now has one uniform signature: its agents have degree DD, receive one state from old block PP, and receive nothing else. These degrees distinguish hidden children from visible siblings and distinguish qq 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 qq has an arc to qq and one from qq. To reach qq from a visible agent, follow an original path until its first hidden target; that arc was redirected to qq. To reach a visible agent from qq, take an original path and its last hidden vertex zz. The remaining visible suffix was retained; if z≠qz \ne q, prepend the added arc q→zq \to z. 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 ∣Lr∣\lvert\mathcal{L}_r\rvert visible blocks, one hidden block per old block, and the extra singleton qq. Starting with at most two blocks gives the claimed node bound. For bit lengths, all retained arcs to visible targets total at most NνMN\nu M per source, and at most NN distinct hidden-target arcs per source are retained. Choose D,DqD,D_q by adding one to the required maxima. All new degrees and incoming multiplicities are polynomially bounded in N,ν,MN,\nu,M, and hence have O(s+log⁡N)O(s+\log N) bits. Since every vista level is nonempty, t+1≤νt+1\le\nu; the tables have O(ν2)O(\nu^2) nodes and O(ν3)O(\nu^3) multiplicity entries.

Lemma 13. Whether N∈Spec⁡ℓ(V)N \in\operatorname{Spec}_{\ell}(\mathcal{V}) is in NP, with certificate length polynomial in s+log⁡Ns+\log N.

Proof. Guess the full-prefix tables of Lemma 12, a node bb at level tt to serve as the vista’s bottom node, and an identification of the input vista with the backward closure of bb. Check positive integer anonymities, total anonymity NN at each level, and exactly ℓ\ell 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 bb onto the input vista.

All checks take time polynomial in the binary table length. Disjoint refinement allows us to partition the same set of NN 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 V\mathcal{V}. 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 K+ℓ+2K+\ell+2, with polynomial bit length in ss. 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 tt, with binary arc multiplicities. The problem SomeAgentKnows asks whether at least one round-tt vista determines the network size.

Theorem 6. SomeAgentKnows belongs to coNP.

Proof. Construct all round-tt vistas by computing the successive partitions and history-tree labels. This takes polynomial time in the explicitly listed network prefix. Its order nn is compatible with every one of these vistas.

If no agent’s vista determines nn, 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 nn. 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 U={0,…,3q−1}U = \{0,\ldots,3q-1\}, and let S1,…,SmS_1,\ldots,S_m be distinct three-element subsets of UU. We may assume q≥2q \ge2: duplicate triples can be deleted, and adding three fresh elements with their unique triple increases qq by one without changing whether an exact cover exists.

Set

B=q+3,K=B3q,W=∑e=03q−1Be,A=qK+W.B = q+3,\qquad K = B^{3q},\qquad W = \sum_{e=0}^{3q-1} B^e,\qquad A = qK+W.

and define

c0=A,cj=K+∑e∈SjBe(1≤j≤m).c_0 = A,\qquad c_j = K+\sum_{e\in S_j} B^e\quad(1\le j\le m).

We have 0<W<K0<W<K, all ci>Kc_i>K, and A<(q+1)KA<(q+1)K. The cic_i are distinct: the triples have distinct base-BB digit vectors, and

cj<2K≤qK<A=c0(j≥1).c_j<2K\le qK<A=c_0\qquad(j\ge1).

Lemma 14. For nonnegative integers x0,…,xmx_0,\ldots,x_m, the equation

Ax0+∑j=1mcjxj=A(11)Ax_0+\sum_{j=1}^{m}c_jx_j=A \tag*{(11)}

has the reference solution x0=1x_0=1, x1=⋯=xm=0x_1=\cdots=x_m=0. Every other solution has x0=0x_0=0, and its nonzero coordinates xjx_j select an exact cover. Conversely, every exact cover gives such a solution. In every solution, ∑i=0mxi≤q\sum_{i=0}^{m}x_i\le q.

Proof. Since every coefficient is at least KK and A<(q+1)KA < (q + 1)K, the sum of the coordinates is at most qq. Equation (5) gives x0≤1x_0 \le1; if x0=1x_0 = 1, positivity of the other coefficients gives the reference solution.

If x0=0x_0 = 0, write

k=∑j=1mxj,de=∑j:e∈Sjxj.k = \sum_{j=1}^{m} x_j,\qquad d_e = \sum_{j:e\in S_j} x_j.

Then

kK+∑e=03q−1deBe=qK+∑e=03q−1Be.kK + \sum_{e=0}^{3q-1} d_e B^e = qK + \sum_{e=0}^{3q-1} B^e.

Here $0 \le d_e \le k \le q < B$, so no carries occur in base BB. The digit at position $3q$ gives k=qk = q, and the remaining digits give de=1d_e = 1 for every ee. Each xjx_j 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 λ\lambda and groups 0,…,m0,\ldots,m of nonleaders. Write

R=1+(m+1)B,N0=R+1,C=B∑i=0mci+A.R = 1 + (m + 1)B,\qquad N_0 = R + 1,\qquad C = B\sum_{i=0}^{m} c_i + A.

The reference group sizes are

a00=B+1,aj0=B(1≤j≤m).a_0^0 = B + 1,\qquad a_j^0 = B\quad(1 \le j \le m).

Thus the reference network has N0N_0 agents and ∑iciai0=C\sum_i c_i a_i^0 = C.

More generally, for group sizes ai≥Ba_i \ge B with ∑iciai=C\sum_i c_i a_i = C, list group ii as xi,1,…,xi,aix_{i,1},\ldots,x_{i,a_i}. The path graph has the arcs

xi,1→xi,2→⋯→xi,ai→λ,x_{i,1} \to x_{i,2} \to\cdots\to x_{i,a_i} \to\lambda,

one copy of each, together with cic_i parallel arcs λ→xi,k\lambda\to x_{i,k} for every group member. Use this same graph for rounds 1,…,B−11,\ldots,B-1. Every nonleader has outdegree one, and the leader has outdegree CC. 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 BB 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 G0G^0 be this BB-round reference prefix, and let V\mathcal{V} be its final leader vista. These are the outputs for the network and vista reductions, respectively.

Lemma 15. For any sizes ai≥Ba_i \ge B with ∑iciai=C\sum_i c_i a_i = C, the labeled history-tree prefix through round B−1B - 1, without fiber cardinalities, is the same. After round rr, for 1≤r≤B−11 \le r \le B - 1, group ii has the rr singleton classes

{xi,1},…,{xi,r}\{x_{i,1}\},\ldots,\{x_{i,r}\}

and the single nonempty suffix class {xi,r+1,…,xi,ai}\{x_{i,r+1},\ldots,x_{i,a_i}\}. All groups have distinct histories.

Proof. In round one, the first path member receives only cic_i leader states; every other member also receives one nonleader state. The leader receives m+1m + 1 copies of the initial nonleader state. Its outdegree is CC. Hence all these records are independent of the group sizes, and the distinct cic_i distinguish the groups. Inductively, previously distinct classes cannot merge, since the previous history is retained. At round r+1r+1, the first member of the old suffix receives the previous state of the singleton at position rr, while every remaining suffix member receives the old suffix state. This separates one further position. Every member still receives cic_i 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 CC. These records are independent of the lengths. This proves both the partition and the equality of its labels.

In particular, at level B−1B-1 there are exactly BB nonleader nodes per group and one leader node, for a total of RR nodes. The reference network’s ordinary star makes every one of those nodes visible in V\mathcal{V}: 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 O((m+1)q)O((m+1)q) agents and O(q)O(q) rounds, with O((m+1)q2)O((m+1)q^2) nonzero arc entries over all round graphs. The numbers cic_i have O(qlog⁡(q+3))O(q\log(q+3)) bits, and CC has O(qlog⁡(q+3)+log⁡(m+1))O(q\log(q+3)+\log(m+1)) bits. The vista has O((m+1)q2)O((m+1)q^2) 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 V\mathcal{V}, on any agent set VV. 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 1≤r≤B−11 \le r \le B-1, let Sr⊆VS_r \subseteq V be the union of the fibers of the nodes visible at level rr of V\mathcal{V}. Parents are visible, so Sr+1⊆SrS_{r+1} \subseteq S_r. The unique leader belongs to every SrS_r.

At level one, each group is represented by two nodes, its first-position node and its suffix node. Let aia_i be the sum of the cardinalities of these two fibers in the arbitrary realization. Their visible descendants at level B−1B-1 include BB disjoint nonempty fibers. Therefore

ai≥B.a_i \ge B.

Both first-level nodes of group ii prescribe cic_i incoming copies of the unique initial leader state. The visible leader’s first-round outdegree is CC, so

∑i=0mciai≤C.\sum_{i=0}^{m} c_i a_i \le C.

This is only an inequality until we prove that level one is full. Writing xi=ai−B≥0x_i=a_i-B\ge0 gives

∑i=0mcixi≤A,∑i=0mxi≤q,\sum_{i=0}^{m} c_i x_i \le A,\qquad\sum_{i=0}^{m} x_i \le q,

where the second bound again uses ci≥Kc_i \ge K and A<(q+1)KA < (q+1)K. Hence

∣S1∣≤R+q,∣SB−1∣≥R.(12)|S_1| \le R+q,\qquad|S_{B-1}| \ge R. \tag*{(12)}

Lemma 16. In every realization of V\mathcal{V}, S1=VS_1=V.

Proof. Suppose S1S_1 is proper. Every Sr⊆S1S_r \subseteq S_1 is then proper and nonempty. If Sr+1=SrS_{r+1}=S_r, strong connectivity of round r+1r+1 gives an arc from V∖SrV\setminus S_r into this set. Its head lies in a visible level-(r+1)(r+1) fiber, so its tail’s level-rr history must be a visible incoming predecessor. The tail would belong to SrS_r, a contradiction. Thus every inclusion Sr+1⊆SrS_{r+1}\subseteq S_r is strict.

There are B−2=q+1B-2=q+1 such transitions between levels 1 and B−1B-1. Consequently (12) gives

R≤∣SB−1∣≤∣S1∣−(q+1)≤(R+q)−(q+1)=R−1,R \leq|S_{B-1}| \leq|S_1|-(q+1) \leq(R+q)-(q+1)=R-1,

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

∑i=0mciai=C,equivalentlyAx0+∑j=1mcjxj=A.\sum_{i=0}^{m} c_i a_i=C,\qquad\text{equivalently}\qquad Ax_0+\sum_{j=1}^{m}c_jx_j=A.

Lemma 14 applies. If there is no exact cover, it forces x0=1x_0=1 and all other coordinates zero, so every realization has order N0=R+1N_0=R+1. If any other solution occurs, the source instance has an exact cover, and its order is R+qR+q.

Combining this converse with the constructions below will give

Spec⁡1(V)={{N0},if the instance has no exact cover,{N0,N0+q−1},if the instance has an exact cover.\operatorname{Spec}_1(\mathcal{V})= \begin{cases} \{N_0\}, & \text{if the instance has no exact cover},\\ \{N_0,N_0+q-1\}, & \text{if the instance has an exact cover}. \end{cases}

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 J⊆{1,…,m}J\subseteq\{1,\ldots,m\}, with ∣J∣=q|J|=q. Define alternative group sizes by

a0′=B,aj′=B+1{j∈J}(j≥1).a'_0=B,\qquad a'_j=B+1_{\{j\in J\}}\quad(j\geq1).

Their order is

N1=R+q=N0+q−1≠N0.N_1=R+q=N_0+q-1\ne N_0.

Moreover,

∑iciai′=B∑ici+∑j∈Jcj=B∑ici+A=C.\sum_i c_i a'_i=B\sum_i c_i+\sum_{j\in J}c_j=B\sum_i c_i+A=C.

By Lemma 15, these sizes realize exactly the same labeled path prefix through round B−1B-1. 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 cic_i 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 CC also agree. Thus its final vista is VV.

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 cic_i 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 VV. It always has the reference realization of order N0N_0. If the source instance has no exact cover, Lemma 16 and the exact integer equation show that every realization has order N0N_0. If it has an exact cover, the adjusted alternative final round above gives a realization of order N1≠N0N_1 \ne N_0. 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 G0\mathcal{G}^{0}, with its ordinary-star final round. If the source instance has no exact cover, the leader has only the compatible order N0N_0, so the output is a yes-instance.

If an exact cover exists, the adjusted alternative final round gives the reference leader a compatible order N1N_1, while the ordinary-star alternative gives every reference nonleader the same compatible order N1N_1. Since all their vistas are also realized by the reference order N0≠N1N_0 \ne N_1, 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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [14]Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979.
  15. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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

Paper details

vlnc:W_sj5vv63e
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

GPT-6 Astra (bare)

View statement
Looking for related papers…
Contents