arXiv CSopen access

Computing in Anonymous Dynamic Networks with One-Bit Communications

Computing in Anonymous Dynamic Networks with One-Bit Communications Thibaut Blanc, Giuseppe Antonio Di Luna, and Giovanni Viglietta

arXiv:2607.08358v1 [cs.DC] 9 Jul 2026

Abstract We initiate the study of deterministic computation in anonymous dynamic networks in which each agent broadcasts a single bit per round and receives only the number of neighbors that broadcast each bit value. Despite this minimal communication, we show that surprisingly rich global computation remains possible. When the network has a unique leader and an upper bound U on the network size n is known, we give a terminating algorithm for any desired computable function of the input multiset in O(n3 log2 n + U ) rounds, where inputs are drawn from a universe of size N = 2O(n log n) . In addition, without any prior knowledge of n, we design a stabilizing algorithm for the same task that runs in O(n3 log2 n) rounds. Notably, this essentially matches the state of the art for the congested communication model, where messages may carry O(log n) bits rather than just one, and general computation is achieved in O(n3 ) rounds. We also obtain companion results for leaderless and multi-leader networks, with comparable performance. We complement these upper bounds with an almost-matching lower bound of  2  n log(N/n) Ω log n rounds, which becomes Ω(n3 ) when N = 2Ω(n log n) . The proof is an information-theoretic argument on local histories, and the lower bound holds even when the network has a unique leader, n and N are known, and the communication graph is restricted to a ring that may change every round. Our algorithmic techniques are based on extracting global linear equations from local one-bit aggregate observations. A one-bit cut test gives a conservation constraint on the sizes of indistinguishable agent classes; by repeatedly refining these classes and collecting independent constraints, the agents recover the desired multiplicities. For the unknown-size case, we also introduce a self-correcting adaptive flooding primitive of independent interest. Together, these results show that the computational power of congested anonymous dynamic networks is essentially preserved, even when every message is compressed to a single bit.

1

Introduction

Dynamic networks are a central research topic in distributed computing. In these systems, communication links may change unpredictably over time. One of the most widely studied models is the 1-interval-connected model. In this synchronous model, a system of n agents proceeds in rounds and, in every round t, an adversary selects an arbitrary communication graph Gt subject only to the requirement that Gt be connected. 1

In this paper, we focus on anonymous dynamic networks. Agents do not have unique identifiers and execute the same deterministic algorithm. Except for their input, agents start in the same state. Anonymous networks arise naturally when identifiers are unavailable, undesirable, or incompatible with the application, for example in privacy-sensitive systems, large-scale populations of simple devices, and biological systems in which globally unique identifiers do not exist. From an algorithmic perspective, however, anonymity creates a fundamental symmetry problem: agents with identical local histories must remain in identical states. It is often customary to make the minimal symmetry-breaking assumption that the network contains a set of leader agents, namely a set of agents with a distinguished initial state whose exact size k is known. The assumption of having a unique leader is the special case in which k = 1. A symmetry-breaking assumption is generally necessary [31] for distributed algorithms computing functions that depend on the absolute scale of the system, such as Counting, which returns the exact number of agents n, and Input Multiset, which returns the multiset of initial inputs of the agents. If broadcasting messages of unbounded size is allowed, the presence of a unique leader is sufficient to reconstruct the complete multiset of inputs. More generally, every function that is deterministically computable in anonymous 1-interval-connected networks can be computed in a linear number of rounds, thanks to a data structure called a history tree [20]. A more restrictive setting is the congested model, in which each message contains at most O(log n) bits. Despite this bandwidth restriction, when a unique leader is present, arbitrary functions of the input multiset can still be computed in O(n3 ) rounds [23]. This raises a natural question: how much communication bandwidth is actually required for general computation in anonymous dynamic networks? We study a minimal transmission model: in every round, each agent emits a single bit. The chosen bit is broadcast to all of its current neighbors. An agent learns the exact number of its neighbors that sent 0 and the exact number that sent 1 in the current round.1

1.1

Contributions

We consider stabilizing and terminating algorithms. An algorithm stabilizes if, after a finite number of rounds, the outputs returned by all agents are correct and never change again; their internal states may still keep evolving. An algorithm terminates if it not only stabilizes, but every agent eventually enters a final state, which no longer changes. A quadratic lower bound. We prove that computing the Input Set, that is the set of initial inputs of agents without multiplicity, where inputs are drawn from a universe of size N ≥ 2n, requires  2  n log(N/n) Ω log n rounds. This lower bound holds even when all agents have distinct input values (which is equivalent to having unique identifiers), all agents know n and N , the network contains a unique leader, the communication graph is a ring in every round, and the algorithm is required only to stabilize. In 1 In the related beeping model, in which an agent either beeps or listens and cannot count the multiplicity of received beeps, computing the Counting function is impossible in an anonymous network with a leader. For example, consider a complete graph with a leader.

2

particular, when N = n1+ε for any constant ε > 0, the bound becomes Ω(n2 ); when N = 2n log n , the bound becomes Ω(n3 ). Note that the same lower bound holds for the Input Multiset problem, which also requires determining the number of agents that have been assigned each input value. We then prove that this lower bound is nearly optimal by designing a terminating algorithm for Input Set, whose running time matches the lower bound up to logarithmic factors, provided that a linear upper bound on n is known by the agents. Leaderless Input Frequency and Input Multiset in the multi-leader setting. One of our main algorithmic contributions is a method for converting local counts into linear equations describing the multiplicities of classes of indistinguishable agents. The algorithm repeatedly refines these classes and collects independent equations until their relative frequencies are uniquely determined. Given a common upper bound U ≥ n, the algorithm solves Input Frequency, the problem of
computing the relative frequency of each input, without a leader in O U nBmax + U n2 log n rounds, where Bmax is the maximum bit length of an input value. We remark that computing input frequencies is complete for the class of problems solvable in leaderless anonymous dynamic networks [21], and it yields an immediate solution to the well-studied average consensus problem [32]. When a known set of leaders is available, that is, when the class containing the leaders has known positive multiplicity,2 we can use the number of leaders as a fixed normalization factor for the linear system. This allows every agent to recover the multiplicity of every input value. We therefore obtain algorithms for Input Multiset and Counting with the same asymptotic round complexity. e 3 ). For U = Θ(n) and Bmax = O(log n), the resulting complexity is O(n3 log n) = O(n Thus, at the level of round complexity, restricting every sender to one-bit transmissions introduces only a logarithmic factor compared with the O(n3 )-round algorithm known for congested anonymous dynamic networks [23]. Under the mild additional assumption that, at the beginning of each round, every agent can query an oracle returning its current degree, we show how a known number of leaders can be used to compute an exponential upper bound U on the network size. Combining this bound with our known-bound procedure described above leads to a terminating, albeit exponential-time, algorithm that requires no prior global knowledge of the network. A stabilizing polynomial algorithm with a single leader and no prior knowledge. Finally, in the case of a unique leader, we remove the assumption that agents initially know a common upper bound on the network size, as well as any other a priori assumption or oracle. We introduce a technique for building a stabilizing flooding algorithm that broadcasts a message using a selfcorrecting network-size estimate. The broadcast either completes or enters a special error state that ends up modifying the estimate. Based on this primitive, we obtain a stabilizing algorithm that does not explicitly terminate but computes Input Multiset, and thus Counting, with round
complexity O n2 Bmax log n + n3 log2 n without any initial knowledge of n. If U ≥ n is given, this technique yields
a terminating algorithm for Input Multiset with complexity O n2 Bmax log n + n3 log2 n + U . Note that this algorithm achieves a slightly better running time than the one in the previous section, although it requires a unique leader. 2 This is also the case in which one distinguished input value and its multiplicity are known a priori.

3

Interestingly, if the input universe consists of the integers from 1 to N = 2n log n , then we have Bmax = n log n, and the previous upper bounds reduce to O(n3 log2 n), matching our lower bound of Ω(n3 ) up to logarithmic factors. For larger input universes, we have again almost-matching upper and lower bounds of O(n2 log N log n) and Ω(n2 log N/ log n), respectively. Table 1 summarizes the main results of this paper. Problem

Assumptions

Result

Input Set Input Multiset Input Set Input Frequency

Unique leader N ≥ 2n Known U Known U Multi-leader Known U Multi-leader Known U Multi-leader Local degree oracle Multi-leader Local degree oracle Unique leader Unique leader Unique leader Known U Unique leader Known U

Stabilization requires Ω n2 log(N/n)/ log n rounds (§ 3)

Input Multiset Counting Input Frequency Input Multiset Counting Input Multiset Counting Input Multiset Counting

Terminating algorithm in O(U n(1 + Bmax )) rounds (§ 4.2) Terminating algorithm in O(U nBmax + U n2 log n) rounds (§ 5.1) Terminating algorithm in O(U nBmax + U n2 log n) rounds (§ 5.2) Terminating algorithm in O(U n2 log n) rounds (§ 5.2) Terminating algorithm in O(nn Bmax + nn+1 log n) rounds (§ 5.3) Terminating algorithm in O(nn+1 log n) rounds (§ 5.3) Stabilizing algorithm in O(n2 Bmax log n + n3 log2 n) rounds (§ 7) Stabilizing algorithm in O(n3 log2 n) rounds (§ 7) Terminating algorithm in O(n2 Bmax log n + n3 log2 n + U ) rounds (§ 7.1) Terminating algorithm in O(n3 log2 n + U ) rounds (§ 7.1)

Table 1. Summary of the main results. Here, Bmax denotes the maximum bit length of an input value, U ≥ n denotes an upper bound on the network size, and N denotes the input universe size. For the multi-leader assumption we have a set of k ≥ 1 leaders with k known; the unique-leader assumption is the special case where k = 1.

Challenges and significance of the results. These results show that general computation in anonymous dynamic networks remains possible even when communication is reduced below the congested threshold. To the best of our knowledge, this is the first work to study deterministic global computation in anonymous dynamic networks with one-bit broadcast communication. The setting is particularly hostile because three restrictions interact: agents have no identifiers, the topology changes adversarially from round to round, and messages contain only one bit. The difficulty is not merely that messages are short. In an anonymous dynamic network, a long message cannot simply be divided into small pieces and reassembled later, because the pieces carry no persistent source information and the neighbors of an agent may change before the next piece is received. In the congested model, this obstacle can still be overcome by sending O(log n)-bit objects, such as temporary labels or edge descriptors [23]. In our model, even this is unavailable: an agent broadcasts only a bit, and its feedback is only the number of neighbors that sent each bit. Thus agents cannot transmit temporary identifiers, attach names to fragments of information, or send numerical quantities directly. This makes the comparison with history-tree algorithms especially informative. History trees were a breakthrough in the study of anonymous dynamic networks: they led to optimal linear-time computability in the non-congested model and were later adapted to obtain the O(n3 )-round state of the art for congested anonymous dynamic networks [20, 21, 23]. The congested adaptation still builds on the history-tree paradigm: it constructs and transmits compacted history-tree information using temporary non-unique identifiers and carefully controlled broadcasts. Our algorithms do 4

not construct history trees, do not exchange vistas, and do not simulate the congested historytree transmission. Nevertheless, for a linear upper bound U = Θ(n) and Bmax = O(log n), our terminating algorithms compute input multiplicities in O(n3 log n) rounds, and our unique-leader stabilizing algorithm without prior knowledge computes them in O(n3 log2 n) rounds. Hence one-bit communication matches the congested state of the art up to logarithmic factors. Our unique-leader algorithm also introduces a self-correcting broadcast primitive that is of independent interest. The adaptive flooding layer of Section 6 replaces the usual assumption of a b . If U b ≥ n, the primitive behaves like an known upper bound U ≥ n by a speculative estimate U ordinary flooding operation; otherwise, the certificates expose the inconsistency and trigger a restart with a larger estimate. Thus the layer provides a reusable way to convert flooding-based algorithms that assume a known size bound into stabilizing algorithms that require no prior knowledge of the network size. The results in this paper also separate our approach from the older local averaging and massdistribution methods used for counting and average-consensus-type tasks in anonymous dynamic networks [19, 27, 28, 32]. Those techniques rely on the ability to move and compare numerical quantities through the network. Such operations have no direct analogue in the one-bit broadcastcounting model. Instead, our algorithms extract information from the only numerical data that remain available: the aggregate counts of neighbors that chose 0 and 1. A one-bit cut test gives a linear conservation constraint on the sizes of refined indistinguishability classes; after enough independent constraints have been collected, the class frequencies, and then the input multiplicities when leaders are available, are determined. Thus the paper identifies a different route to global computation: not by reconstructing history, transmitting identifiers, or redistributing mass, but by turning one-bit aggregate observations into a solvable global linear system. Furthermore, for logarithmic-size inputs, this representation uses only O(n2 log n) bits of local state. This is substantially smaller than storing history-tree vistas which, after t rounds, require O(tn2 log n) bits of local state in the worst case [33]. Paper overview Section 2 defines the model and tasks. Section 3 proves the input-set lower bound. Section 4 gives the basic one-bit primitives and the near-optimal input-set algorithm. Section 5 gives known-bound algorithms for Input Frequency and Input Multiset. Section 6 removes the known-bound assumption in the unique-leader case by introducing the self-correcting adaptive flooding layer. Section 7 uses this layer to build the stabilizing Input Multiset algorithm. Section 8 discusses related work.

2

System Model

Agents and interval connectivity. The system consists of a finite, nonempty set V of n agents. Time is divided into synchronous rounds. In round t ≥ 1, the communication topology is a simple undirected graph Gt = (V, Et ) chosen by an adversary. A dynamic network is 1-interval-connected if Gt is connected in every round t. Computation, anonymity and leaders. In an anonymous system, agents have no identifiers. Each agent v starts with an input λ(v), which is assigned to it at round 0. When relevant, its local data also include its leader flag, and its initial state may depend on the common knowledge assumed,

5

such as knowledge of a U ≥ n. When we discuss local space, we mean the number of bits needed to encode an agent’s local state that includes its output register. At the beginning of each round t ≥ 0, during the communication step, each agent chooses, based on its internal state, whether to send 0 or 1. This message is then delivered to all its neighbors. After the communication step and before the end of the round, the agent learns the number of neighbors that sent 0 and the number of neighbors that sent 1. At this point, each agent uses its state and the multiset of received messages to update its state according to a deterministic algorithm A, and then proceeds to the next round.3 Note that A is the same for all agents. We call this the one-bit broadcast-counting model. When we assume the presence of multiple leaders, we mean that the input of each agent also includes a distinguished input flag, called the leader flag, and that exactly k agents start with this flag on, where k is known to all agents. The unique-leader setting is the special case k = 1. When we assume an upper bound on the network size, we assume that there is a quantity U ≥ n known to all agents. In one result, we also assume the presence of a local degree oracle. In this case, each agent v has access to an oracle that it can query at the beginning of each round t to learn the number of its neighbors in Gt . Stabilization and termination. Each agent produces an output at the end of every round. An execution stabilizes if, from some round onward, every agent has the correct output and no output changes. Internal states may continue to evolve after stabilization. An agent terminates when it enters a final state from which no further transition is possible. An execution terminates when every agent has terminated. The stabilization time is the least T such that, at the end of every round t ≥ T , every agent has the correct output and no output changes thereafter. The termination time of an execution is the round in which all agents have terminated. An admissible execution is an execution consistent with the algorithm, the assumed inputs and leader flags, the assumed initial knowledge, and an adversarial sequence of 1-interval-connected communication graphs. An algorithm computes a function if every admissible execution stabilizes to the correct output. It computes the function with termination if every agent also eventually terminates. Functions and Problems. An input assignment is a map λ : V → N>0 , together with any leader flags required by the theorem under consideration. The global input multiset of λ is µλ = {{ λ(v) : v ∈ V }}. Unless a theorem specifies a finite input universe, input values are positive integers. We write Bmax = maxv∈V ⌈log(λ(v) + 1)⌉ for the maximum input bit length. We investigate the following problems: • Counting. The Counting function is FC (v, λ) = n: every agent must output the size of the system. • Input Multiset. The Input Multiset function is FIM (v, λ) = µλ . Equivalently, for each input value a, every agent must output its multiplicity |{u ∈ V : λ(u) = a}|. Counting 3 An agent receives only a multiset of 0’s and 1’s, and no other information, such as port numbers or similar identifiers.

6

reduces to Input Multiset by having every agent ignore its original input and invoke the multiset routine with the same synthetic constant input. • Input Set. The Input Set function is FIS (v, λ) = {λ(u) : u ∈ V }. Equivalently, every agent must output the set of input values that occur in the network, ignoring their multiplicities. • Input Frequency. The Input Frequency function maps each input value a to its relative multiplicity |{u ∈ V : λ(u) = a}| . n Equivalently, it is the normalized version n1 µλ of the input multiset. • Counting upper bound. Every agent must eventually output the same finite integer U satisfying U ≥ n.

3

Lower Bound for Input-Set Computation

We prove that computing the Input Set function requires   2 n log(N/n) Ω log n rounds when the input values are drawn from a universe of size N . In particular, if N = n1+ε for a fixed ε > 0, the lower bound is Ω(n2 ), even though each input has only O(log n) bits. This remains true even if the network has a unique leader and even if all agents know both n and N . Clearly, the same lower bound applies to the Input Multiset problem. The proof is a counting argument on local histories. The adversary chooses each communication graph so that, in every round, all but a constant number of agents receive an observation that is determined by their current local history. We will show that, if too few rounds have passed, some agent has too few possible local histories to distinguish all possible input sets. Hence two different input assignments remain indistinguishable to that agent. ▶ Theorem 3.1. Suppose that input values are drawn from a universe of size N ≥ 2n. In anonymous 1-interval-connected dynamic networks, every deterministic algorithm that computes the Input Set function requires   2 n log(N/n) Ω log n rounds in the worst case. This holds even if there is a unique leader, even if all agents know n and N , even if all agents are assigned different input values, and even if the communication graph at every round is a ring (not necessarily the same ring in every round). Proof. Fix a deterministic algorithm A. We prove the lower bound in the stronger setting in which there is a unique leader and all agents know both n and N , and restrict the adversary to choosing a ring in every round. Giving information to the agents and restricting the adversary can only help the algorithm. Give the unique leader a fixed input value that is not assigned to any other

7

agent. The remaining n − 1 non-leader agents receive distinct input values from a set UN of size N , assigned to them in a well-defined canonical order. We consider one execution for every set S ⊆ UN ,

|S| = n − 1.

The adversary will choose a ring as the communication graph in every round. Hence every agent always has degree d = 2, and its observation is completely determined by the number q ∈ {0, 1, 2} of its neighbors that sent 1. We therefore identify an observation with q throughout the proof. We now describe the adversary. Consider the beginning of a round, before the graph of the round has been chosen. For each agent v, let bv be the bit that v sends in this round, given its current local history and degree 2. Since the algorithm A is deterministic and the adversary knows the execution so far, the values bv are well defined. Let V 0 = {v : bv = 0},

V 1 = {v : bv = 1}.

The adversary arranges the agents on a ring so that the agents in V 0 form one contiguous block and the agents in V 1 form the other. If one of the two classes is empty, it chooses an arbitrary ring. Thus, the communication graph is a ring in every round, although its cyclic order may change between rounds. We call an agent v ∈ V b active in this round if at least one of its neighbors belongs to V 1−b . All other agents are called inactive in this round. Since a ring containing two nonempty contiguous blocks has exactly two edges between the blocks, at most C = 4 agents are active in each round. Observe that every inactive agent in a class V b has degree 2, and both of its neighbors belong to the same class V b . Therefore, each of these three agents sends a bit according to the prediction used to define the classes V 0 and V 1 . It follows that an inactive agent observes a number of ones that is: 0

if b = 0,

2

if b = 1.

An active agent can have D = 3 observations 0, 1 and 2. For an execution and an agent v, let Hv (T ) be the local history of v up to time T : it consists of the initial state of v, including its input value and whether it is the leader, together with the sequence of its observations during the first T rounds. Since the algorithm A is deterministic, Hv (T ) determines the state of v at time T . Suppose that a non-leader agent v is active in at most R of the first T rounds. Then the number of possible histories Hv (T ) is at most N

R   X T

r

r=0

Dr .

Indeed, such a history is determined by: 1. the input value of v, with at most N choices;
2. the set of active rounds, with Tr choices if there are r active rounds; 3. the observations in the active rounds, with at most Dr choices.

8

The inactive observations do not contribute to this count, because they are forced. Given the history of v before a inactive round, the algorithm determines the bit b that v sends. Since the round is inactive, the observation is then necessarily 0

if b = 0,

2

if b = 1.

Since at most C agents are active in any one round, during the first T rounds there are at most CT pairs (v, t) such that agent v is active in round t. At least half of the n − 1 non-leader agents must be active in at most   2CT R= n−1 rounds. Indeed, if more than half of the non-leader agents were active in more than R rounds, then these agents alone would account for more than CT such pairs, a contradiction. We call a pair (S, v) quiet if S ⊆ UN is one of the input sets under consideration, v is a non-leader agent in the execution associated with S, and v is active in at most R of the first T rounds. Hence, for every input set S, at least (n − 1)/2 choices of v give a quiet pair. Therefore the total number of quiet pairs is at least   N n−1 . 2 n−1 On the other hand, as shown above, the number of possible local histories of an agent that is active in at most R rounds is at most R   X T N Dr . r r=0 Thus this also bounds the number of possible local histories that can occur in quiet pairs. We compare these two quantities. Since N ≥ 2n, 

N n−1

Thus

 log



 ≥

N n−1

n−1

 ≥

N n

n−1 .

  N n−1 ≥ (n − 1) log(N/n) − O(log n). 2 n−1

Now set T =c

n2 log(N/n) log n

for a constant c > 0 to be chosen sufficiently small. Then     n log(N/n) 2CT =O c . R= n−1 log n We now count the number of possible local histories that can arise from a quiet pair. From Stirling’s formula, we have r! ≥ (r/e)r . Hence, for every 1 ≤ r ≤ R,    r T T (T − 1) · · · (T − r + 1) Tr eT = ≤ ≤ . r r! r! r

9

Therefore

  r  T eDT r . D ≤ r r

The function

 x 7→ x log

eDT x



is increasing for x ≤ DT , because its derivative is log(DT /x). For all sufficiently large n, we have R ≤ T ≤ DT . Hence every term with 1 ≤ r ≤ R is at most 

eDT R

R .

The term r = 0 is 1, which is also bounded by the same expression. Thus R   X T r=0

Since

r

Dr ≤ (R + 1)



eDT R

R .

 2CT , R= n−1 

we have T /R = O(n). Therefore log N

R   X T r=0

r

! D

r

 ≤ log N + log(R + 1) + R log

eDT R



   T = log N + log(R + 1) + R log(eD) + log R ≤ log N + R(log n + O(1)) + O(log R) ≤ log N + O(c n log(N/n)) + O(log R), where we used our previous bound on R. Set L = log(N/n) ≥ 1. Observe that both L and O(log n) are o(nL). Hence the lower bound on the number of quiet pairs is    n−1 N log ≥ (n − 1)L − O(log n) = nL − L − O(log n) = nL − o(nL). 2 n−1 The upper bound on the number of quiet local histories is ! R   X T r log N D ≤ log N + O(cnL) + O(log R) = O(cnL) + o(nL), r r=0

10

because log N = log n + L = o(nL), and from 

nL R=O c log n



we also have log R = o(nL). Choosing c > 0 sufficiently small, the upper bound is strictly smaller than the lower bound for all sufficiently large n. Therefore N

R   X T r=0

r

Dr <

  n−1 N . 2 n−1

We conclude that there are more quiet pairs than possible local histories that can arise from quiet pairs. By the pigeonhole principle, there exist two distinct quiet pairs (S, v) and (S ′ , v ′ ) such that the local history of v in the execution associated with S is equal to the local history of v ′ in the execution associated with S ′ , up to time T . A local history contains the agent’s input value; hence v and v ′ have the same input value. We claim that S = ̸ S ′ . Indeed, if S = S ′ , then, since all inputs in S are distinct and assigned to agents in a well-defined canonical order, there is only one agent with that input value. Thus v = v ′ , contradicting the fact that (S, v) and (S ′ , v ′ ) are distinct. Therefore S ̸= S ′ . However, v and v ′ have identical local histories up to time T , and hence identical states at time T . Since the algorithm A is deterministic, both agents produce the same output at time T . But the correct Input Set outputs are different, because one execution has input set S together with the fixed leader input, while the other has input set S ′ together with the same fixed leader input. Thus the same output cannot be correct in both executions. Consequently, A cannot guarantee correctness by time c

n2 log(N/n) . log n

This proves the claimed lower bound.

◀

As a complementary observation, the frequency problem also requires large local state when the input universe is large. ▶ Remark 3.2. Suppose that input values are drawn from a finite universe of size N ≥ n. Every deterministic algorithm that computes the Input Frequency function on networks of n agents requires at least Ω(n log(1 + N n )) bits of local space in the worst case. This holds even if all agents know n and N , and even if the communication graph is static and complete in every round. Proof. Fix an agent v and fix its input to some value a in the input universe. Consider all possible multiplicity vectors for the inputs of the remaining n − 1 agents. Such a vector consists of N
−2 nonnegative integers whose sum is n − 1, so there are n+N possible vectors. N −1 Each of these vectors gives a different correct Input Frequency output at v. Indeed, because n is fixed, the frequency
of each value uniquely determines its multiplicity. Thus v must be able to −2 produce at least n+N distinct outputs while its own input remains fixed. N −1 If v uses at most s bits of local space, it has at most 2s possible local states. Since the output of an agent is determined by its local state, v can produce at most 2s distinct outputs. Consequently,

11

−2 −2 −2 2s ≥ n+N symmetry of the binomial coefficient we have n+N = n+N . Using N −1 . Now by the N −1 n−1

n+N −2 k the standard estimate m ≥ (m/k) up to constant factors in the exponent, we get log = k n−1 n+N −2 N Ω((n − 1) log( n−1 )). Since N ≥ n, this simplifies to s ≥ Ω(n log(1 + n )). ◀ From the above, when N = n1+ε for some ε > 0, each agent requires Ω(n log n) bits of local space in the worst case.

4

Basic Primitives

In this section, we discuss some basic primitives that will be used by our algorithms and the pseudocode convention that we will use. We first present the Flood algorithm, a primitive that computes the collective OR of the bits held by all agents. On top of this primitive, we build another primitive that computes the Input Set of the agents’ values. Recall that this set contains the input values, but not their multiplicities. Both procedures require an upper bound U on the network size.

4.1

Computing the OR: Flood

The Flood procedure takes a duration k and a local boolean value b. In each of the next k rounds, every agent sends its current value of b to its neighbors. If an agent receives at least one value equal to 1, it sets b to 1. After the k communication rounds, every agent returns b. We will show that, if k ≥ n − 1, then, at the end of the procedure, each agent returns the correct OR of all initial boolean values. The pseudocode is given in Algorithm 1. Pseudocode convention. We also use Algorithm 1 to explain our pseudocode convention, which follows a standard convention of synchronous distributed algorithms (see, for example, [29]). All pseudocode is written for an arbitrary agent, and the same code is executed by every agent. Unless stated otherwise, all variables are local. A statement “send b” represents one synchronous round: every agent broadcasts the value of b, computed from its local state, to its current neighbors. After this statement, the agent knows how many neighbors sent 0 and how many sent 1. All other statements are local computations and do not consume rounds. Hence a loop with k iterations and one “send” statement per iteration uses k rounds. Algorithm 1: Flood

Input: A duration k ≥ 0 and a boolean value b ∈ {0, 1} Output: If k ≥ n − 1, returns the OR of all initial boolean values 1 Function Flood(k, b): 2 for t ← 1 to k do 3 send b 4 if at least one neighbor sent 1 then 5 b←1 6 return b ▶ Lemma 4.1. Consider a 1-interval-connected dynamic network. Let S0 be the set of agents whose initial boolean value is 1. After Flood (k, b):

12

1. an agent returns 1 only if S0 ̸= ∅; 2. if S0 ̸= ∅ and |V \ S0 | ≤ k, then every agent returns 1; 3. the procedure uses exactly k rounds. Proof. For r ∈ {0, . . . , k}, let Sr be the set of agents whose boolean value is 1 after the first r rounds. The update is irreversible, so S0 ⊆ S1 ⊆ · · · ⊆ Sk . If S0 = ∅, no agent sends 1 in the first round. Consequently, no agent changes its value and S1 = ∅. Repeating the same argument inductively gives Sr = ∅ for every r ≤ k. Therefore no agent can return 1 unless some agent initially had value 1. Suppose now that S0 ̸= ∅. Consider a round r ∈ {1, . . . , k} such that Sr−1 ̸= V . Both Sr−1 and V \ Sr−1 are nonempty. Since the graph Gr of that round is connected, it contains an edge {u, v} ∈ Er with u ∈ Sr−1 and v ∈ / Sr−1 . Agent u sends 1 during round r. Hence v receives at least one value equal to 1 and sets its value to 1. Thus |Sr | ≥ |Sr−1 | + 1 whenever Sr−1 ̸= V . It follows by induction that after at most |V \ S0 | rounds all agents belong to the flooded set. Therefore, if |V \ S0 | ≤ k, then Sk = V and every agent returns 1. Finally, the procedure executes one round in each of its k iterations, so it uses exactly k rounds. ◀ ▶ Corollary 4.2. If all agents know a common upper bound U ≥ n, then Flood (U − 1, b) returns W v∈V bv at every agent, where bv is the initial boolean value of agent v. Proof. If every initial value is 0, the first part of Lemma 4.1 implies that every agent returns 0. Otherwise S0 ̸= ∅, and therefore |V \ S0 | ≤ n − 1 ≤ U − 1. The second part of the lemma implies that every agent returns 1. In both cases, the returned value is the OR of the initial values. ◀

4.2

Computing the Input Set: DistinctValues

The DistinctValues procedure is given in Algorithm 2. Every agent v invokes it with its local value x = λ(v). The first phase computes the bit length of the largest input value. The counter ℓ is initialized in line 2, and the loop in lines 3–4 uses Flood to find the smallest ℓ such that 2ℓ > Xmax . The second phase extracts the distinct values in decreasing order. The main loop starts in line 7. In each iteration, the currently remaining agents enter a bit-by-bit race, initialized in line 8. The bit loop in lines 10–15 keeps only the candidates with the largest prefix seen so far. The value found in this race is added to I in line 16, and the agents holding it are removed from later races in line 18. The final set is returned in line 19.

13

Algorithm 2: DistinctValues

Input: A positive integer value x and a common upper bound U ≥ n Output: The set of input values initially present 1 Function DistinctValues(x, U ): 2 ℓ←0 3 while Flood(U − 1, x ≥ 2ℓ ) do 4 ℓ←ℓ+1 5 I←∅ 6 remaining ← true 7 while Flood(U − 1, remaining) do 8 candidate ← remaining 9 y←0 10 for b ← ℓ − 1 downto 0 do 11 hasOne ← Flood(U − 1, candidate ∧ bit b of x is 1) 12 if hasOne then 13 set bit b of y to 1 14 if candidate and bit b of x is 0 then 15 candidate ← false 16 I ← I ∪ {y} 17 if candidate then 18 remaining ← false 19 return I ▶ Lemma 4.3. Let Bmax be the bit length of the largest input value, and let q be the number of distinct input values. Assuming a common upper bound U ≥ n, DistinctValues returns exactly the set of input values initially present. It uses O(U q(1 + Bmax )) rounds, and therefore O(U n(1 + Bmax )) rounds. Proof. Let Xmax be the largest input value in the input assignment. By definition of Bmax , all input values can be represented using bits Bmax − 1, . . . , 0, and Bmax is the smallest integer such that 2Bmax > Xmax . First consider the loop of lines 3–4. For a fixed value of ℓ, the call to Flood in line 3 returns true at every agent if and only if some input value is at least 2ℓ , by Corollary 4.2. Hence the loop increments ℓ exactly while 2ℓ ≤ Xmax . When the loop terminates, we have ℓ = Bmax . Now consider one iteration of the main loop in line 7, and let W be the set of agents with remaining = true at the start of the iteration. If W = ∅, the call to Flood in line 7 returns false, and the algorithm terminates. Otherwise, line 8 makes exactly the agents in W candidates for the current race. The loop starting in line 10 scans the bits from most significant to least significant. At bit position b, line 11 checks whether some current candidate has bit 1. If not, all candidates remain in the race. If so, line 13 sets bit b of y to 1, and line 15 removes every candidate with bit 0. Thus, after each bit position, the remaining candidates are exactly those agents in W whose scanned prefix is maximum. By induction over the bit positions, after the last bit the candidates are exactly the agents in W with maximum input value. The value reconstructed in y is therefore this maximum remaining 14

value. Line 16 adds it to I, and line 18 marks exactly the agents holding this value as no longer remaining. Hence each iteration removes one distinct input value, starting from the largest. After exactly q iterations, no agent remains, so the next test in line 7 terminates the algorithm. Therefore the set returned in line 19 is precisely the set of input values initially present. For the complexity, the first phase performs O(1 + Bmax ) calls to Flood. Each extraction performs one call in line 7 and one call per bit in line 11, hence O(1 + Bmax ) calls to Flood per extracted value. Since there are q extracted values and each call to Flood lasts U − 1 rounds, the total number of rounds is O(U q(1 + Bmax )) ≤ O(U n(1 + Bmax )). ◀ Notice that, when U = O(n), Algorithm 2 nearly matches the lower bound of Section 3. Indeed, if the inputs are drawn from a universe of size N , then Bmax = O(log N ), and the algorithm uses O(nq log N ) ⊆ O(n2 log N ) rounds. The lower bound is Ω(n2 log(N/n)/ log n) rounds. Thus, when N is polynomially related to n, the upper and lower bounds differ only by logarithmic factors. In particular, the quadratic dependence on n is essentially tight.

5

Computing with Multiple Leaders

We first compute the Input Frequency function without a leader and then derive the Input Multiset function when the number k of leader-flagged agents is known.

5.1

Computing Input Frequency

We give a terminating algorithm for the Input Frequency problem. All agents know a common upper bound U ≥ n, but no leader is required. Overview. The agents first compute the set of input values occurring in the network and assign one common label to each value. Agents with the same label form a class. If the current classes are P1 , . . . , Pm , let c = (c1 , . . . , cm ), ci = |Pi |, be their size vector. The algorithm learns homogeneous linear equations satisfied by c. Once it has m − 1 independent equations, their common solution space is the line spanned by c. Normalizing any nonzero solution so that its coordinates sum to 1 yields c c cm  1 = ,..., , n n n the frequencies of the current classes. To obtain one equation, the algorithm chooses a nonempty proper set S of class labels. In one test round, agents whose labels belong to S send 1, and all other agents send 0. Each agent counts its neighbors that sent the opposite bit. Counting the edges between the two sides from either side gives a homogeneous equation. Agents in the same class may obtain different counts. The algorithm therefore splits each class according to the count observed by its members. Previously learned equations are transferred to the refined classes and remain valid. The set S is chosen so that the new equation is independent of the previous ones. We first describe this operation, then show that a suitable S always exists, and finally give the complete algorithm.

15

5.1.1

Classes and constraints

At any step of the algorithm, the class labels are the consecutive integers 1, . . . , m, and every label is held by at least one agent. We call such labels compact. The corresponding classes are Pi = {v ∈ V : label (v) = i}, with i ∈ {1, . . . , m}. Initially, each class consists of all agents having the same input value. Since subsequent refinements may split classes but never merge them, every current class is contained in a unique initial class and therefore has a well-defined original input value. A vector a ∈ Rm is a constraint for the current partition if a · c = 0. The algorithm maintains a linearly independent list C = (a1 , . . . , ar ) of such constraints. Initially, C is empty. If r = m − 1, then the vectors in C span c⊥ . Thus every nonzero solution of the equations aj · y = 0 is a scalar multiple of c, and normalizing it by the sum of its coordinates gives c/n. 5.1.2

Obtaining one constraint with ConstraintRound

The procedure that creates a new constraint is given in Algorithm 3. Consider one invocation of ConstraintRound with a nonempty proper set S ⊊ {1, . . . , m}. We call the classes present at the beginning of the invocation the old classes, and the classes produced by the invocation the refined classes. The invocation begins with a single test round. In this round, an agent sends 1 if its old label belongs to S, and sends 0 otherwise. Here oldLabel (u) denotes the label held by u at the beginning of the invocation. For an agent u, let d1 (u) = #{neighbors of u that sent 1}, d0 (u) = #{neighbors of u that sent 0}. The opposite-side count of u is ( h(u) =

d0 (u), d1 (u),

oldLabel (u) ∈ S, oldLabel (u) ∈ / S.

Thus h(u) is the number of neighbors of u whose old labels lie on the opposite side of the partition induced by S. The test round and the computation of the opposite-side counts are implemented in lines 3–5. After the test round, ConstraintRound splits each old class according to the opposite-side counts observed by its members. For each old class x, all agents invoke DistinctValues. An agent in class x contributes the encoded value h + 2, while every agent outside class x contributes the sentinel value 1. Since h ≥ 0, the sentinel is distinct from every encoded count. After removing 1 from the set returned by DistinctValues, all agents keep the remaining encoded values in sorted order and subtract 2 only when recording the corresponding opposite-side counts. The smallest opposite-side count occurring in old class x retains label x, while every other count receives a fresh label. Fresh labels are assigned in a fixed order. Hence all agents construct the same refined partition and the same parent map. For every refined label j, parent[j] is the label of the old class from which it originates, and hj is the opposite-side count shared by all agents in the corresponding refined class. The encoded counts are collected and the old classes are refined in lines 6–16. Let c′ be the refined class-size vector, and write π(j) = parent[j]. Every previously known constraint α ∈ C is lifted to the refined classes by defining α bj = απ(j) . 16

Since the refined classes with parent i partition old class i, every lifted constraint remains valid for c′ . ′ The procedure defines a new vector a ∈ Rm by ( hj , π(j) ∈ S, aj = −hj , π(j) ∈ / S. The old constraints arePlifted in line 18, and the new constraint is defined and added in lines 19–20. Note that the sum j:π(j)∈S hj c′j counts the edges crossing the partition from the S side, whereas P ′ j:π(j)∈S / hj cj counts the same edges from the other side. The two sums are therefore equal, and hence a · c′ = 0. Thus a is a valid constraint for the refined class-size vector. Validity alone is not sufficient: the new constraint must also be independent of the lifted constraints already known. Otherwise, the invocation would add no new information about the class sizes, and the rank of the constraint system would not increase. To express the condition that guarantees independence, define KS = {z ∈ Rm : zi ≥ 0 for i ∈ S,

zi ≤ 0 for i ∈ / S} .

We call a nonempty proper set S ⊊ {1, . . . , m} a progress set for C if span(C) ∩ KS = {0}. The name reflects the role of this condition: choosing a progress set ensures that the constraint produced by ConstraintRound is independent of the lifted old constraints and therefore increases the rank of the constraint system by one. The next lemma establishes the properties of one invocation of ConstraintRound. In particular, it shows that the procedure correctly refines the classes, preserves the previously known constraints under refinement, and adds one new independent constraint whenever S is a progress set. In Section 5.1.3, we prove that a progress set always exists as long as fewer than m − 1 independent constraints are known, and we explain how all agents can select the same progress set using only local computation.

17

Algorithm 3: ConstraintRound

Input: A nonempty proper set S ⊊ {1, . . . , m}, a common upper bound U ≥ n, the current number m of classes, the constraint list C, and the local label label Output: The refined label, the new number of classes, the augmented constraint list, and the parent map 1 Function ConstraintRound(S, U, m, C, label ): 2 oldLabel ← label ; m′ ← m // Test round: agents whose old labels belong to S send 1, while all other agents send 0 3 send 1 iff oldLabel ∈ S, and send 0 otherwise 4 d1 ← number of neighbors that sent 1; d0 ← number of neighbors that sent 0 5 h ← d0 if oldLabel ∈ S, and h ← d1 otherwise 6 o←h+2 7 for x ← 1 to m do 8 z ← o if oldLabel = x, and z ← 1 otherwise 9 Ox ← DistinctValues(z, U ) \ {1} 10 write Ox = {ox,1 < · · · < ox,qx } 11 parent[x] ← x; hx ← ox,1 − 2 12 for j ← 2 to qx do 13 m′ ← m′ + 1 14 parent[m′ ] ← x; hm′ ← ox,j − 2 15 if oldLabel = x and o = ox,j then 16 label ← m′ ′ 17 C ← [] ′ 18 for each α ∈ C append its lift α b ∈ Rm to C ′ , where α bj = αparent[j] ′ 19 define a ∈ Rm by aj = hj if parent[j] ∈ S, and aj = −hj otherwise 20 append a to C ′ 21 return (label , m′ , C ′ , parent) ▶ Lemma 5.1 (Correctness of one constraint round). Assume that the current labels are compact. Let c ∈ Rm >0 be the current class-size vector, and let the vectors in C be linearly independent constraints for c. If S is a progress set for C, then after one invocation of ConstraintRound: 1. the new labels are compact, and two agents have the same new label exactly when they had the same old label and the same opposite-side count; 2. for every refined class j, parent[j] is the old label of that class and hj is the common oppositeside count of its agents; 3. the returned list C ′ contains |C| + 1 linearly independent constraints for the refined class-size vector c′ . Proof. Fix an old class x. By lines 5 and 6, every agent computes its opposite-side count h and encodes it as o = h + 2. In line 8, agents in class x contribute their encoded values, while all other agents contribute the sentinel value 1. Since every encoded value is at least 2, the sentinel cannot coincide with an encoded count. Consequently, line 9 returns exactly the encoded counts occurring 18

in class x, after the sentinel has been removed. Thus all agents obtain the same nonempty set Ox , ordered in line 10. Line 11 records the original label x as the retained label for the smallest count occurring in class x. Agents with that smallest count keep label x, because they are not relabeled later in the loop. For every remaining count, lines 13 and 14 create a fresh consecutive label and record its old parent and opposite-side count. Line 16 assigns this fresh label exactly to the agents of class x having the corresponding count. It follows that each distinct count occurring in old class x corresponds to exactly one refined class. The original label x remains in use, and every additional label is introduced consecutively. Since this construction is performed for every old class, all labels 1, . . . , m′ occur. Moreover, two agents receive the same new label exactly when their old labels and opposite-side counts agree. This proves part (1). The construction also records the old parent and the corresponding decoded opposite-side count for each retained or fresh label, proving part (2). Let π(j) = parent[j] be the parent of refined class j. In line 18, every old constraint α ∈ C is ′ replaced by the vector α b ∈ Rm defined by α bj = απ(j) . Since the children of old class i form a partition of that class, ′

′

α b·c =

m X

απ(j) c′j

=

j=1

m X

αi

i=1

X j:π(j)=i

c′j =

m X

αi ci

= 0.

i=1

Thus every lifted vector remains a constraint for c′ . The lifting map is injective. Indeed, by line 11, every old class has at least one refined child. Therefore, if two old vectors have the same lift, their coordinates agree on at least one child of every old class, and hence the old vectors are equal. It follows that the lifted constraints remain linearly independent. We next consider the vector a defined in line 19. By lines 3–5, an agent whose old label lies in S sets h equal to the number of neighbors outside S, while an agent whose old label lies outside S sets h equal to the number of neighbors inside S. Therefore, summing the relevant counts over the two sides counts the same crossing edges: X X hj c′j = hj c′j . j:π(j)∈S /

j:π(j)∈S

The signs assigned in line 19 consequently give a · c′ = 0. Hence a is also a constraint for c′ . Because S is nonempty and proper, both sides of the induced partition contain at least one agent. The communication graph in the test round is connected, so at least one edge crosses the partition. By lines 4 and 5, at least one relevant count is therefore positive. Consequently, the vector a defined in line 19 is nonzero. It remains to prove that a is independent of the lifted old constraints. Suppose, for contradiction, Pr cℓ , that a belongs to their span. ThenPthere exist coefficients λ1 , . . . , λr such that a = ℓ=1 λℓ α r 1 r ℓ where C = (α , . . . , α ). Define b = ℓ=1 λℓ α . By construction, b ∈ span(C). Moreover, for every cℓ j = αℓ . Since every old class has at least one refined refined class j, we have aj = bπ(j) , because α π(j) child and a ̸= 0, it follows that b ̸= 0. If i ∈ S, then every refined child j of i satisfies bi = aj = hj ≥ 0. If i ∈ / S, then every refined child j of i satisfies bi = aj = −hj ≤ 0. Hence 0 ̸= b ∈ span(C) ∩ KS , contradicting the assumption that S is a progress set. Therefore, a is independent of the lifted old constraints. ◀ 19

▶ Lemma 5.2. Suppose that an invocation
of ConstraintRound starts with m classes and creates s fresh labels. It uses O U (m + s) log n rounds. Proof. Lines 3 and 4 execute one communication round. Computing the relevant count and its encoding in lines 5 and 6 is local. For an old class x, let qx be the number of distinct opposite-side counts occurring in that class. By line 8, the invocation of DistinctValues in line 9 receives at most qx + 1 distinct values: the qx encoded counts and the sentinel value 1. Each opposite-side count is at most n − 1. Hence, by line 6, every encoded value is at most n + 1 and
has bit length O(log n). Lemma 4.3 therefore bounds the invocation in line 9 by O U (qx + 1) log n rounds. Lines 11–16 create one refined class P for each of the qx counts occurring in old class x. Consequently, m the total number of refined classes is x=1 qx . Since the procedure Pm starts with m labels and creates s fresh ones, the final number of classes is m + s. Therefore, x=1 qx = m + s. Summing the costs of line 9 over all old classes gives: ! m m X X
O U (qx + 1) log n = O U log n (qx + 1) x=1

x=1

= O U (2m + s) log n
= O U (m + s) log n . The lifting, construction of the new constraint, and all label operations in lines 10–21 are local. The single test round is absorbed by the stated bound. ◀ ▶ Lemma 5.3. If the initial partition has q classes, all calls to ConstraintRound create at most n − q fresh labels in total. Proof. Each fresh label denotes a new nonempty class, classes are never merged, and there can be at most n nonempty classes. ◀ 5.1.3

Choosing a set that guarantees independence

The agents do not know the class-size vector c. They therefore choose S using only the common constraint list C. We first show that a progress set exists whenever more constraints are needed, and then show how to find one locally. Recall that KS = {z ∈ Rm : zi ≥ 0 for i ∈ S, zi ≤ 0 for i ∈ / S}. ⊥ ▶ Lemma 5.4 (Existence of a progress set). Let c ∈ Rm >0 , and let L ⊆ c . If dim L < m − 1, then there exists a nonempty proper set S ⊊ {1, . . . , m} such that L ∩ KS = {0}.

Proof. Since dim L < m − 1, the space L⊥ has dimension at least two. It contains c, so choose y ∈ L⊥ that is not a scalar multiple of c. The ratios yi /ci are therefore not all equal. Choose t strictly between their minimum and maximum and different from every ratio, and set S = {i : yi /ci > t}. Then S is nonempty and proper. Suppose that a nonzero vector a ∈ L ∩ KS exists. Since a · c = 0 and every coordinate of c is positive, a has both a positive and a negative coordinate. By the definitions of S and KS , every

20

term in

m X i=1

 ai ci

yi −t ci



is nonnegative, and at least one is positive. The sum is therefore positive. But it is also equal to a · y − t(a · c) = 0, because a ∈ L and y, c ∈ L⊥ . This contradiction proves the claim. ◀ ▶ Lemma 5.5 (Testing a candidate set). Let L ⊆ Rm . For every nonempty proper set S ⊊ {1, . . . , m}, one can decide by linear programming whether L ∩ KS contains a nonzero vector. Pr Proof. Let L be given by a basis b1 , . . . , br . Write z = j=1 P θj bj and use P θ1 , . . . , θr as the variables. Impose zi ≥ 0 (i ∈ S), and zi ≤ 0 (i ∈ / S), together with z − i i∈S i∈S / zi ≥ 1. P Under the sign constraints, the last left-hand side is i |zi |. Hence feasibility implies that z is a nonzero vector in L ∩ KS . Conversely, any nonzero vector in L ∩ KS can be scaled by a positive constant to satisfy the last inequality. ◀ ▶ Corollary 5.6 (Selecting the next progress set). Let c ∈ Rm >0 , and let the vectors in C be linearly independent constraints for c. If |C| < m − 1, then all agents can select the same progress set without communication. Proof. Apply Lemma 5.4 to L = span(C). A progress set exists because dim L = |C| < m − 1. All agents know the same m and C, enumerate the nonempty proper subsets of {1, . . . , m} in the same fixed order, and use Lemma 5.5 to select the first progress set. These are local computations and use no rounds. ◀ 5.1.4

The complete Input Frequency algorithm

The InputFrequency procedure is given in Algorithm 4. The agents use DistinctValues to obtain the set of input values and assign initial labels according to their increasing order. The array origin stores the original input associated with each current class; whenever a class is split, each child inherits its parent’s value. The procedure then repeatedly calls ConstraintRound to obtain new constraints until the accumulated constraints are sufficient to compute the frequencies of the input.

21

Algorithm 4: InputFrequency

Input: A positive integer input x and a common upper bound U ≥ n Output: The frequency of every input value occurring in the network 1 Function InputFrequency(x, U ): 2 I ← DistinctValues(x, U ) 3 write I = {w1 < · · · < wm } 4 label ← i such that x = wi 5 for i ← 1 to m do 6 origin[i] ← wi 7 C←∅ 8 while |C| < m − 1 do 9 choose the first nonempty proper set S ⊊ {1, . . . , m} in a fixed common order such that span(C) ∩ KS = {0} 10 oldOrigin ← origin 11 (label , m, C, parent) ← ConstraintRound(S, U, m, C, label ) 12 for j ← 1 to m do 13 origin[j] ← oldOrigin[parent[j]] Pm 14 solve for y = (y1 , . . . , ym ) the system α · y = 0 for every α ∈ C and i=1 yi = 1 15 foreach w ∈X I do 16 fw ← yj j:origin[j]=w

17

return the map w 7→ fw for w ∈ I

▶ Theorem 5.7. Assume that all agents know a common upper bound U ≥ n. The algorithm InputFrequency computes the Input Frequency function with termination in anonymous
1-interval-connected dynamic networks. It uses O U nBmax + U n2 log n rounds. Proof. By Lemma 4.3, all agents obtain the same set I. Its increasing order gives compact initial labels, and origin records the correct input for every initial class. Initially, C is empty. At the beginning of every loop iteration, the labels are compact, every class has the correct value in origin, and the vectors in C are linearly independent constraints for the current class-size vector. If the loop guard holds, Corollary 5.6 guarantees that the required set S exists and that all agents select the same one. By Lemma 5.1, the call to ConstraintRound preserves compactness and the old constraints, adds one independent constraint, and returns the correct parent map. The update of origin is therefore also correct. Thus these properties hold throughout the execution. Each iteration increases |C| by one. Since the vectors in C are independent and orthogonal to the nonzero current class-size vector, |C| ≤ m − 1 ≤ n − 1. Every invocation of ConstraintRound terminates, by Lemma 5.2, so the loop performs at most n − 1 iterations. At termination, its guard is false; hence |C| = m − 1. Let c be the final class-size vector. The vectors in C form aP basis of c⊥ , so the homogeneous equations in the final system have solution space span{c}. Since i ci = n, the additional equation P y = 1 gives the unique solution y = c/n. For every original input value w, the current classes i i

22

with origin[j] = w partition exactly the agents whose input is w. Therefore fw =

X j:origin[j]=w

|{v ∈ V : λ(v) = w}| cj = . n n

Thus the output is correct.
For the complexity, let q = |I|. The initial call to DistinctValues uses O U q(1 + Bmax ) = O(U nBmax ) rounds, since inputs are positive integers and Bmax ≥ 1. For iteration i, let mi be the number of classes at its start and P si the number of fresh labels it creates. There are at most n − 1 iterations, m ≤ n, and i i si ≤ n − q by Lemma 5.3. Hence Lemma 5.2 gives

P 2 O U (m + s ) log n = O U n log n . Adding the initial call proves the stated bound. ◀ i i i

5.2

Input Multiset with a Known Number of Leaders

Relative frequencies become exact multiplicities once the multiplicity of some distinguished population is known. In this section we assume that exactly k ≥ 1 agents have their leader flag set, and that k is known to all agents. The InputMultisetWithMultiLeaders procedure is given in Algorithm 5. An agent with input x and leader flag b ∈ {0, 1} encodes the pair as z = 2x + b. This encoding is injective, and z is odd exactly for leaders. Note that leaders need not have the same input. After running InputFrequency on the encoded values, let fz be theP frequency of z, with fz = 0 for absent values. The total frequency of odd encoded values is fL = z odd fz = nk .
Thus all agents recover n = k/fL . For every original input a, its multiplicity is n f2a + f2a+1 . Algorithm 5: InputMultisetWithMultiLeaders

Input: A positive integer input x, the local leader flag isLeader , a common upper bound U ≥ n, and the known number k ≥ 1 of leaders Output: The multiplicity of every input value occurring in the network 1 Function InputMultisetWithMultiLeaders(x, isLeader , U, k): 2 if isLeader then 3 z ← 2x + 1 4 else 5 z ← 2x 6 f ← InputFrequency(z, U ) 7 Z ← dom(f ) 8 treat fz as 0 for every z ∈ /Z X 9 fL ← fz z∈Z: z odd

10 11 12 13 14

n b ← k/fL I ← {⌊z/2⌋ : z ∈ Z} foreach a ∈ I do
Ca ← n b f2a + f2a+1 return the map a 7→ Ca

▶ Theorem 5.8. In anonymous 1-interval-connected dynamic networks with exactly k ≥ 1 leaders, where k is known to all agents, InputMultisetWithMultiLeaders computes the In23

put Multiset function
with termination, assuming a common upper bound U ≥ n. It uses O U nBmax + U n2 log n rounds. Proof. Exactly the leaders have odd encoded values, so fL = nk > 0 and hence n b = fkL = n. For every original input a, the
agents holding a are exactly those with encoded value 2a or 2a + 1. Therefore n b f2a + f2a+1 = |{v ∈ V : λ(v) = a}|. The output is correct, and termination follows from Theorem 5.7. Since the encoding 2x + b increases the input bit length by at most one, the same theorem gives the stated complexity. ◀ The unique-leader setting is the special case k = 1. ▶ Corollary 5.9. In anonymous 1-interval-connected dynamic networks with exactly k ≥ 1 leaders, where k is known to all agents, the Counting function can be computed with termination in
O U n2 log n rounds, assuming a common upper bound U ≥ n. Proof. Each agent ignores its original input and invokes InputMultisetWithMultiLeaders with synthetic input 1, common bound U , known leader count k, and its original leader flag. The multiplicity of the synthetic value 1 is n. Since the input bit length is constant, the term O(U nBmax ) is absorbed by O(U n2 log n). ◀

5.3

Computing an Upper Bound with a Known Number of Leaders and a Local Degree Oracle

We now present a procedure that computes a common upper bound on the network size in a 1-interval-connected dynamic network with exactly k ≥ 1 leaders, k known to all agents, and a local degree oracle. The procedure, called UpperBound, is given in Algorithm 6. The algorithm considers successive trials indexed by an integer q. In the trial with parameter q, the candidate upper bound is U = k(q + k)q . Initially, exactly the k leaders are reached. Their signal then propagates for q rounds, but a reached agent forwards the signal only when its degree in the current round is at most q + k − 1. After the propagation phase, every agent invokes Flood(U, ¬reached ). Thus, an unreached agent supplies 1, while a reached agent supplies 0. If some agent is unreached, Flood returns 1 at every agent and the candidate is rejected. Otherwise, Flood returns 0 at every agent and all agents return U .

24

Algorithm 6: UpperBound

Input: The local leader flag isLeader , the known number k ≥ 1 of leaders and access to the local degree oracle Output: A common integer U satisfying U ≥ n 1 Function UpperBound(isLeader , k): 2 for q ← 0, 1, 2, . . . do 3 U ← k(q + k)q 4 reached ← isLeader 5 for t ← 1 to q do 6 d ← current degree returned by the local degree oracle 7 send 1 iff reached and d ≤ q + k − 1; otherwise send 0 8 if at least one neighbor sent 1 then 9 reached ← true 10 failed ←Flood(U, ¬reached ) 11 if ¬failed then 12 return U The local degree oracle is queried at line 6, and the returned degree is tested at line 7. An agent whose degree is larger than q + k − 1 does not immediately reject the candidate; it simply refrains from forwarding the signal. This restriction is sufficient to bound the number of reached agents by U = k(q + k)q . The invocation of Flood at line 10 has duration U , rather than U − 1. At this point, U is not yet known to be an upper bound on the entire network, so Corollary 4.2 cannot be applied. Instead, the proof shows that at most U agents begin this invocation of Flood with value 0, allowing us to apply Lemma 4.1 directly. ▶ Lemma 5.10. In anonymous 1-interval-connected dynamic networks with exactly k ≥ 1 leaders, with k known to all agents and with a local degree oracle, all agents executing UpperBound terminate in the same round with the same value U , and this value satisfies n ≤ U . Proof. Fix a trial with parameter q. For every i ∈ {0, . . . , q}, let Ri be the set of agents whose variable reached is true after the first i rounds of the propagation phase. By line 4, R0 contains exactly the leaders, and hence |R0 | = k. We first show that |Ri | ≤ k(q + k)i for every i ∈ {0, . . . , q}. Consider propagation round i, where 1 ≤ i ≤ q. By synchrony, only agents in Ri−1 can send 1 in this round. By line 7, every agent that sends 1 has degree at most q + k − 1. Therefore, each sender can cause at most q + k − 1 agents to become newly reached, and at most (q + k − 1)|Ri−1 | agents become newly reached in total. It follows that |Ri | ≤ (q + k)|Ri−1 |. Since |R0 | = k, induction gives |Ri | ≤ k(q + k)i . In particular, at the end of the propagation phase we have |Rq | ≤ k(q + k)q . By line 3, the candidate is U = k(q + k)q , and therefore |Rq | ≤ U . Consider now the invocation of Flood at line 10. Let S0 be the set of agents whose initial value in this invocation is 1. Since the initial value is ¬reached , we have S0 = V \ Rq . If S0 is empty, all agents invoke Flood with value 0. By part (1) of Lemma 4.1, every agent returns 0. Suppose instead that S0 is nonempty. The agents that invoke Flood with value 0 are exactly the agents in Rq . Consequently, |V \ S0 | = |Rq | ≤ U . Since the duration of Flood is U , part (2) of

25

Lemma 4.1 implies that every agent returns 1. Thus, the call to Flood returns the same value at every agent and, because the duration of the trial is fixed by q, it returns in the same round at every agent. It returns 1 exactly when at least one agent remains unreached. Consequently, all agents either reject the current candidate and proceed to the next trial in the same round or return the same value U at line 12 in the same round. Suppose that the agents return in the trial with parameter q. Then Flood returned 0, so no agent was unreached and Rq = V . Since |Rq | ≤ U , it follows that n = |V | = |Rq | ≤ U . Therefore, every returned value is a valid upper bound. It remains to prove termination. Consider the trial with parameter q = n − k. Every agent has degree at most q + k − 1 = n − 1, so every reached agent sends 1 at line 7. If some agent is still unreached at the beginning of a propagation round, connectivity of the communication graph implies that there is an edge between a reached agent and an unreached agent. The reached endpoint sends 1, and hence at least one new agent becomes reached at line 9. Starting with the leaders, all n agents therefore become reached within n − k rounds. The call to Flood returns 0, and all agents terminate. Hence UpperBound terminates for every network size. ◀ ▶ Lemma 5.11. Assume that 1 ≤ k ≤ n. Then UpperBound returns a value U ≤ nn−1 and uses O(nn ) rounds. Proof. By the proof of Lemma 5.10, the trial with parameter q = n − k succeeds. Therefore, the algorithm terminates in a trial with some parameter q ∗ ≤ n − k. The returned value is ∗ U = k(q ∗ + k)q . Since k ≤ n, q ∗ + k ≤ n, and q ∗ ≤ n − k, we obtain U ≤ knn−k ≤ n · nn−2 = nn−1 , if k ≥ 2. If ∗ k = 1, then U = (q ∗ + 1)q ≤ nn−1 . Thus, in all cases, U ≤ nn−1 . A trial with parameter q uses exactly q rounds for the propagation phase. By part (3) of Lemma 4.1, the call to Flood uses exactly k(q + k)q rounds. Since the algorithm terminates with q ∗ ≤ n − k, fewer than n trials are executed. The propagation phases use fewer than n2 rounds in total. Moreover, by the bound proved above, every flooding phase in an executed trial uses at most nn−1 rounds. Since fewer than n trials are executed, the flooding phases use at most n · nn−1 = nn rounds in total. Hence the overall number of rounds is O(nn ). ◀ Already at this point, combining UpperBound with the known-bound algorithms of this section gives the following immediate corollary. ▶ Corollary 5.12. In anonymous 1-interval-connected dynamic networks with exactly k ≥ 1 leaders, with k known to all agents and with a local degree oracle, Input Frequency, Input Multiset, and Counting can be computed with termination without any initially known upper bound on the network size. The round complexities are O(nn Bmax + nn+1 log n) for Input Frequency and Input Multiset, and O(nn+1 log n) for Counting. Proof. Run UpperBound first. By Lemma 5.10, all agents terminate with the same value U satisfying U ≥ n. This value can then be used as the common upper bound required by Theorem 5.7, Theorem 5.8, and Corollary 5.9. Lemma 5.11 gives U ≤ nn−1 and O(nn ) rounds to compute the bound. Substituting this U into the known-bound complexities gives O(nn−1 · nBmax + nn−1 · n2 log n) = O(nn Bmax + nn+1 log n) for Input Frequency and Input Multiset, and O(nn−1 · n2 log n) = O(nn+1 log n) for Counting. These terms dominate the cost of UpperBound. ◀ 26

6

Adaptive Flooding Without a Known Bound

The known-bound algorithms of the previous sections use calls of the form Flood(U − 1, x), where all agents know a common upper bound U ≥ n. Such a call computes the OR of the local input bits and, when all agents start it in the same round, also gives all agents a common finishing round. We now remove the initially known bound by providing a communication layer that only requires a leader and can be used to simulate the Input Multiset algorithm described in the previous section, leading to a stabilizing algorithm. b of the network size and runs the known-bound The communication layer maintains an estimate U Input Multiset algorithm in successive trials. A trial starts either at the beginning of the execution or when the layer delivers a Restart event. When a Restart event is delivered, the current copy b. of the simulated algorithm is discarded and a fresh copy is started with the current value of U The communication layer exposes to the simulation algorithm the following interface. b is the current estimate. The simulated algorithm may read this value but cannot modify it. • U • AdaptiveFlooding (x), where x ∈ {0, 1}, replaces every call to Flood(U − 1, x) of the known-bound algorithm. • DetectError is an operation by which the simulated algorithm may invalidate the current trial. In the Input Multiset simulation below this happens when the computed value is not b. consistent with the estimate U • Restart is a local event delivered by the layer. When it is delivered, the current trial is invalidated and the next trial starts from the initial state of the simulated algorithm. Local events delivered by the layer are processed at the beginning of a round, before the simulated algorithm takes its next step. Before the final successful trial, trials are speculative: a call to AdaptiveFlooding may return any value in {0, 1}, and any output produced by the simulated algorithm may be arbitrary. Correctness is required only after the last restart, or from the beginning if no restart occurs.

6.1

Adaptive Flooding

The AdaptiveFlooding routine is given in Algorithm 7. b , initially 1. It also stores a boolean flag invalid , initially false. Each agent stores the estimate U An agent with invalid = true has abandoned the current trial; an agent with invalid = false is active. The operation DetectError invalidates the current trial at the executing agent by setting b and may call DetectError, but it cannot invalid to true. The simulated algorithm may read U read or modify invalid . The read-only predicate IsInvalid, used later by the terminating wrapper, is the predicate invalid = true. A call to AdaptiveFlooding has a common start if all active agents invoke the call in the same round. It terminates synchronously if all active agents receive its return value in the same round. b in place of the unknown upper bound. It first floods The routine AdaptiveFlooding uses U b − 1 rounds and obtains a local value y. the input bit for U Then two floodings are executed in which the leader certifies the value it obtained as the result of the first flood, and other agents verify that the value each received is consistent with the one received by the leader. In the first one, the leader’s initial bit is 1 exactly when the leader’s value is 27

0; in the second one, the leader’s initial bit is 1 exactly when the leader’s value is 1. Thus the leader always participates in both certificate floodings, but its pair of initial certificate bits is either (1, 0) or (0, 1), never (0, 0). All other agents participate in the two floodings with (0, 0). An agent accepts its local value only if it receives the certificate corresponding to that value. Algorithm 7: Adaptive flooding

Input: A local boolean value x Output: A boolean value 1 Function AdaptiveFlooding(x): b − 1, x) 2 y ← Flood(U b − 1, isLeader ∧ y = 0) 3 c0 ← Flood(U b − 1, isLeader ∧ y = 1) 4 c1 ← Flood(U 5 if (y = 0 ∧ ¬c0 ) or (y = 1 ∧ ¬c1 ) then 6 DetectError() 7 return y The two certificates are needed because the absence of a one-bit signal is not informative by itself: it may mean that the leader certified the other value, or that the matching certificate did not reach the agent. With two certificates, every agent that returns without calling DetectError can verify that its local value agrees with the leader’s value. b ≥ n then AdaptiveFlooding behaves like a normal flood We now show that if the estimate U and no agent flags the current trial as invalid. ▶ Lemma 6.1. Assume that no agent is invalid before a common-start call to AdaptiveFlooding, b in this call. Then all agents reach the return statement and that all agents use the same estimate U in the same round. Moreover, either some agent becomes invalid during the call, or all agents return b ≥ n, then all agents return the global OR and no agent the global OR of their input bits. If U becomes invalid. Proof. Consider a common-start call and assume that no agent is invalid before it starts. Since all agents use the same estimate, the three floodings in lines 2–4 have the same fixed durations at all agents. Hence all agents reach the check in line 5 and the return statement in line 7 in the same round. Let b be the leader’s value after the first flooding. In the certificate flooding of line 3, the leader’s initial bit is 1 exactly if b = 0; in the certificate flooding of line 4, the leader’s initial bit is 1 exactly if b = 1. No other agent can have initial bit 1 in either certificate flooding. Suppose that an agent reaches line 7 without calling DetectError in line 6. If its local value is y = 0, then the test in line 5 implies that it received c0 = 1. By Lemma 4.1, this is possible only if some agent had initial bit 1 in the certificate-for-0 flooding of line 3; hence the leader had b = 0. Similarly, if its local value is y = 1, then receiving c1 = 1 implies, through line 4, that the leader had b = 1. Therefore every agent that returns without invalidating the trial has y = b. If no agent becomes invalid during the call, all agents return the same value b. If some input bit is 1, then an agent holding such a bit has value 1 after the value-flooding of line 2, because flooding never changes a 1 to 0. Since all returned values are equal in the non-invalid case, the common value must be 1. If all input bits are 0, flooding cannot create a 1, by Lemma 4.1; hence the common value is 0. Thus, in the non-invalid case, the returned value is exactly the global OR. 28

b ≥ n. Each internal flooding in lines 2–4 has duration U b − 1 ≥ n − 1. By Finally suppose that U Corollary 4.2, the first flooding returns the global OR at every agent, and the certificate for this common value reaches every agent. Therefore the condition in line 5 is false at every agent, and no agent calls DetectError. ◀

6.2

Recovery Service

The purpose of recovery is to turn a call to DetectError at one agent into a synchronized restart with a larger estimate. The implementation uses three logical recovery protocols, called invalidation, control, and reset. These protocols are multiplexed by interleaving the rounds of their execution. An execution of a recovery protocol means one round of that logical protocol. Consecutive executions are consecutive inside that protocol’s own subsequence; after the protocols are interleaved, they need not be adjacent rounds of the underlying network. For an estimate u, a control window is a group of u consecutive executions of the control protocol, measured from the beginning of the current trial. At the first execution of a control window, an active leader starts a control signal, and active agents relay it until the window ends. A reset window is defined analogously for the reset protocol: it is a group of consecutive executions of the reset protocol, its length is prescribed by a deterministic reset calendar known to all agents, and reached agents update their estimate only at the common end of the window. The recovery service uses the invalidation, control, and reset protocols to achieve the synchronized restart in three phases. Invalidation propagation. The purpose of this phase is to propagate the information of an invalid trial to the entire network. Once an agent becomes invalid, it repeatedly announces this fact. Any agent that hears such an announcement also calls DetectError and becomes invalid. Therefore, if a trial is invalidated anywhere, invalidation eventually reaches the leader. Silent control window. The leader does not reset immediately after becoming invalid. Instead, it waits through one complete control window of length equal to the current estimate. In a normal control window, an active leader would start the control signal. An invalid leader does not send such a signal. Hence every agent that still trusts the old trial misses the signal and calls DetectError by the end of the window. Thus, before the reset starts, no agent still trusts the old trial. Calendar reset. After the silent control window has ended, the leader waits for a reset window of b and floods a reset signal through that window. Every agent reached by the signal installs length 2U b , propagates the signal in the window, and when the window ends, clears its invalid the estimate 2U flag and generates a Restart. If the window is too short to reach all agents, the unreached agents b ≥ n, the reset remain invalid; their invalidation announcements eventually force another reset. If 2U reaches every agent. The reset calendar is local and deterministic. It is divided into stages. Stage h is the finite sequence of reset windows whose lengths are 1, 2, 4, . . . , 2h . Thus the calendar begins 1;

1, 2;

1, 2, 4;

1, 2, 4, 8;

...

and every power of two appears infinitely often. No messages are needed to construct the calendar: all agents advance the same deterministic calendar whenever the reset protocol is scheduled, so they agree on the length and the end of the current reset window. 29

channels

reset rounds calendar

S

I

C

R

S

I

C

R

1

2

1

1

stage 0

S

I

C

R

S

I

3

C

R

4

2 stage 1

Figure 1. The four channels are interleaved in the fixed order: simulation (S), invalidation propagation (I), control (C), reset (R). The reset calendar advances only on the reset-channel subsequence. Thus the window labeled 2 consists of two reset-channel rounds, shown as reset rounds 3 and 4.

Figure 1 illustrates the interleaving of the channels and the concept of a reset window.

6.3

Implementation by Four Interleaved Channels

A channel is a logical protocol executed on a prescribed subsequence of rounds. The implementation uses four channels: simulation, invalidation, control, and reset. The scheduler assigns rounds cyclically to these channels in that order. A channel round is one execution of the corresponding channel. Since the network graph is connected in every round, the graph sequence observed by each channel is connected in every channel round. The simulation channel executes the simulated algorithm. Each round of an unfinished AdaptiveFlooding call is executed as one simulation-channel round. At the beginning of every simulation-channel round, the layer first checks whether a restart flag has been set. If so, it delivers Restart to the simulated algorithm and aborts any unfinished simulated operation. The recovery service is implemented by Algorithms 8, 9 and 10. Recovery service initialization. Algorithm 8 initializes the estimate, flags, control-position, and reset-calendar variables in lines 2–12. It then runs the four logical channels cyclically: the simulation channel is executed in lines 16–18, followed by one invalidation, control, and reset channel round in lines 19–21. Invalidation and control. Algorithm 9 contains the invalidation and control logic. The operation DetectError marks the current trial as invalid in lines 2–3; if the leader is the agent that becomes invalid, lines 4–7 start the wait for a complete silent control window. Invalidation is propagated by lines 9–11 of Algorithm 9. The control window is also implemented directly in Algorithm 9. The local variable controlPos, initialized in line 7 of Algorithm 8 and updated in lines 13–16 of Algorithm 9, records the current b , this position ranges over 1, . . . , U b; position in the control window. When the current estimate is U b is its last round. When position 1 is the first control-channel round of the window and position U an agent installs a new estimate, line 19 of Algorithm 10 resets controlPos to 0, so the next controlchannel round starts a fresh control window for the new trial. The leader uses the flags waitSilent and resetReady: the first means that the leader has become invalid and is waiting for one complete silent control window, while the second means that this silent window has ended and the leader may b. start the next reset window of length 2U The control position is advanced in lines 13–16; the beginning of a control window is handled in lines 17–19; the control signal is sent and relayed in lines 20–22; and a missing signal or the end of

30

the silent window is handled in lines 23–28. Reset and restart. Algorithm 10 contains the reset calendar and reset flooding. Lines 2–4 of Algorithm 10 define the calendar. Lines 6–8 open a new reset window when the previous one ends. Once the silent control window has ended, the leader starts a reset exactly at the beginning of the b , by lines 9–11. The reset signal is flooded in lines 12–14. Agents next reset window of length 2U reached by the reset signal wait until the common end of that window, then lines 15–24 install the window value as the new estimate, clear the invalid flag, reset the control position, and set the local flag that will be delivered as Restart on the next simulation-channel round. Algorithm 8: Initializing and scheduling the four-channel layer 1 Function InitializeCommunication():

b ←1 U invalid ← false restart ← false reset ← false 6 control ← false 7 controlPos ← 0 // position inside the current control window; 0 means no window has started 8 waitSilent ← false // leader flag: waiting for one complete silent control window 9 silentWindow ← false 10 resetReady ← false // leader flag: the silent control window has ended 11 Ureset ← ⊥ 12 Treset ← 0 13 Function RunAdaptiveLayer(): 14 InitializeCommunication() 15 while true do 16 restartEvent ← restart 17 restart ← false 18 execute one simulation-channel round, delivering a Restart event iff restartEvent 19 InvalidationRound() 20 ControlRound() 21 ResetRound() 2 3 4 5

31

Algorithm 9: Invalidation propagation and control windows 1 Function DetectError(): 2 if ¬invalid then 3 invalid ← true 4 if isLeader then 5 waitSilent ← true 6 silentWindow ← false

resetReady ← false 8 Function InvalidationRound(): 9 send 1 iff invalid ; otherwise send 0 on the invalidation channel 10 if at least one neighbor sent 1 then 11 DetectError() 12 Function ControlRound(): // advance the position inside the current control window b then 13 if controlPos = 0 or controlPos = U 14 controlPos ← 1 15 else 16 controlPos ← controlPos + 1 // beginning of a control window 17 if controlPos = 1 then 18 control ← isLeader ∧ ¬invalid 19 silentWindow ← isLeader ∧ invalid ∧ waitSilent 20 send 1 iff control ∧ ¬invalid ; otherwise send 0 on the control channel 21 if ¬invalid and at least one neighbor sent 1 then 22 control ← true // end of a control window: active agents must have received the control signal b and ¬invalid and ¬control then 23 if controlPos = U 24 DetectError() b and silentWindow then 25 if controlPos = U 26 resetReady ← true 27 waitSilent ← false 28 silentWindow ← false 7

32

Algorithm 10: Reset calendar and reset windows 1 Function ResetCalendar(): 2 for h ← 0, 1, 2, . . . do 3 for i ← 0 to h do 4 yield 2i 5 Function ResetRound(): 6 if Treset = 0 then 7 Ureset ← ResetCalendar() 8 Treset ← Ureset

25

b and isLeader and resetReady then if Treset = Ureset and Ureset = 2U reset ← true resetReady ← false send 1 iff reset; otherwise send 0 on the reset channel if at least one neighbor sent 1 then reset ← true if Treset = 1 and reset then invalid ← false reset ← false control ← false controlPos ← 0 waitSilent ← false silentWindow ← false resetReady ← false b ← Ureset U // restart the simulation and start a new trial restart ← true Treset ← Treset − 1

6.4

Correctness and Cost of Recovery

9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

We first record the synchronization properties that follow from the deterministic scheduler and reset calendar. ▶ Lemma 6.2. All agents execute the same channel in the same rounds. Moreover, all agents advance the reset calendar synchronously and therefore agree on the boundaries and lengths of all reset windows. Proof. The four-channel loop in Algorithm 8 is fixed: one simulation-channel round is executed in line 18, then the invalidation, control, and reset channels are executed in lines 19, 20, and 21. Since every agent runs this same loop, all agents execute the same channel in the same rounds. It remains to consider the reset calendar. Initially all agents set Ureset = ⊥ and Treset = 0 in lines 11–12, and no agent has requested a calendar value. Suppose these values, and the number of previous calendar requests, are the same at all agents at the beginning of a reset-channel round. The test in line 6 has the same truth value everywhere. If it is true, all agents request the next calendar value in line 7; the calendar generated by lines 2–4 of Algorithm 10 is deterministic, so they 33

receive the same value and set the same countdown in line 8. If the test is false, no agent requests a new value. In both cases all agents decrement the countdown once in line 25. Thus the calendar state remains synchronized by induction, and the reset-window boundaries and lengths are common to all agents. ◀ ▶ Lemma 6.3. An execution of q rounds on any one of the four channels uses at most 4q rounds. Proof. The scheduler in Algorithm 8 executes the channels cyclically: one simulation-channel round in line 18, one invalidation-channel round in line 19, one control-channel round in line 20, and one reset-channel round in line 21. Hence each channel is selected exactly once in every four consecutive rounds. The interval from the first to the q-th occurrence of a fixed channel has length 4(q − 1) + 1 ≤ 4q. ◀ ▶ Lemma 6.4. If at least one agent is invalid, then every agent becomes invalid within n − 1 invalidation-channel rounds, and hence within 4(n − 1) rounds. Proof. In an invalidation-channel round, invalid agents send 1 in line 9. Any active agent that receives such a 1 calls DetectError in line 11 and becomes invalid in line 3. As long as some agent is active and some agent is invalid, connectedness provides an edge crossing the cut between the two sets in the next invalidation-channel round. Therefore at least one active agent becomes invalid in each such round. Starting from one invalid agent, after at most n − 1 invalidation-channel rounds all agents are invalid. The bound in rounds follows from Lemma 6.3. ◀ ▶ Lemma 6.5. Throughout the execution, all active agents have the same estimate and the same control position. Fix an interval between two consecutive reset completions, or the initial interval before the first reset completion, and let u be the common estimate of the active agents at the beginning of the interval. If some agent is invalid during this interval, then the leader eventually initiates a reset flooding at the beginning of a reset window of length 2u. At the beginning of that window all agents are invalid. All agents reached during the window set their estimate to 2u, reset their control position to 0, and observe Restart in the same round. If 2u ≥ n, the reset reaches all agents. Proof. We argue by induction over reset completions. Initially all agents are active, have estimate 1, and have control position 0, by lines 2, 3, and 7 of Algorithm 8. Thus the invariant holds before the first reset completion. Assume that, at the beginning of the current interval, all active agents have the same estimate u and the same control position. While no reset completes, estimates do not change. In every control-channel round, all active agents update their position by the same deterministic rule in lines 13–16 of Algorithm 9, using the same estimate u. If an active agent becomes invalid, it leaves the active set by line 3 of Algorithm 9. Hence all active agents continue to have the same estimate and the same control position throughout the interval. If some agent is invalid, Lemma 6.4 implies that invalidation reaches every agent within at most n − 1 invalidation-channel rounds; in particular, the leader eventually becomes invalid. When the leader first becomes invalid in this interval, it has estimate u. It sets waitSilent to true and clears the two waiting flags in lines 5–7 of Algorithm 9. Consider the first control window whose first round occurs after this event. At the first round of this window, all active agents enter position 1 together by lines 13–14 of Algorithm 9. The leader is invalid and waitSilent = true, so the leader sets silentWindow to true in line 19 of Algorithm 9 and does not start a control signal in line 18 of Algorithm 9. Every active non-leader also sets its control flag to false in line 18

34

of Algorithm 9. During the window, invalid agents send 0 on the control channel by line 20 of Algorithm 9, and no active agent can create a control signal unless it first receives one and executes line 22 of Algorithm 9. Since the invalid leader starts no signal, no active agent receives one in the window. Therefore, at the last round of the window, every agent that is still active satisfies the test in line 23 of Algorithm 9 and calls DetectError in line 24 of Algorithm 9. Thus all agents are invalid by the end of the silent control window. At that same last round, the leader sets resetReady to true in line 26 of Algorithm 9 and clears the waiting flags in lines 27–28 of Algorithm 9. After the silent control window, the leader waits until the first reset-calendar window whose value is 2u. Such a window exists because the calendar of lines 2–4 of Algorithm 10 contains every power of two infinitely often. At the beginning of that window, the condition in line 9 of Algorithm 10 holds at the leader: the window has just started, its value is 2u, and resetReady is true. Hence the leader sets reset to true in line 10 of Algorithm 10 and starts a reset flooding. By Lemma 6.2, all agents agree on the window boundaries and on the value Ureset = 2u. During the window, the reset signal is flooded by lines 12–14. Every reached agent has reset = true at the last reset-channel round of the window and therefore satisfies the test in line 15. It then clears its invalid flag, resets its control position, installs the estimate 2u, and sets its local restart flag in lines 16–24. Since all reached agents agree on the end of the reset window, they perform these updates in the same round and install the same new estimate and control position. The restart flag is read and cleared in lines 16–17, and the corresponding Restart event is delivered in line 18. By Lemma 6.2, this is the same round for all reached agents. Hence they observe Restart synchronously. If 2u ≥ n, then the reset window has length at least n. Starting from the leader, the reset signal is flooded for at least n reset-channel rounds by lines 12–14. By the flooding argument of Lemma 4.1, it reaches every agent by the end of the window. The only agents that become active after the reset are the reached agents, which clear invalid in line 16; all of them install the same estimate in line 23 and reset their control position to 0 in line 19. Agents not reached, if any, remain invalid. Thus the induction invariant is preserved for the next interval. ◀ b uses O(U b ) rounds. ▶ Lemma 6.6. One call to AdaptiveFlooding with estimate U b − 1. Each round Proof. The routine performs three calls to Flood in lines 2–4, each of duration U of these internal floodings is executed in one simulation-channel round by line 18. Thus the call uses b − 1) = O(U b ) simulation-channel rounds, and the bound in rounds follows from Lemma 6.3. ◀ 3(U We separate two kinds of cost in the analysis. The calendar cost is the passive delay after the leader is ready to reset but before the deterministic reset calendar reaches a window of the required length. The non-calendar cost of an interval with fixed leader estimate is all other work charged to that interval: simulation work until some agent aborts, invalidation propagation, the silent control window, and the actual flooding inside the reset window once that window has begun. Thus reset flooding is non-calendar cost, while waiting for the appropriate reset-window boundary is calendar cost. ▶ Lemma 6.7 (Non-calendar recovery cost). After the first invalidation in an interval with common active estimate u, the recovery cost excluding the waiting time for the appropriate resetcalendar window is O(n + u) rounds.

35

Proof. By Lemma 6.4, invalidation reaches all agents, and in particular the leader, within O(n) rounds, using lines 9–11 of Algorithm 9. When the leader becomes invalid, lines 5–7 of Algorithm 9 start the wait for a complete silent control window. The position update in lines 13–16 of Algorithm 9 implies that at most one partial control window remains before the first silent control window starts, and that silent window has length u. At its end, the leader sets resetReady in line 26 of Algorithm 9. Hence reaching the end of the silent control window costs O(u) channel rounds, and therefore O(u) rounds by Lemma 6.3. When the reset window of length 2u begins, the leader starts the reset in lines 9–10 of Algorithm 10, and the reset flooding of lines 12–14 of Algorithm 10 costs O(u) more rounds. These are the only recovery costs not counted as calendar waiting. ◀ ▶ Lemma 6.8 (Reset-calendar waiting time). Suppose that t reset-channel rounds have elapsed when the leader starts waiting for a reset window of length u = 2k . The desired window begins after at most t + O(u + log(t + 2)) additional reset-channel rounds. Consequently, if T rounds have elapsed at that time, then the waiting costs at most T + O(u + log(T + 2)) additional rounds. Proof. The calendar is generated by ResetCalendar in Algorithm 10: stage j consists of the reset windows of lengths 1, 2, 4, . . . , 2j , and therefore has total length 2j+1 − 1. Let the leader start waiting during stage h. The total length of the stages preceding stage h is 2h+1 − h − 2, and hence h = O(log(t + 2)). Finishing the current stage costs at most t + O(log(t + 2)) additional reset-channel rounds. After the current stage ends, a window of length u = 2k appears no later than stage max{h+1, k}, again by the definition of ResetCalendar. If k ≤ h + 1, then after finishing the current stage, the desired window appears during stage h + 1, and the part of that stage before the window has length less than u. If k > h + 1, then the total length of stages h + 1, . . . , k before the desired window is O(2k ) = O(u). Thus the desired window begins after at most t + O(u + log(t + 2)) additional reset-channel rounds. After T ordinary rounds, at most ⌊T /4⌋+1 reset-channel rounds have elapsed, and each additional reset-channel round costs at most four ordinary rounds by the scheduler lines 18–21. The waiting time in ordinary rounds is therefore at most T + O(u + log(T + 2)). ◀ ▶ Lemma 6.9 (Calendar amortization). Let ui = 2i , and suppose that the leader initiates exactly r resets. Let Ti be the elapsed time at the beginning of the interval with leader estimate ui . If Hi is an upper bound on the non-calendar cost charged to that interval, including simulation work before invalidation propagation, the silent control window, and the reset flooding, and if the sequence Hi is nondecreasing and satisfies P Hi = Ω(ui ),then the total time until the beginning of the interval r−1 r−1−i with leader estimate ur is O . i=0 Hi 2 Proof. Let Ai be the non-calendar cost incurred before the leader starts waiting for the appropriate reset window, and let Bi be the non-calendar cost incurred after that waiting period, including the reset flooding. By the definition of Hi , we may assume Ai + Bi ≤ Hi . Let Si = Ti + Ai be the elapsed time when the leader starts waiting. By Lemma 6.8, the waiting period lasts at most Si + O(ui + log(Si + 2)) rounds. So the total time until the beginning of the next interval is Ti + Ai + Si + O(ui + log(Si + 2)) + Bi , which, since Si = Ti + Ai , equals 2Ti + 2Ai + Bi + O(ui + log(Si + 2)). Using Ai + Bi ≤ Hi , Ai ≤ Hi and Hi = Ω(ui ), this is 2Ti + O(Hi + log(Ti + Hi + 2)) = 2Ti + O(Hi + log(Ti + 2)). Then Ti+1 = 2Ti + O(Hi + log(Ti + 2)).

36

We first derive a coarse bound. Since log(Ti + 2) ≤ Ti + 2 and Hi = Ω(ui ) = Ω(1), we get Ti+1 ≤ O(Ti + Hi ). Since the sequence Hi is nondecreasing and T0 = 0, induction gives Ti ≤ Kci Hi for some sufficiently large constant K and c independent of i. We now bound the logarithmic term more sharply. From the coarse bound, log(Ti + 2) ≤ log(Kci Hi + 2) = O(i + log(Hi + 2)). Since Hi = Ω(ui ) = Ω(2i ), we have i = O(log(Hi + 2)), and therefore log(Ti + 2) = O(log(Hi + 2)) = O(Hi ). Substituting this into the previous recurrence gives Ti+1 ≤ 2Ti + c′ Hi for a constant c′ independent of i. Unfolding this recurrence over r resets gives ! r−1 X r−1−i Tr = O Hi 2 , i=0

which proves the claimed bound.

7

◀

Stabilizing Input Multiset and Counting

We now combine the recovery layer with the known-bound Input Multiset algorithm. The procedure is given in Algorithm 11. Each trial simulates InputMultisetWithMultiLeaders. Every flooding call is replaced by AdaptiveFlooding. When a trial returns a candidate multiset, b . If so, the agent checks whether the total multiplicity represented by the candidate is larger than U the estimate is certainly too small, and the agent invalidates the trial by calling DetectError. Otherwise the candidate becomes the current stabilizing output. Algorithm 11: Stabilizing Input Multiset without a known bound

Input: An input value input Output: A stabilizing output for the Input Multiset function 1 Function StartInputMultisetTrial(): 2 initialize a simulation of InputMultisetWithMultiLeaders on input 3 answer ← ⊥ 4 Function StabilizingInputMultiset(input): 5 start the communication layer 6 StartInputMultisetTrial() 7 while true do 8 if Restart event occurs then 9 StartInputMultisetTrial() 10 else 11 execute the next step of the current simulation, replacing each call to Flood (U − 1, x) by AdaptiveFlooding (x) 12 if the current simulation returns a candidate multiset C then b 13 if C is not a well-formed multiset or its total multiplicity is larger than U then 14 DetectError() 15 else 16 answer ← C 17 output answer

37

We use two simple properties of the simulated known-bound algorithm. First, if a trial starts at all agents in the same round and all completed calls to AdaptiveFlooding have returned the correct global OR synchronously, then the next simulated flooding call, if any, is invoked by all agents in the same round. This is just the usual lockstep behavior of the known-bound synchronous algorithm: all ordinary communication steps have fixed duration, and every completed adaptive-flooding call has the same return round at all agents. Second, the correctness proof of the known-bound Input Multiset algorithm uses the bound only to guarantee that the flooding calls return the global OR. Thus, if all flooding calls are answered by correct global ORs, the simulated execution returns the correct input multiset. ▶ Lemma 7.1. Consider the known-bound InputMultisetWithMultiLeaders algorithm. If each call to Flood(U − 1, x) is replaced by a synchronous oracle that returns one bit, and if all oracle calls return the correct global OR at all agents in the same simulation-channel round, then a synchronously started execution stays in lockstep. The algorithm makes O(nBmax + n2 log n) such OR calls and O(n) further one-round cut-test steps. Proof. The known-bound algorithm is synchronous and deterministic. Between flooding calls, all ordinary communication steps have fixed duration, and every local choice is determined by the common state, the local input, and the observations already obtained. Hence, if the previously consumed oracle calls return in the same simulation-channel round at all agents, the next oracle call, if any, is invoked by all agents in the same simulation-channel round. The correctness proof of Theorem 5.8 uses the bound U only through Lemma 4.1, namely to ensure that each Flood(U − 1, x) call returns the global OR. Replacing those calls by a correct synchronous OR oracle therefore preserves the simulated execution and its output. The call bound follows from the complexity proof of Theorem 5.8: the O(U nBmax + U n2 log n) term is U times the number of flooding calls, while ConstraintRound contributes only O(n) additional one-round cut tests over the whole execution. ◀ ▶ Lemma 7.2. Consider a synchronously started adaptive Input Multiset trial with common estimate u, and suppose all agents are active at the beginning of the trial. If no agent invalidates before the simulated execution produces a candidate multiset C, then all agents produce the same C in the same simulation-channel round, and C is the correct input multiset. In particular, |C| = n. Proof. We argue by induction over the adaptive-flooding calls consumed by the simulation before C is produced. At the start of the trial, all agents are in the same simulated state with the same estimate. If all previous adaptive-flooding calls have returned the correct global OR synchronously, the lockstep part of Lemma 7.1 implies that the next such call, if any, has a common start. Since no agent invalidates before C is produced and all active agents have the same estimate by Lemma 6.5, Lemma 6.1 implies that this call returns the correct global OR synchronously. Thus every flooding answer consumed before C is a correct global OR. By Lemma 7.1, the simulated known-bound execution therefore returns the correct input multiset. The same lockstep induction gives the same return round and the same candidate C at all agents. Since C is the global input multiset, its mass is n. ◀ ▶ Lemma 7.3 (Progress of one Input Multiset trial). Consider a synchronously started trial of Algorithm 11 with estimate u ≤ 2n, and suppose all agents are active at the beginning of the trial. Let f (n) = nBmax + n2 log n. If u < n, then the trial becomes invalid within O(uf (n)) rounds. If

38

u ≥ n, then no agent becomes invalid, no further reset is initiated, and all agents store the correct input multiset within O(uf (n)) rounds. Proof. By Lemma 7.1, the known-bound Input Multiset algorithm performs O(nBmax +n2 log n) = O(f (n)) flooding calls and synchronous steps. In the simulated trial, each flooding call is replaced by AdaptiveFlooding in line 11. By Lemma 6.6, each such replacement costs O(u) rounds. Hence, unless the trial is invalidated earlier, the simulated algorithm returns a candidate multiset within O(uf (n)) rounds. If the trial is invalidated earlier, then the first conclusion for u < n already holds within this time bound. Assume first that no agent invalidates before this return, and let C be the candidate returned. By Lemma 7.2, C is the correct input multiset and |C| = n. If u < n, then C is not u-valid, so the test in line 13 succeeds and the agent calls DetectError in line 14. Thus the trial is invalidated within O(uf (n)) rounds. If u ≥ n, then C is u-valid, so the test in line 13 fails and the correct candidate is stored in line 16. It remains, in the case u ≥ n, to check that no invalid propagation is created by the layer before the candidate is stored. The adaptive-flooding calls do not call DetectError in line 6, by Lemma 6.1. The invalidation channel cannot create an invalidated agent while none exists. The reset channel only reacts to an already started reset. In the control channel, the active leader starts the control signal at the beginning of each control window in line 18 of Algorithm 9; since the window length is u ≥ n, the signal reaches every agent before the missing-signal test in line 23 of Algorithm 9, by the flooding argument of Lemma 4.1. Hence no agent invalidates the trial. Since a reset can start only after the leader becomes invalid, no further reset is initiated. ◀ ▶ Theorem 7.4. StabilizingInputMultiset stabilizes to the Input Multiset function. More precisely, after some finite time, every agent outputs the correct input multiset forever. From the beginning of the execution, the stabilization time is O(n2 Bmax log n + n3 log2 n) rounds. Proof. The case n = 1 is immediate, so assume n ≥ 2. Let r = ⌈log2 n⌉ and ui = 2i . The leader starts with estimate u0 = 1 by line 2. Whenever the leader initiates a reset with estimate ui , the reset condition in line 9 of Algorithm 10 requires the reset-window value to be 2ui = ui+1 . The leader is reached by the reset it starts, and installs this value in line 23. Thus the leader’s estimates are u0 , u1 , u2 , . . .. Consider an interval in which the leader’s estimate is ui < n. If the reset that began this interval reached all agents, then all agents observe Restart synchronously by Lemma 6.5, and the new trial is synchronously started with all agents active. By Lemma 7.3, this trial is invalidated within O(ui f (n)) rounds. If the reset did not reach all agents, then some unreached agent remained invalid by line 16; in this case recovery is already active, and no progress guarantee for the simulated trial is needed. In either case, once an invalid agent exists, the non-calendar recovery work before the next reset is O(n + ui ) rounds by Lemma 6.7. Hence the non-calendar cost charged to the interval with leader estimate ui is
Hi = K ui f (n) + n + ui for a sufficiently large absolute constant K. The sequence Hi is nondecreasing and satisfies Hi = Ω(ui ), so Lemma 6.9 applies.

39

By Lemma 6.9, the total time before the first trial with leader estimate at least ur ≥ n is ! r−1 X r−1−i O Hi 2 . i=0

Since 2r−i = Θ(n/ui ), the simulation-work part contributes r−1 X

  n O ui f (n) = O(nf (n) log n), ui i=0

and the recovery terms contribute r−1 X

  n O (n + ui ) = O(n2 ). u i i=0

The first reset whose value is at least n, if any, reaches all agents by Lemma 6.5. Therefore the following trial is synchronously started with all agents active and estimate at least n. By Lemma 7.3, no further reset is initiated and all agents store the correct input multiset within an additional O(ur f (n)) = O(nf (n)) rounds. In the no-reset case, the initial estimate must already be sufficient for the Input Multiset trial: otherwise Lemma 7.3 would invalidate the trial and trigger recovery. Hence the same lemma gives stabilization in the initial trial. Combining the bounds and substituting f (n) = nBmax + n2 log n gives O(nf (n) log n + n2 ) = O(n2 Bmax log n + n3 log2 n), as claimed.

◀

▶ Corollary 7.5 (Stabilizing Counting). The same communication layer gives a stabilizing algorithm for the Counting function. From the beginning of the execution, it stabilizes in O(n3 log2 n) rounds. Proof. Counting is the special case of Input Multiset in which every agent uses the same constant input value. The final multiset then contains one value with multiplicity n, so every agent can output this multiplicity. The stabilization follows from Theorem 7.4. Since the input alphabet has constant bit length in this reduction, the O(n2 Bmax log n) term is absorbed by O(n3 log2 n). ◀

7.1

Termination with a Common Bound

Suppose that all agents are given a common bound U ≥ n. We obtain a terminating algorithm by running the stabilizing algorithm and delaying acceptance of each candidate output. When an b -valid candidate multiset C, it stores C, stops advancing the simulation, active agent obtains a U and waits for U + 1 simulation-channel rounds. If it invalidates or receives a Restart event during this waiting period, it discards C and continues with the next trial. Otherwise, when the waiting b -valid are rejected period ends, it terminates and outputs C. As before, candidates that are not U by calling DetectError. ▶ Theorem 7.6. In anonymous 1-interval-connected dynamic networks with a unique leader, given a common bound U ≥ n, the Input Multiset function can be computed with termination in O(n2 Bmax log n + n3 log2 n + U ) rounds. 40

Proof. By Theorem 7.4, within O(n2 Bmax log n + n3 log2 n) rounds all later candidates produced by the stabilizing algorithm are the correct input multiset and no further restart is generated. The next such candidate is therefore correct and is followed by a waiting period of U + 1 = O(U ) simulation-channel rounds, hence O(U ) ordinary rounds. It remains only to rule out termination with an earlier incorrect candidate. If some agent has already invalidated when such a candidate is stored, then during the U + 1 simulation-channel waiting period at least U ≥ n invalidation-channel rounds occur. Hence the invalidation reaches the agent before the waiting period can finish, unless a reset completion reaches it first; in either case the candidate is discarded. If no agent has become invalid when the candidate is stored, then the trial was synchronously started and Lemma 7.2 implies that the candidate is correct. Thus no incorrect candidate can be accepted, and the stated bound follows. ◀ ▶ Corollary 7.7. In anonymous 1-interval-connected dynamic networks with a unique leader, given a common bound U ≥ n, the Counting function can be computed with termination in O(n3 log2 n + U ) rounds.

8

Related Work

We survey work on anonymous networks and on communication models close to the one-bit model studied in this paper. Anonymous networks. The study of computability in anonymous static networks goes back to Angluin [2] and has developed into a broad line of work [4, 11, 12, 24, 34, 35]. The main obstacle introduced by anonymity is symmetry: agents with the same view of the network cannot be distinguished by a deterministic algorithm. For instance, in an anonymous static ring, all agents have the same view, and this view does not by itself distinguish rings of different sizes. Hence non-trivial tasks such as counting require additional information or a symmetry-breaking assumption, such as the presence of a leader. Several works provide structural characterizations of computability in anonymous networks. Yamashita and Kameda characterized the tasks solvable in anonymous networks of known size through the combinatorial notion of views [35]. Boldi and Vigna gave a characterization of computability and stabilization using graph fibrations and coverings [4]. The above techniques only work on static networks and use messages of size at least log(n). Anonymous dynamic networks. The problem of counting and computing in anonymous dynamic networks has been studied in several papers [31, 27, 28] that have given polynomial algorithms for counting and related problems. For anonymous 1-interval-connected dynamic networks, Di Luna and Viglietta, introducing the history-tree technique, showed that every computable function, including the one studied in our paper, can be computed in linear time in the presence of a leader [20]. Subsequent work extended their history-tree approach to the leaderless and multi-leader setting [21], to finite-state and self-stabilizing computation [22], and to congested networks [23]. These history-tree algorithms rely on agents transmitting at least parts of their vistas. In the congested model, where messages have O(log n) bits, this yields an O(n3 )-round algorithm for computing Input Multiset when a leader is present [23]. Our paper studies the stricter setting 41

in which each agent broadcasts only a single bit per round; the history-tree approach used in the previous algorithms therefore does not directly apply. Beeping networks. The beeping model was introduced as a very weak radio communication model by Cornejo and Kuhn [15] and, to our knowledge, all works have examined static networks. Metivier, Robson, and Zemmari then studied the algorithmic power of several beeping variants, including collision-detection emulations and local graph problems [30]. For counting, Casteigts, Metivier, Robson, and Zemmari considered one-hop beeping networks [6]. In the beeping model, exact deterministic counting cannot be done, and the impossibility even holds for Las Vegas algorithms; with sender-side collision detection, they give an O(n) randomized algorithm with high probability. Brandes, Kardas, Klonowski, Pajak, and Wattenhofer studied randomized size approximation in one-hop beeping networks and obtained time-optimal approximation bounds [5]. These results concern one-hop networks and are randomized, while our results are deterministic in multi-hop dynamic networks. Regarding multi-hop static networks, Czumaj and Davies developed deterministic beeping algorithms for static global communication tasks including broadcast, gossiping, and multi-broadcast [16, 17], and Beauquier, Burman, Davies, and Dufoulon later obtained uniform time-optimal deterministic multi-broadcast via group testing [3]. Davies obtained an O(∆ log n)-round simulation of one Broadcast-CONGEST round and an O(∆2 log n)-round simulation of one CONGEST round in the noisy beeping model [18]. These works use techniques that rely on fixed neighborhoods, identifiers, or degree/diameter structure, and therefore do not directly transfer to anonymous 1-interval-connected dynamic networks. Relationship between our model and beeping networks. The communication model studied in this paper is closely related to beeping models. In both settings, each agent chooses between two possible actions in each round: in beeping models these actions are usually called beep and silence or listen, while in our model they are denoted by 1 and 0. The basic beeping model is half-duplex. An agent that emits a signal receives no information in that round, while an agent that remains silent only learns whether at least one neighbor emitted a signal. Thus the feedback is both asymmetric and boolean: it distinguishes zero from nonzero, but does not provide multiplicities. In counting full-duplex variants of beeping an agent learns, in every round, how many of its neighbors emitted a signal. However, this is still weaker than our model, since it does not learn how many neighbors remained silent. If, in addition, the agent can observe its degree after choosing its action, then it can recover the number of silent neighbors. This gives exactly the same information as in the broadcast-counting model. Consequently, the algorithms presented in this paper also apply to the corresponding counting beeping models under these additional assumptions. Content-oblivious model. The content-oblivious (CO) model was introduced by Censor-Hillel, Cohen, Gelles, and Sela. In this model agents communicate over an asynchronous network by exchanging pulses [7]. A pulse carries no content, not even the identity of the sender, so an agent can only use the number of pulses received on each local port. From this perspective a pulse is weaker than a message carrying a single bit. To the best of our knowledge, all work on this model has examined static networks [7, 25, 9, 8, 13, 10].

42

Censor-Hillel et al. showed that, in the presence of a leader, CO communication can simulate asynchronous message passing on 2-edge-connected networks [7]. Subsequent work removed or weakened the leader requirement in several settings: Frei, Gelles, Ghazy, and Nolin gave a leaderelection algorithm for oriented rings [25]; Chalopin, Chang, Chen, Di Luna, and Zhou gave a non-uniform leader-election algorithm on unoriented rings and a leader-election algorithm in uniform 2-edge-connected networks [9, 8]; while Chang, Chen, and Zhou studied what remains possible beyond 2-edge-connectivity [13]. Closest to our counting problem, Chalopin, Chang, Di Luna, and Zhou study counting and simulation in content-oblivious rings [10]. They give an O(n3/2 )-pulse counting algorithm for anonymous rings with a leader, an O(n log2 n)-pulse algorithm for rings with identifiers, and an Ω(n log n) lower bound for counting in the CO model. They also give a simulator for asynchronous message passing on general 2-edge-connected networks with constant pulse overhead per transmitted bit after preprocessing. The result on counting in an anonymous ring with a leader is close in spirit to ours, but the models are different: their algorithm is asynchronous and ring-based, and agents can send a message over a single link, while our algorithms are synchronous, broadcastbased, and work in arbitrary 1-interval-connected dynamic networks. The dynamic topology and broadcast communication of our setting do not allow the transfer of the content-oblivious algorithmic techniques.

References [1] Ny Aina Andriambolamalala and Vlady Ravelomanana. Energy-Efficient Naming in Beeping Networks, 2021. URL: https://arxiv.org/abs/2106.03753, arXiv:2106.03753. [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] Joffroy Beauquier, Janna Burman, Peter Davies, and Fabien Dufoulon. Optimal Multi-broadcast with Beeps Using Group Testing. In Structural Information and Communication Complexity (SIROCCO 2019), volume 11639 of Lecture Notes in Computer Science, pages 66–80. Springer, 2019. doi:10.1007/978-3-030-24922-9_5. [4] Paolo Boldi and Sebastiano Vigna. An Effective Characterization of Computability in Anonymous Networks. In Distributed Computing, volume 2180 of Lecture Notes in Computer Science, pages 33–47. Springer, 2001. doi:10.1007/3-540-45414-4_3. [5] Philipp Brandes, Marcin Kardas, Marek Klonowski, Dominik Pajak, and Roger Wattenhofer. Fast Size Approximation of a Radio Network in Beeping Model. Theoretical Computer Science, 810:15–25, 2020. doi:10.1016/j.tcs.2017.05.022. [6] Arnaud Casteigts, Yves Métivier, John Michael Robson, and Akka Zemmari. Counting in One-Hop Beeping Networks. Theoretical Computer Science, 780:20–28, 2019. doi:10.1016/j. tcs.2019.02.009. [7] Keren Censor-Hillel, Shir Cohen, Ran Gelles, and Gal Sela. Distributed Computations in Fully-Defective Networks. Distributed Computing, 36(4):501–528, 2023. doi:10.1007/ s00446-023-00452-2. 43

[8] Jérémie Chalopin, Yi-Jun Chang, Lyuting Chen, Giuseppe A. Di Luna, and Haoran Zhou. Content-Oblivious Leader Election in 2-Edge-Connected Networks, 2025. URL: https://arxiv. org/abs/2507.08348, arXiv:2507.08348. [9] Jérémie Chalopin, Yi-Jun Chang, Lyuting Chen, Giuseppe A. Di Luna, and Haoran Zhou. Non-Uniform Content-Oblivious Leader Election on Oriented Asynchronous Rings, 2025. URL: https://arxiv.org/abs/2509.19187, arXiv:2509.19187. [10] Jérémie Chalopin, Yi-Jun Chang, Giuseppe A. Di Luna, and Haoran Zhou. Efficient Counting and Simulation in Content-Oblivious Rings. To appear in Proceedings of the 45th ACM Symposium on Principles of Distributed Computing (PODC 2026). ACM, 2026. URL: https: //arxiv.org/abs/2603.28260, arXiv:2603.28260. [11] Jérémie Chalopin, Emmanuel Godard, and Yves Métivier. Local Terminations and Distributed Computability in Anonymous Networks. In Distributed Computing, volume 5218 of Lecture Notes in Computer Science, pages 47–62. Springer, 2008. doi:10.1007/978-3-540-87779-0_4. [12] Jérémie Chalopin, Yves Métivier, and Thomas Morsellino. Enumeration and Leader Election in Partially Anonymous and Multi-hop Broadcast Networks. Fundamenta Informaticae, 120(1):1– 27, 2012. doi:10.3233/FI-2012-747. [13] Yi-Jun Chang, Lyuting Chen, and Haoran Zhou. Beyond 2-Edge-Connectivity: Algorithms and Impossibility for Content-Oblivious Leader Election, 2025. URL: https://arxiv.org/abs/ 2511.23297, arXiv:2511.23297. [14] Bogdan S. Chlebus, Gianluca De Marco, and Muhammed Talo. Naming a Channel with Beeps. Fundamenta Informaticae, 153(3):199–219, 2017. doi:10.3233/FI-2017-1537. [15] Alejandro Cornejo and Fabian Kuhn. Deploying Wireless Networks with Beeps. In Distributed Computing, volume 6343 of Lecture Notes in Computer Science, pages 148–162. Springer, 2010. URL: https://arxiv.org/abs/1005.2567. [16] Artur Czumaj and Peter Davies. Communicating with Beeps. In 19th International Conference on Principles of Distributed Systems (OPODIS 2015), volume 46 of LIPIcs, pages 30:1–30:16. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2016. doi:10.4230/LIPIcs.OPODIS.2015. 30. [17] Artur Czumaj and Peter Davies. Communicating with Beeps. Journal of Parallel and Distributed Computing, 130:98–109, 2019. doi:10.1016/j.jpdc.2019.03.020. [18] Peter Davies-Peck. Optimal Message-Passing with Noisy Beeps. Distributed Computing, 38(3):247–260, 2025. doi:10.1007/s00446-025-00488-6. [19] Giuseppe A. Di Luna, Roberto Baldoni, Silvia Bonomi, and Ioannis Chatzigiannakis. Counting in Anonymous Dynamic Networks under Worst-Case Adversary. In 2014 IEEE 34th International Conference on Distributed Computing Systems (ICDCS 2014), pages 338–347. IEEE, 2014. doi:10.1109/ICDCS.2014.42. [20] Giuseppe A. Di Luna and Giovanni Viglietta. Computing in Anonymous Dynamic Networks Is Linear. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS 2022), pages 1122–1133. IEEE, 2022. doi:10.1109/FOCS54457.2022.00108. 44

[21] Giuseppe A. Di Luna and Giovanni Viglietta. Optimal Computation in Leaderless and MultiLeader Disconnected Anonymous Dynamic Networks. In 37th International Symposium on Distributed Computing (DISC 2023), volume 281 of LIPIcs, pages 18:1–18:20. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2023. doi:10.4230/LIPIcs.DISC.2023.18. [22] Giuseppe A. Di Luna and Giovanni Viglietta. Universal Finite-State and Self-Stabilizing Computation in Anonymous Dynamic Networks. In 28th International Conference on Principles of Distributed Systems (OPODIS 2024), volume 324 of LIPIcs, pages 10:1–10:17. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024. doi:10.4230/LIPIcs.OPODIS.2024.10. [23] Giuseppe A. Di Luna and Giovanni Viglietta. Efficient Computation in Congested Anonymous Dynamic Networks. Distributed Computing, 38(2):95–112, 2025. URL: https://arxiv.org/ abs/2301.07849. [24] Pierre Fraigniaud, Andrzej Pelc, David Peleg, and Stéphane Pérennes. Assigning Labels in Unknown Anonymous Networks (Extended Abstract). In Proceedings of the 19th Annual ACM Symposium on Principles of Distributed Computing (PODC 2000), pages 101–111. ACM, 2000. doi:10.1145/343477.343527. [25] Fabian Frei, Ran Gelles, Ahmed Ghazy, and Alexandre Nolin. Content-Oblivious Leader Election on Rings. In 38th International Symposium on Distributed Computing (DISC 2024), volume 319 of LIPIcs, pages 26:1–26:20. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024. doi:10.4230/LIPIcs.DISC.2024.26. [26] Pawel Garncarek, Dariusz R. Kowalski, Shay Kutten, and Miguel A. Mosteiro. Beeping Deterministic CONGEST Algorithms in Graphs. In 33rd Annual European Symposium on Algorithms (ESA 2025), volume 351 of LIPIcs, pages 20:1–20:17. Schloss Dagstuhl – LeibnizZentrum für Informatik, 2025. doi:10.4230/LIPIcs.ESA.2025.20. [27] Dariusz R. Kowalski and Miguel A. Mosteiro. Polynomial Counting in Anonymous Dynamic Networks with Applications to Anonymous Dynamic Algebraic Computations. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), volume 107 of LIPIcs, pages 156:1–156:14. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2018. doi:10.4230/LIPIcs.ICALP.2018.156. [28] 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. [29] Nancy A. Lynch. Distributed Algorithms. Morgan Kaufmann Publishers, San Francisco, CA, 1996. [30] Yves Métivier, John Michael Robson, and Akka Zemmari. On Distributed Computing with Beeps, 2015. URL: https://arxiv.org/abs/1507.02721, arXiv:1507.02721. [31] Othon Michail, Ioannis Chatzigiannakis, and Paul G. Spirakis. Naming and Counting in Anonymous Unknown Dynamic Networks. In Stabilization, Safety, and Security of Distributed Systems, volume 8255 of Lecture Notes in Computer Science, pages 281–295. Springer, 2013. doi:10.1007/978-3-319-03089-0_20.

45

[32] Alex Olshevsky. Linear Time Average Consensus and Distributed Optimization on Fixed Graphs. SIAM Journal on Control and Optimization, 55(6):3990–4014, 2017. [33] Giovanni Viglietta. History Trees and Their Applications. In 31st International Colloquium on Structural Information and Communication Complexity (SIROCCO 2024), volume 14662 of LNCS, pages 3–23, 2024. URL: https://arxiv.org/abs/2404.02673, arXiv:2404.02673. [34] Masafumi Yamashita and Tsunehiko Kameda. Computing on an Anonymous Network. In Proceedings of the 7th Annual ACM Symposium on Principles of Distributed Computing (PODC 1988), pages 117–130. ACM, 1988. [35] Masafumi Yamashita and Tsunehiko Kameda. Computing on Anonymous Networks. I. Characterizing the Solvable Cases. IEEE Transactions on Parallel and Distributed Systems, 7(1):69–89, 1996. doi:10.1109/71.481599.

46