arXiv CS open access

Counting in Population Protocols on Graphs

2026 · arxiv_cs

arXiv CS · Papers · 2026

cloud distributed-computing parallel-computing

Conceptio Open Archive

Analyze & explore related research in Conceptio

Connect this record directly into your research workflow or AI agent. Explore citations across open repositories, query full text, and export structured proof bundles.

Explore in Search →Connect via MCP / API ↗

Counting in Population Protocols on Graphs Petra Berenbrink # University of Hamburg, Germany

Robert Elsässer # University of Salzburg, Austria

Tom Friedetzky # Durham University, U.K.

Thorsten Götte # University of Hamburg, Germany

Lukas Hintze #

arXiv:2608.17590v1 [cs.DC] 18 Aug 2026

University of Hamburg, Germany

Dominik Kaaser # Hamburg University of Technology, Germany

Abstract We consider the problem of counting the number of agents in a population protocol where the agents are connected by an underlying graph G = (V, E) with |V | = n nodes. In each step, a random scheduler selects an edge uniformly at random, and the incident nodes make a state transition. As per standard assumptions, agents are identical and anonymous, that is, have no identifiers. To break symmetry, in each interaction one of the agents is declared as the initiator uniformly at random. e (n) states and stabilizes in O(B(G) · log2 (n) + L(G) · log(n)) Our size counting protocol uses O interactions with high probability, where B(G) is the broadcast time and L(G) is the load balancing time. Our protocol is based on novel protocols for sampling independent random bits (given that the scheduler determines an initiator and responder) and approximating log n up to an additive error of O(log log n) with high probability. The latter uses O(polylog(n)) states and O(B(G) · log2 n) interactions. Both results may be of independent interest. The main protocol for exact counting requires the presence of a unique leader, the other two do not. None of the protocols requires any knowledge about the graph G. We conclude with impossibility results for terminating uniform population protocols that compute graph-size properties (like counting nodes or determining parity) with and without a leader.

Counting in Population Protocols on Graphs

Contents 1 Introduction

1.1

Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.2

Background and Related Work . . . . . . . . . . . . . . . . . . . . . . . . . .

2 Results 2.1 Approximate Counting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

8 8

2.2

Counting the Exact Population Size . . . . . . . . . . . . . . . . . . . . . . . 10

2.3

Impossibility Result . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

2.4

Generating Independent Random Bits . . . . . . . . . . . . . . . . . . . . . . 15

2.5

Summary and Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

3 Approximate Counting

3.1

Formal Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

3.2

Proof of the Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

4 Counting the Exact Population Size

4.1

Formal Description of our Protocol . . . . . . . . . . . . . . . . . . . . . . . . 23

4.2

Proof of the Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

4.3

Balancing Blue Tokens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

4.4

Eliminating Red Tokens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

4.5

Balancing Red Tokens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

5 Impossibility of Termination

6 Generating Independent Random Bits

6.1

Bits are Uniform . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

6.2

Bits are Independent . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

6.3

Bits are Sampled Frequently . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

7 Baseline: Space-Efficient Uniform Counting

7.1 Analysis of UniformCounting . . . . . . . . . . . . . . . . . . . . . . . . . 46 8 Tools from Probability Theory

P. Berenbrink, R. Elsässer, T. Friedetzky, T. Götte, L. Hintze, and D. Kaaser

Introduction

The population protocol model [5] is one of the most basic and fundamental models of distributed computing. Angluin, Aspnes, Diamadi, Fischer, and Peralta [5] provide a comprehensive collection of examples that illustrate applications. Population protocols are closely related to chemical reaction networks [31], and they model processes occurring naturally in life sciences [13, 15, 28]. In classical population protocols, each agent is in one out of a fixed number of states. A probabilistic scheduler selects in each step a pair of agents independently and uniformly at random. One of the agents is called initiator and the other one the responder. These agents perform a state transition that depends only on their states. In our paper, we assume that interactions are restricted to edges of an underlying graph G = (V, E), where V is the set of agents. We assume that in each step the scheduler randomly chooses one edge and determines randomly which of the endpoints acts as the initiator and which one as the responder. Agents are anonymous and have neither identifiers nor knowledge of G. A large body of recent work (e.g., [1, 2, 4, 9, 10, 20, 30]) proposes so-called non-uniform protocols where the transition rules depend on the number of agents. In biologicallyinspired applications, however, this knowledge may not be available, and even polynomial approximations may not be feasible. In this context, size counting protocols [12, 17, 18, 19, 23] can be used to count the number of agents before running a non-uniform protocol. However, all the protocols in these papers assume that the underlying interaction graph is the complete graph. Our main result is a novel population protocol to count the number of agents of the underlying (arbitrary) graph. Its time complexity depends on bounds for standard broadcasting and load balancing on the underlying graph. Its state complexity is asymptotically nearly e optimal at Θ(n) with high probability (w.h.p., with probability at least 1 − n−Ω(1) ). The protocol is graph-uniform, i.e., neither its state space nor its transition function depend on G (and thus it does not depend on n either). Informally, this means that the protocol works as advertised (from the initial configuration) without agents having to know anything about the graph. The only hard requirement is the presence of a leader. The high-level strategy is to first approximate log n to within a factor of 1 ± o(1) w.h.p. using polylogarithmically many states. This part does not yet require the leader, and we e 2 ) tokens across believe this subroutine to be of independent interest. Then we distribute Θ(n the network and repeatedly balance that load until the system naturally converges to a configuration where the loads of different agents differ by at most an additive constant. From this, agents can directly output the exact value of n. This technique was already used for exact counting in complete graphs (see [12, 21]) and crucially requires Ω(n2 ) tokens to be balanced. Our main technical contribution lies in our space-efficient implementation of the balancing: a naïve protocol would start with Ω(n2 ) tokens located at the leader, and in each step two interacting agents would balance their loads. This approach requires Ω(n2 ) states to store the number of tokens. To save states, we instead employ two types of tokens: red and blue. The leader starts with Θ(n) red tokens that are balanced (in a certain way). Whenever an agent holds exactly one red token, it converts it into Θ(n) blue tokens. These blue tokens are then balanced using the naïve approach and are used to compute n. As we ensure that each red token is (eventually) converted, the total number of blue tokens is (eventually) Ω(n2 ) and thus large enough. The crux of our protocol is the space-efficient balancing of red tokens: Our protocol ensures that the number of red tokens on each agent is always a

Counting in Population Protocols on Graphs

power of two, so this number can be encoded using only O(log n) states instead of n states. This, however, entails that two agents holding red tokens cannot necessarily balance them. The main difficulty in the analysis is overcoming the subtle dependencies between red tokens caused by our balancing protocol and showing that they indeed balance quickly. The stabilization times of our protocols depend heavily on properties of the underlying graphs. The “native” representation of our results is in terms of the broadcast time B(G) and the load balancing time L(G) of the underlying graph. The former is the expected time it takes to send a message from an arbitrary node to every other node, assuming that in each step the message can be sent over a randomly chosen edge of G. The latter is the time it takes to balance a polynomial number of arbitrarily distributed discrete tokens until every node has (almost) the same load. In detail, our contributions are as follows. 1. An auxiliary protocol that estimates log(n) up to an additive error of log log(n) in O(B(G) · log2 n) interactions using O(log4 (n)) states w.h.p. This protocol does not need any knowledge of the graph nor does it require a leader. 2. Another auxiliary protocol for generating fair and independent random bits for population protocols on graphs. This protocol also does not need any knowledge of the graph nor does it require a leader. Instead, the protocol relies on the random initiator and responder choices by the scheduler. 3. As our main result, we present a protocol that counts the exact population size in e O(B(G) · log2 n + L(G) · log(n)) interactions using O(n) states w.h.p. By counting we mean that the population stabilizes to a configuration where each agent can derive the exact number of agents n from its state. Our protocol requires a leader, but does not use any information on the underlying graph. In particular, neither B(G) nor L(G) are known or used by the protocol. 4. We prove that certain graph properties (e.g., size or parity) cannot reliably be computed by terminating population protocols, regardless of whether a leader is present or not. In particular, this means that the fact that our exact counting protocol only stabilizes (and does not detect termination) is inevitable.

1.1

Model

We consider a fixed undirected graph G = (V, E) with |V | = n agents and m edges. We define ∆(G), δ(G) and d(G) as G’s maximum, minimum, and average node degree, respectively. The state space of the agents is called Q and each agent is initially in state q0 ∈ Q. An output function ρ : Q → Σ∗ maps states to an output domain. The computation proceeds in discrete steps t = 1, 2, . . . In each step t, a stochastic scheduler picks an edge (u, v) independently and uniformly at random with probability 1/(|E|) and then decides which of the nodes is the initiator and which one the responder. Note that this can be regarded as picking a directed edge. u and v observe each other’s states and update their states according to a transition function Π : Q × Q → Q × Q. We call a population protocol (graph-)uniform if neither its transition function Π nor the output function ρ depend on (any parameters of) the underlying graph G. The size of the total state space Q of our protocols may be viewed as unbounded (and must be for counting). When we say that a protocol uses O(f (n)) states w.h.p., we mean that there are state subsets Q1 ⊆ Q2 ⊆ . . . ⊆ Q with |Qn | = O(f (n)) so that when the protocol is run on a graph of size n, all states used are in Qn w.h.p. Alternatively, one could define all this in terms of the agents being multi-tape Turing machines, see [19].

P. Berenbrink, R. Elsässer, T. Friedetzky, T. Götte, L. Hintze, and D. Kaaser

Table 1 B(G), L(G), and H(G) for certain graph classes. Note that B(G) and L(G) are properties of population protocols on graphs while H(G) only depends on the graph. Note that (1 − λ(P(G))) denotes the spectral gap. Graph Class

B(G)

L(G)

H(G)

Clique Regular graphs

O(n log n) n O(( 1−λ(P(G)) ) log n)

O(n) O( √

Cycle d-dim. Torus (d = 2) d-dim. Torus (d > 2) Worst Case

O(n2 log n) O(n3/2 log n) O(n · d · n1/d · log n) O(n3 )

O(n3 log n) O(n2 log n) O(n · d · n2/d · log n) O(n4 log n)

O(n ) O(n log n) O(n) O(n3 )

n ) 1−λ(P(G)) 2

A configuration of the population protocol assigns each node a state. We call a configuration C stable if no sequence of interactions exists that can change the future output ρ(C(u)) of any agent u. The time complexity is measured by the so-called stabilization time, which is the total number of interactions needed to reach a stable configuration. In our results, we quantify the stabilization time in terms of the broadcast time and the load balancing time L(G). Let T (v) be a random variable for the number of steps a broadcast (also called one-way epidemics [6]) started at node v needs to inform the entire graph. We use the same definition as Alistarh, Rybicki, and Voitovych [4] and define B(G) = maxv {E[T (v)]} to be the worst-case (over v) expected broadcast time on G. Alistarh, Rybicki, and Voitovych [4] prove that B(G) is the minimum of O(mD + m log n) and O(m/β · log n) for any graph with diameter D and edge expansion β. Since m ≤ n2 and D, β −1 ≤ n we have B(G) ∈ O(n3 ) for any connected graph G. However, B(G) can be as small as O(n log n), e.g., on a regular expander. To define the load balancing time we first need some additional definitions. Let P = P(G) be the matrix given by Pu,v = 1/(2∆(G)) if {u, v} ∈ E(G), Pu,v = 1 − deg(u)/(2∆(G)) if u = v, and Pu,v = 0 otherwise. Let λ1 (P) ≥ λ2 (P) ≥ · · · ≥ λn (P) be the n eigenvalues of P, and define λ(P) = max{|λ2 (P)|, |λn (P)|}. Then, by [8], it holds that d(G) 1 L(G) = O n log(n) · · . ∆(G) 1 − λ(P(G)) As the spectral gap (1 − λ(P(G))) is bounded by Ω(n−3 ) we have L(G) ∈ O(n4 log n) for any connected graph G. However, L(G) can be as small as O(n log n), e.g., on a regular expander. Finally, we require the notion of a graph’s hitting time. For a graph G = (V, E) and nodes u, v ∈ V , the hitting time H(u, v) from u to v is the expected time it takes a simple random walk on G, started at u, to visit v for the first time. The hitting time H(G) of G is then the maximal hitting time over all pairs u, v ∈ V . It is known that the hitting time of any simple connected graph G is at most O(n3 ) [27]. We give some known upper bounds for B(G), L(G), and H(G) for some important graph classes in Table 1.

1.2

Background and Related Work

General Results for Population Protocols on Graphs. Alistarh, Gelashvili, and Rybicki [3] show how to simulate an arbitrary population protocol on a graph in the standard model (using a complete graph as the underlying graph). The simulation overhead is polylogarithmic in the number of nodes, and quadratic in the conductance of the graph. The authors assume

Counting in Population Protocols on Graphs

Table 2 An overview of leader election algorithms for population protocols on graphs. Result [4, Theorem 3] [4, Theorem 4] [4, Theorem 5]

Runtime O(H(G) · n log n) O(B(G) + n log n) O(2h log n)

Runtime(WC) 4

O(n log n) O(n3 ) O(n3 log n)

States

Comment

O(1) O(n4 ) O(h · log n)

uniform, based on [7]. uniform. h known, 2h ≥ B(G)

that a bound on the conductance is known in advance. Chen and Chen [14] present two selfstabilizing leader election protocols for k-regular graphs. The state complexity is polynomial in k and they do not provide any bounds on the convergence time. Beauquier, Blanchard, and Burman [7] present a constant state leader election protocol for general graphs. With the help of an oracle, this protocol can be made self-stabilizing. They focus on necessary conditions for self-stabilization and do not bound the convergence time. Alistarh, Rybicki, and Voitovych [4] consider leader election in population protocols on graphs. They present several upper and lower bounds for the problem. For a graph G they express their results in terms of the broadcast time B(G) as defined before. They present a space-efficient protocol using O(log n · h(G)) states where h(G) ∈ O(log n) is a parameter depending on the broadcast time. The expected convergence time is O(B(G) · log n). In that paper they also present a phase clock using h + 1 states that triggers a clock tick every Θ(2h ) interactions. We give an overview of leader election protocols in Table 2. Rybicki, Solnerzik, Stietel, and Vacus [30] give upper and lower bounds on the majority problem in population protocols on graphs. The upper bounds are expressed by the inverse of the spectral gap of the Markov chain induced by the random scheduler on G and the degree imbalance (defined as maximum divided by the minimum degree). For expander graphs their result matches the best result for complete graphs by Doty, Eftekhari, Gasieniec, Severson, Uznanski, and Stachowiak [20]. Their result depends on an efficient phase clock implementation for graphs. For their phase clock they need graph parameters like the size of the graph or its relaxation time. There are many results for the generation of random bits, approximate counting and counting in the standard population model where the nodes are connected by a complete graph. In the following, we present results for this classical model. Approximate Counting. One well-known way to approximate log n is to consider n geometrically distributed random variables X1 , . . . , Xn with parameter 1/2. Their maximum max{X1 , . . . , Xn } then approximates log n to within a constant factor. This approach is easily realized by a population protocol [1]. Doty and Eftekhari [19] improve this result by repeating the experiment O(log n) times. Taking the average of O(log n) maxima then results in an approximation of log(n) ± 5.7. Their algorithm requires O(n log2 n) interactions and O(log4 (n)) states. However, to obtain a polylogarithmic state space size, their algorithm relies on phase clocks to synchronize the agents. This requires the interaction frequencies of different agents to be the same (up to a multiplicative constant), and therefore is not directly transferable to population protocols on graphs. Berenbrink, Kaaser, and Radzik [12] present an approximate counting protocol that computes ⌊log n⌋ or ⌈log n⌉. Their protocol first elects a leader. The leader starts with one token. In alternating phases, the tokens are doubled and balanced using load balancing. The first time there exists a node with two tokens after a balancing phase, the number of doubling steps is used as an approximation of log n. In a similar setting, Kowalski and

P. Berenbrink, R. Elsässer, T. Friedetzky, T. Götte, L. Hintze, and D. Kaaser

Mosteiro [26] use load balancing for counting in the dynamic networks model. Note that the dynamic network model is inherently synchronized, while the protocol from [12] relies heavily on synchronizing the agents via the phase clock from [6]. Doty and Eftekhari [18] and Kaaser and Lohmann [23] use geometrically distributed random variables to approximate log n in a dynamic variant of population protocols where agents arrive and depart during the execution. Doty and Eftekhari [18] use the first missing value of geometrically distributed random variables to approximate log n. Given n geometrically distributed random variables X1 , . . . , Xn , the first missing value is defined as the smallest integer i ∈ / {X1 , . . . , Xn } (cf. [22, 29]). W.h.p., the first missing value is in Θ(log n) [18]. While we follow a similar approach in our work, the bounds on the first missing value are not tight enough for our purposes (see the proof of Lemma 5.5 in the full version of [18]). Instead, we resort to a more fine-grained partitioning of the agents before we detect the first missing value. Our approach gives us an approximation in [log n − 2 log log n, log n − log log n] (see Section 2.1). Exact Counting. On general graphs, counting can be achieved with mass-carrying coalescing random walks: Each agent starts with one token. Whenever two agents holding tokens interact, one of them sends all its tokens to the other. Eventually, there will be one agent holding all n tokens left. This trivial solution to exact counting on the complete graph requires O(n) states and converges in O(n2 ) interactions [12]. On an arbitrary graph the running time is equal to the coalescence time (cf. [24]), which is at most O(H(G) · n · log n). For completeness, we give the corresponding algorithm and a sketch of the analysis in Section 7. Doty, Eftekhari, Michail, Spirakis, and Theofilatos [21] count the exact number of agents without any prior size estimate. Their protocol converges in O(n log n log log n) interactions w.h.p. and in expectation, using n60 states per agent. Berenbrink, Kaaser, and Radzik [12] e present a protocol that computes n in optimal O(log n) time using O(n) states. As their protocol for approximating n, the exact size counting protocol first elects a leader and then synchronizes phases via phase clocks. Hence, it cannot be applied in population protocols on graphs. For further details on (exact) size counting protocols, we refer to the survey of size counting in population protocols by Doty and Eftekhari [17]. A natural question is whether known fast protocols for the complete graph, perhaps after some mild modifications (cf. [3]), can be applied directly on graphs. Unfortunately, all currently known fast protocols for complete graphs rely on synchronization via so-called phase clocks [6], and these phase clocks require network parameters such as the number of edges and the maximum degree. To the best of our knowledge, all known phase clock implementations on graphs [3, 4, 30] require prior knowledge of graph parameters: The clock from [4] is driven by high-degree nodes of the graph, and its parameters must be adjusted based on the number of edges m = |E| and the maximum degree ∆. The clock from [30] requires prior knowledge of the spectral gap induced by the scheduler (1 − λ) and the minimum and maximum degrees. The clock from [3] is defined for d-regular graphs only, and both the degree d and the expansion β must be known. In contrast, our counting protocol can be applied without any knowledge of graph parameters: without resorting to synchronization, our protocol converges to the correct output in a time that depends on spectral properties of the graph. Random Bits. The problem of generating random bits has received significant attention in both classical population protocols and population protocols on graphs. On the complete graph, generating independent random bits is seemingly simple. Each node is equipped

Counting in Population Protocols on Graphs

with a so-called flip bit which is flipped in each interaction. The initiator then uses the flip bit of the responder as a random bit p [1, 11]. This provides w.h.p. nearly random bits after some initialization time n/2 ± O( log(n)/n). Sudo, Ooshita, Izumi, Kakugawa, and Masuzawa [32] provide a simple protocol that ensures that the number of agents with flip bit 1 equals exactly the number of agents with flip bit 0. Note that this approach applied on graphs requires that roughly half of each agent’s neighbors have a flip bit 0 and the remaining ones hold 1, which is not the case for low-degree graphs. In population protocols on graphs the required randomness is, to our best knowledge, always derived from the initiator-responder pattern (see [4]). That is, in an interaction, the initiator samples bit 1 and the responder samples bit 0. Since a node is the initiator or responder with equal probability, nodes always sample fair coins. However, the coins produced by this approach are highly correlated as the coins of interacting nodes are always different. Thus, the bits created by this protocol are fair but not independent. Kanaya, Eguchi, Sasada, and Inoue [25] present a protocol to sample bits based on a static coloring of the graph. They begin by computing a coloring (for this they need an upper bound on n or on the maximal degree). In each subsequent interaction only the agent with the higher-ranked color obtains a random bit depending on its role (initiator/responder). The other agent does not sample a bit. This ensures independence of the sampled bits but means that there will be agents that cannot sample any bits as their color is a local minimum.

Results

In this section, we give an overview of our results, including descriptions of algorithms and sketches of the associated proofs. We begin with our two main results for approximate and exact counting in Section 2.1 and Section 2.2. In Section 2.3 we show that there can be no terminating protocol for counting that is correct with probability 1. Finally, in Section 2.4 we present an auxiliary protocol to sample independent, unbiased bits. The full proofs are given in subsequent sections.

2.1

Approximate Counting

Doty and Eftekhari [18] use the first missing value of n geometrically distributed random variables with parameter 1/2 to approximate log n. To improve their estimate of log n we consider n tuples of random variables (Li , Gi ) as follows. The random variables Li have a geometric distribution with parameter 1/2. The random variables Gi have a uniform distribution over 1, 2, . . . , 2⌈log Li ⌉ . We say that the random variable Li determines a level, and the random variable Gi determines a group within that level. Now we order our tuples lexicographically and calculate the first missing tuple, which we call (ML , MG ) in the following. We show that ML is a tight approximation of log n; it only has an additive error of log log n + O(1) w.h.p. (see Lemma 9 for the detailed statement). The idea of this approach is as follows. The random variable Li is geometrically distributed, hence the number of variables with a value of k is roughly n/2k . For all random variables Li with Li = L (belonging to level L) we draw a coupon from the range 1, 2, . . . 2⌈log L⌉ . We output the smallest level L for which we could not collect all 2⌈log L⌉ coupons of that level. The protocol for sampling Li and Gi is straightforward and can be found in Section 3.1. Note that we use the subprotocol GenerateRandomBit to generate the random bits for both the geometric and the uniform distribution. We explain the details of this protocol in Section 2.4.

P. Berenbrink, R. Elsässer, T. Friedetzky, T. Götte, L. Hintze, and D. Kaaser

Our protocol Approximate uses the idea presented above. In our protocol node u computes levelu with a geometric distribution (role of Li ) and groupu with a uniform distribution (role of Gi ). Before we describe protocol Approximate to compute the first missing tuple we need one more definition: succlex (bcLevel, bcGroup) returns the successor of the tuple (bcLevel, bcGroup) in lexicographical order. The protocol is applied by agent u as soon as levelu and groupu are calculated. In the protocol Approximate, node u has two more fields bcLevelu and bcGroupu (bc stands for broadcast) which are initialized to 1 and 0, respectively. Whenever node u has (levelu , groupu ) = (bcLevelu , bcGroupu ), node u knows for sure that the tuple (bcLevelu , bcGroupu ) is not missing and thus sets (bcLevelu , bcGroupu ) to the successor according to the lexicographical order. This process continues as long as all tuples are present. Crucially, for the first missing tuple, no further increase is possible, and the protocol stabilizes. Protocol 1 Approximate(u, v) 1

2 3

w.l.o.g. let (bcLevelu , bcGroupu ) ≥lex (bcLevelv , bcGroupv )

▶ otherwise, exchange u and v

if ∃i ∈ {u, v} : (leveli , groupi ) = (bcLevelu , bcGroupu ) then (bcLevelu , bcGroupu ) ← succlex (bcLevelu , bcGroupu )

▶ start looking for the next value

(bcLevelv , bcGroupv ) ← (bcLevelu , bcGroupu )

▶ broadcast the maximum

▶ Theorem 1. Protocol Approximate uses O(log4 (n)) states w.h.p., and stabilizes after O(log2 (n) · B(G)) interactions w.h.p. When it stabilizes we have bcLevelv = ℓ̂ for all agents v. For ℓ̂ we have with probability 1 − 4/nc that ℓ̂ ∈ [log n − 2 log log n − log c,

log n − log log n + 4 + 2c].

Proof Sketch for Theorem 1. The subprotocol GenerateRandomBit which is used to sample from the geometric and uniform distribution uses a constant number of states. Further, the four key fields of Approximate, level, group, bcLevel, and bcGroup are each O(log n) w.h.p., since the maximum of n independent Geom(1/2) random variables is O(log n) w.h.p., and group values are bounded by level values. The broadcast fields bcLevel and bcGroup track at most one beyond the maximum sampled values, so they are O(log n) as well. This gives us a state complexity of O(log4 n) w.h.p. The stabilization time is O(log2 n · B(G)) w.h.p. Each agent needs O(log n) random bits w.h.p. to determine its level and group (the geometric variable for level dominates). Theorem 4 shows that agents collect the required O(log n) random bits in time O( |E(G)| δ(G) log n). Note that |E(G)| δ(G) is precisely the expected time that an agent with minimal degree δ(G) is activated once. This is clearly a lower bound for B(G) as broadcast requires each agent to be active (at least) once. Thus, the time to sample all required random bits is O(B(G) log n) Once sampling is complete, the bcLevel and bcGroup fields converge to the first missing value (ML , MG ). The proof constructs a chain of witness agents v1 , . . . , vk whose (level, group)tuples cover every predecessor of (ML , MG ) in lexicographical order. Convergence proceeds as a sequence of broadcasts. 1. Agent v1 ’s value propagates through the graph until it reaches agent v2 . 2. Contact with v2 triggers the next lexicographic increment and a new epidemic. 3. This cascades through v3 , . . . , vk and finally propagates (ML , MG ) to all agents. Since k = O(log2 n) w.h.p. (there are at most 2ℓ groups per level ℓ, and ML = O(log n)), the total time is bounded by O(log2 n) consecutive broadcast times, yielding O(log2 n · B(G)).

Counting in Population Protocols on Graphs

2.2

Counting the Exact Population Size

To count the exact number of nodes we follow the general idea by Berenbrink, Kaaser, and Radzik [12]. Initially, the leader starts with M discrete tokens. These tokens are balanced using a classical load balancing algorithm [8]. Let Lu (t) denote the load of node u at time t. Once the load balancing has converged, all nodes have a load of M/n ± 2. Each agent outputs at time t the value round(M/Lu (t)) where round(·) is a function rounding to the nearest integer. Note that Lu (t) is not necessarily exactly the same for all of them (which it cannot be when n does not divide M ). To make sure that round(M/Lu (t)) still returns the same value for all agents M has to be by a factor n larger than the number of agents. We ensure this by choosing an M = Ω(n2 ). Fortunately, to choose M appropriately we do not have to know n exactly. Our protocol first computes an approximation of n (called bcLevel) using Approximate and then computes M as a function of that estimate. That way, once Approximate has converged, all agents can calculate a correct value for M , as required for correctness. This allows us to store just the (integer-valued) binary logarithm of the number of red tokens in a field called logRed, requiring only logarithmically many states. The field will store the value ⊥ if an agent does not store any red tokens. In our protocol the leader initially creates 2ℓ red tokens (ℓ has to be chosen suitably and we calculate it later). Each red token is worth M/2ℓ blue tokens. Our protocol first roughly balances the number of red tokens as follows: When an agent with red tokens interacts with an agent without any red tokens, the former sends half of its tokens to the latter. If both agents have red tokens, then the agents swap their tokens with probability 1/2. This ensures two things. Firstly, the number of red tokens stored at any agent is always a power of two. Secondly, when viewed individually, each red token performs a random walk. Whenever an agent stores only one red token (and not too many blue tokens already) the agent converts the red token into M/2ℓ blue tokens. Blue tokens are balanced in the standard way using the algorithm from [8]: when two agents interact, they balance their load as much as possible, with any round-off remaining at the initiator. These blue tokens then balance up to a discrepancy of at most three. The combination of our red tokens representing powers of two and the maximum number of blue tokens allowed per agent creates significant probabilistic dependencies between the movement of red and blue tokens. The main problem in our analysis is that agents with red tokens are only allowed to balance with agents having no red tokens. Since agents are only allowed to balance the load with their neighbors it is clear that the number of red tokens on nodes with a small distance in the graph is highly correlated. For this reason we swap the tokens in interactions where both agents have already red tokens. Note that these dependencies complicate the analysis of our protocol considerably. Formal Description of our Protocol. Our counting protocol consists of two parts, the outer protocol CountExact(u,v) and the subroutine Balance(u,v). We assume that there is a unique agent l for which the field isLeaderl = True, and isLeaderv = False for all other agents v = ̸ l. In addition to the fields of Approximate, agent v has fields logRedv and bluev storing the logarithm of the number of red tokens and the number of blue tokens, respectively. Initially, the leader starts with 2r(bcLevel) red tokens, and red tokens are converted into b(bcLevel) 2 blue tokens, where r and b are given by r(x) = max{0, ⌊x − 12 + log(x − 8)⌋}

and

b(x) = ⌈2(x + 2 log(x) + 7)⌉ + 3 − r(x). (1)

P. Berenbrink, R. Elsässer, T. Friedetzky, T. Götte, L. Hintze, and D. Kaaser

As initially we have bcLevel = 1 for all agents, the leader initializes logRedl to r(1) (which is zero) and all other agents initialize it to ⊥. The field blue is initialized to 0 for all agents. Now until Approximate has converged, bcLevel may change—although it is monotonically non-decreasing (see Observation 7). Whenever bcLevel is increased, all agents reset their loads and start all over again. More precisely, all nodes discard their red and blue tokens, and the leader l restarts with logRedl set to r(bcLevell ). This ensures that agents only balance their load with other agents having the same bcLevel value, preserving the total load in the system. All this is done in the outer protocol CountExact. Balance(u,v) first balances the red tokens, converts red tokens into blue tokens and balances the blue tokens. If a node u holds red tokens, it can only convert a red token into blue tokens if it has at most 2·2b(bcLevelu ) +3 blue tokens. One red token converts into 2b(bcLevelu ) blue tokens, where b is the function defined above. For our exact counting protocol we define the output function for a node u as ρ(bcLevelu , blueu ) = round 2r(bcLevelu ) · 2b(bcLevelu ) / blueu . This expression is the total load in the system divided by the load of node u (both in terms of blue tokens). Protocol 2 CountExact(u, v) 1

2 3 4 5 6 7

Approximate(u, v) for i ∈ {u, v} do if bcLeveli has increased then if isLeaderi then (logRedi , bluei ) ← (r(bcLeveli ), 0) else (logRedi , bluei ) ← (⊥, 0) Balance(u, v) output function: ρ(bcLevelu , blueu ) = round 2r(bcLevelu ) · 2b(bcLevelu ) / blueu

Protocol 3 Balance(u,v) 1 2 3

4 5

6 7

10 11 12 13

▶ balance red tokens if logRedu ≥ 1 and logRedv = ⊥ then logRedu , logRedv ← logRedu −1 else if logRedu = ⊥ and logRedv ≥ 1 then logRedu , logRedv ← logRedv −1 else if logRedu ≤ logRedv (logRedu , logRedv ) ← (logRedv , logRedu ) ▶ balance blue tokens l m j k blueu + bluev blueu + bluev (blueu , bluev ) ← , 2 2 ▶ load conversion (See Equation (1) for the definition of b(x).) for i ∈ {u, v} do if logRedi = 0 and bluei ≤ 2 · 2b(bcLeveli ) + 3then (logRedi , bluei ) ← ⊥, bluei +2b(bcLeveli )

▶ Theorem 2. Assume CountExact is started on a graph G = (V, E) with n = |V | nodes e and exactly one of the nodes is marked as leader. The protocol uses O(n) states, w.h.p. CountExact stabilizes w.h.p. in O(B(G) · log2 (n) + L(G) · log(n)) interactions, and at that time each agent outputs the correct value of n w.h.p.

Counting in Population Protocols on Graphs

Table 3 Comparison between the stabilization times of our new protocol and the baseline protocol on several graph classes. λ denotes the second-largest eigenvalue of the adjacency matrix of G. Note that for the Clique, [12] is faster than both. Note that (1 − λ(P(G))) denotes the spectral gap. Graph Class

O(B(G) log2 n + L(G) log n)

O(H(G) · n · log n)

Comment

Clique Regular graphs

O(n log3 n) n O( 1−λ(P(G)) log3 n)

O(n2 log n) 2 O( √ n

1 ∈ O(n2 ) 1−λ(P(G))

Cycle d-dim. Torus (d = 2) d-dim. Torus (d > 2) Worst Case

O(n3 log2 n) O(n2 log2 n) O(n · n2/d · log2 n) O(n4 log2 n)

O(n log n) O(n2 log2 n) O(n2 log n) O(n4 log n)

1−λ(P(G)) 3

log n)

Tight for Lollipop

Note that the worst-case stabilization time across all graph classes is O(n4 log2 n). This time is achieved, e.g., on the lollipop graph that consists of a path connected to a clique, each containing n/2 agents. However, for many graph classes the stabilization time is much lower. In Table 3 we present the performance of our protocol for various important graph classes like regular graphs and d-dimensional tori. Therein, we also compare the stabilization time of our protocol with the stabilization time of the baseline protocol (see Section 7) as a frame of reference. In particular, we note that for regular expanders the stabilization time is almost linear, which is optimal within logarithmic factors, and improves upon the baseline protocol almost by a linear factor. Proof Sketch for Theorem 2. The bound on the number of states is straightforward. In our proof we assume that protocol Approximate stabilizes such that all nodes have the same value of bcLevel. We call this time T0 . The rest of the proof is split into three parts. Part 1. Let T1 be the first time when all agents have at most one red token such that logRedu ≤ 0 for any node u. Lemma 13 shows that T1 − T0 = O(log(n) · L(G)) w.h.p. Part 2. Let T2 be the first time when all red tokens have been converted into blue tokens such that logRedu = ⊥ ∀u. Lemma 12 shows that T2 − T1 = O(log(n) · L(G)) w.h.p. Part 3. Let T3 be the first time when all blue tokens are balanced up to discrepancy 3 such that maxu {blueu } − minv {bluev } ≤ 3. Then Lemma 11 shows that that T3 − T2 = O(log(n) · L(G)) w.h.p. The bound on the running time follows by taking the union bound over these parts. Our algorithm outputs the correct size of the population since the number of blue tokens is at least Ω(n2 ). Hence, we can apply the same analysis as in [12]. It remains to give some more details about the three parts of our proof. Since the proof of the third part follows immediately from a known load balancing result [8] we discuss here only the first two parts. Part 1. This is the most challenging of our proofs. The main idea of the proof is to track the positions of individual red tokens and to bound the time until the token is the sole red token on its host node. In our proof we show that every red token, when considered by itself, performs a lazy random walk on the graph. Note that initially all red tokens are on the same node. Tokens that are on the same node travel together for a while until they separate due to a halving step. Recall that a halving step occurs exactly when a node with at least two red tokens interacts with a node without red tokens (see lines 2 to 5 in Protocol 3 Balance). Until then their movements are highly correlated and, in fact, identical.

P. Berenbrink, R. Elsässer, T. Friedetzky, T. Götte, L. Hintze, and D. Kaaser

To prove the theorem we fix a red token i and consider disjoint epochs of length O(L(G)). Now we consider, for each epoch j, the last interaction of token i in epoch j. Our goal is to show that there is a constant probability of i being involved in a halving step in exactly that interaction (unless, of course, it has already halved earlier in epoch j). Since in the beginning (as long as Approximate stabilized on a correct value) there are at most n/c red tokens (for a constant c), i must be alone after log2 n halving steps. It remains to show that for token i the probability of a halving step is constant per epoch. A halving step occurs exactly when the node holding token i interacts with a node not having any red tokens. As there is only a constant fraction of n/c red tokens, there must be many such nodes without red tokens. If halving steps only occurred at the end of an epoch, the stacks of red tokens would be distributed (more or less) uniformly among the nodes of the graph by the end of the epoch. Hence, it would be straightforward to show that interacting with an empty node would happen with constant probability, and we would be done. The usual method to deal with such situations is to simply assume that, since there are at most n/c red tokens, the worst-case probability to interact during the last step of an epoch with an empty node is still 1 − 1/c. However, stacks of red tokens can be halved at any time during an epoch, and we cannot focus on the last step due to significant dependencies between red tokens which started on the same node at the beginning of the epoch. We address the problem as follows. Let I be the set of red tokens which are, at the start of epoch j, in the same stack of red tokens (on the same node) as token i. Tokens in I stay together until they undergo a halving step. Tokens in I and tokens not in I do not move completely independently at random since they can never be on the same node, but they move independently otherwise (we make this precise in Lemma 17). Now let v be the node interacting with the node holding i in the final interaction of the epoch. There are three disjoint cases: v has no tokens at all, v has tokens from I, or v has tokens, but not from I. The first case is straightforward: there will be a halving step then and there (unless, of course, i is already alone, in which case there must have been a halving step before). In the second case it is easy to see that there has been a halving step before, since the tokens in I are no longer all on the same node. Hence, only the third case is problematic. In this case we bound the probability of a halving step by using the fact that tokens starting on different nodes behave almost independently (again Lemma 17). This allows us to bound the expected number of tokens on v not from I by a constant less than 1. Part 2. At time T1 each node holds at most one red token. We call the nodes holding a red token red nodes. On a high level, the proof proceeds by dividing the execution into non-overlapping epochs of length 2 · L(G) and showing that in every other epoch the number of red nodes decreases by a constant factor with constant probability. Recall that a red node will be able to convert its red token into blue tokens as soon as it interacts with a node holding a small enough number of blue tokens. Fortunately, the number of nodes that can be used for the conversion is sufficiently large as agents constantly balance their blue tokens. More precisely, we partition time into epochs of length 2 · L(G). For i ≥ 0 let ti denote the first step of epoch i, and let R(i) denote the number of red nodes at time ti . For our proof it will be necessary to distinguish between the blue tokens a node has at the beginning of an epoch and the blue tokens it receives due to conversions in that epoch. Hence, we refer to the tokens which are on a node at the beginning of an epoch as old blue tokens. All blue token added in epoch i are new blue tokens, respectively. In the following we denote the set of old blue tokens at the beginning of epoch i as B ′ (i). Note that we can assume w.l.o.g. that our protocol balances the old blue tokens and the new blue tokens independently. By [8,

Counting in Population Protocols on Graphs

Theorem 2.3], the old blue tokens from epoch i are balanced at the beginning of epoch i + 1 with at least constant probability, and the discrepancy is at most 3. Since the total number of blue tokens generated by Protocol 3 (Balance) is bounded by n · 2b(bcLevel) there are at most n · 2b(bcLevel) old blue tokens. Hence, if the tokens are successfully balanced, each node holds at most 2b(bcLevel) + 3 old blue tokens at the end of each epoch. Let now B(i + 1) be the total number of blue tokens and ∂B(i + 1) = B(i + 1) − B ′ (i) be the number of new blue tokens created in epoch i. We now distinguish between two cases: 1. If ∂B(i + 1) ≤ 23 R(i)2b(bcLevel) then 12 R(i) red nodes have fewer than 2 · 2b(bcLevel) + 3 blue tokens, and their red token will be converted into blue tokens in their next interaction (line 12 of protocol Balance). W.h.p., this interaction happens in epoch i + 1. 2. Otherwise, ∂B(i + 1) > 23 R(i)2b(bcLevel) . In this case 23 R(i) red nodes must have already converted their token in epoch i. Therefore, given that the old blue tokens are balanced, the number of red nodes decreases by a constant factor, either in epoch i (Case 2) or epoch i + 1 (Case 1).

2.3

Impossibility Result

Our protocol converges to the correct estimate of n w.h.p. However, the agents themselves cannot detect when this stabilization occurs. In particular, even if an agent currently stores the correct value of n, it cannot determine whether this value is final or may still change in future interactions. One may therefore ask whether it is possible to make the protocol detect that it has terminated. We follow the definition by Doty and Eftekhari [19] and augment each node u with a Boolean variable terminatedu that indicates termination. Ideally, this variable would be set to True once the agent has computed the correct value of n, and remain True thereafter, at least with some non-trivial probability. As it turns out, however, this is impossible in our model. More precisely, if the protocol has no a priori knowledge about the underlying graph, then no agent can reliably detect that the correct value of n has been computed, even in the presence of a unique leader. ▶ Theorem 3. Let P be a graph-uniform population protocol that computes the size of an interaction graph. Suppose there is a graph H on which P terminates correctly with positive probability in bounded time tH for some initial configuration. 1. If the protocol starts with a unique leader then there is an infinite sequence of graphs (Gi )i∈N with |V (Gi )| < |V (Gi+1 )| for all i so that the probability of P terminating incorrectly on Gi is constant. 2. Without a unique leader there is an infinite sequence of graphs (G′i )i∈N with |V (G′i )| < |V (G′i+1 )| for all i so that the probability of P terminating incorrectly on G′i is 1 − exp(−Θ(|V (G′i )|)). Proof Sketch for Theorem 3. We begin with the first statement. The key idea is to embed the graph H inside a much larger graph Gi . The construction connects H as an induced subgraph to the rest of Gi by just a single edge. During the first tH interactions which involve nodes in H, that connecting edge is never used with constant probability. When this happens, H’s nodes cannot tell they are part of a larger graph; they terminate thinking that the graph size is |H|. But the actual size is |Gi | > |H|, so they output the wrong answer. The second statement uses more or less the same setup except all agents start in an identical state. Now the probability of correct termination becomes exponentially small in the graph size. Instead of embedding H once, we embed many disjoint copies of H. We create roughly ni /|H| copies of H, each connected to a central clique by one edge, where ni denotes the size

P. Berenbrink, R. Elsässer, T. Friedetzky, T. Götte, L. Hintze, and D. Kaaser

of the graph with all the copies of H. Each copy independently has constant probability of getting isolated and terminating incorrectly. For the protocol to be correct on Gi , all copies must avoid this trap. The probability of success is then exp(−Θ(ni )).

2.4

Generating Independent Random Bits

Our final result is a uniform protocol for generating independent, fair, unbiased random bits. These bits will be used as a basic primitive in our counting protocol. While it is not surprising that such a protocol exists, we are not aware of a rigorous analysis; thus, we provide one here. Just as all other protocols (we are aware of) for sampling bits in graphical population protocols [3, 4], our protocol derives randomness from the orientation of the edge selected by the scheduler in each step. Instead of using static coloring as in [25] to decide which of the two interaction partners may use the random bit implied by the direction, our protocol uses dynamic 2-coloring to produce a non-monochromatic edge with constant probability. In a nutshell, the protocol works as follows. Each node u maintains a color, either black or white, stored in the field coloru . Whenever nodes u and v interact and have different colors, the black node generates a random bit. Suppose that u is black. Then the bit is stored in the field randu , taking value 1 if u is the initiator, i.e., if the scheduler activated edge (u, v), and value 0 otherwise. The white node v sets randv to ⊥, meaning that it created no random bit in this interaction. If both endpoints have the same color, the corresponding values randu and randv are both set to ⊥. At the end of the step, the colors of u and v are updated to black and white, respectively. Protocol 4 GenerateRandomBit(u, v) 1 2 3 4 5 6 7

if (coloru , colorv ) = (Black, White) then (randu , randv ) ← (1, ⊥) else if (coloru , colorv ) = (White, Black) then (randu , randv ) ← (⊥, 0) else (randu , randv ) ← (⊥, ⊥) (coloru , colorv ) ← (Black, White)

▶ The black node u is initiator, assign bit 1 ▶ The black node v is responder, assign bit 0

▶ Theorem 4. Let T be an arbitrary step and assume that node u interacts in steps Tu ⊆ [T ]. For tj ∈ Tu , let Ru (tj ) be the value of randu ∈ {0, 1, ⊥} at the end of the interaction in step tj . For node u, define Ru′ (T ) = {Ru (ti ) | Ru (ti ) ∈ {0, 1}, ti ∈ Tu }. 1. For all R(ti ) ∈ Ru′ (T ) we have Pr[Ru′ (ti ) = 1] = Pr[Ru′ (ti ) = 0] = 21 . S 2. All variables in v∈V Rv′ (T ) are mutually independent. 3. For any step t ≥ 1, each node u generates a random bit in steps [t, t + 4|E(G)|/δ(G)] with probability at least 1/96. This probability is independent for non-overlapping time intervals. The first two statements show that our protocol indeed generates uniformly random and independent bits. The third result states that each node u creates a random bit roughly every |E(G)|/δ(G) steps where δ(G) is the minimal degree of G. Note that the number of random bits a node generates is proportional to the number of times it interacts. We prove the theorem in Section 6. Moreover, we derive a user-friendly statement about the number of bits that are sampled within a certain time frame. Using well-known tail estimates, the following corollary directly follows from the third property in the above theorem. ▶ Corollary 5. Let ℓ ≥ 1 be an integer.

Counting in Population Protocols on Graphs

1. In O

|E(G)| δ(G) · ℓ −ℓ

steps, a node u draws at least ℓ random bits with probability at least

1−2 . 2. For ℓ ≥ (c + 1) log n, in O |E(G)| δ(G) · ℓ steps, each node draws at least ℓ random bits with probability at least 1 − n−c . Proof Sketch for Theorem 4. For this protocol, it is relatively easy to show that each black node receives the bit 0 and 1 with probability 1/2 each. This holds since the random edge orientation is assigned to only one of the two activated nodes in each step. Showing that each node receives random bits regularly is harder. To show this we partition time into phases of length Θ(|E(G)|/δ(G)). Fix an arbitrary phase i and fix all random choices up to this phase. After this conditioning, all remaining randomness stems solely from the scheduler’s random choices within phase i. Recall that a random bit is created by node u whenever node u is black and interacts with a white node v. In turn the colors of u and v are determined by the outcome of their previous interactions. Since we have an arbitrary coloring of G at the beginning of the phase, u possibly starts with the same color as all its neighbors, e.g., white. Now the length of the phase comes into play. Using elementary calculations, we show that with constant probability the following happens in phase i: node u interacts with a node w, and both u and w had another interaction (not necessarily with each other) earlier in phase i. Thus, in this case, the color of u and w is only determined by the random choices during these interactions, thus it is independent of the graph coloring at the beginning of the phase: The most recent interactions of u and w were with each other. In this case they have different colors, and u is black with probability 1/2 (see Line 7 of Protocol 4). The most recent interactions of u and w occurred in different interactions. In this case the color of u and w is determined exclusively by the orientation of the edge in these interactions (again, Line 7 in Protocol 4). Hence, the probability that u is black and v is white is 1/4. It follows that, considering the second interaction of node u, the colors of nodes u and w are either deterministically different or they are independent random variables. Note that the interaction pattern only depends on the pairs of nodes that interact, while the coloring depends on the orientation of the edges. As these are chosen independently of each other, the probability of having the interaction pattern and the appropriate coloring is constant. We give the detailed proof in Section 6.

2.5

Summary and Future Work

We present a fast population protocol on graphs to count the exact number of nodes. Our protocol requires no knowledge of the underlying graph. Its performance depends only on spectral properties of the random scheduler, the degree distribution of G, and the broadcast time B(G). Our approach separates the task into three independent components: generation of independent random bits on graphs, a tight approximation of log n via a refined first-missingvalue construction, and load-balancing-based exact counting driven by a unique leader. We believe that the first two components are of independent interest. The resulting protocol e requires O(n) states and stabilizes w.h.p. in a time proportional to the broadcast time B(G) and the load balancing L(G) time of the graph. Within logarithmic factors, our approach is always as fast as the baseline protocol based on coalescing random walks. For important graph classes like regular expanders, i.e., graphs with constant edge expansion, or

P. Berenbrink, R. Elsässer, T. Friedetzky, T. Götte, L. Hintze, and D. Kaaser

d-dimensional torii (with d > 3), our new protocol is faster. We conjecture that the protocol can be turned into an always-correct protocol which is guaranteed to eventually output the correct value of n with probability 1, using the same convergence time and state complexity. Finally, we present an impossibility result for terminating uniform protocols that compute strongly increasing size properties, both with and without a leader. Further, our protocol is state-optimal within logarithmic factors. To encode the exact number of nodes, every node needs at least Ω(n) states. Our protocol, on the other hand, e requires O(n) = n · polylog n states. For the sake of presentation, we did not attempt to optimize the degree of the polylogarithmic term in the expression for the number of states. Finally, we discuss the assumption that our protocol is initialized with a unique leader. Although this is a genuine restriction, unique leaders are a well-established resource in the population-protocol literature. For example, Angluin, Aspnes, and Eisenstat [6] study fast computation with a given leader, while the approximate- and exact-counting protocols of Berenbrink, Kaaser, and Radzik [12] elect and subsequently rely on one. On the other hand, there exists simple graph-uniform protocol that can count exactly without a leader using O(n) states; however, its stabilization time is governed by the maximal hitting time of a random walk on the underlying graph and can, for many graph families, be far larger than e O(B(G) + L(G)). Thus, the leader does not trivialize the problem but enables a substantially faster protocol whose construction and analysis remain technically involved. Nevertheless, eliminating the leader assumption while keeping a near-linear state complexity and a low running time is an important direction for future work. The closest known result is the graph-uniform leader-election protocol of Alistarh, Rybicki, and Voitovych [4], which requires no prior knowledge of the graph and stabilizes in O(B(G) + n log n) interactions, but uses O(n4 ) states. This leaves open the concrete problem of designing a stabilizing e leader-election protocol for arbitrary graphs that is graph-uniform, uses O(n) states, and e stabilizes in O(B(G) + L(G)) interactions.

Approximate Counting

In this section we present all technical details of our algorithm for approximate counting. First each agent v samples a value levelv having geometric distribution Geom(1/2). We aim to determine the smallest level value where less than roughly log(n) agents have said value. In lieu of a space-efficient and fast procedure to do this directly, we instead let agents additionally sample a groupv ranging from 0 to 2⌈log(levelv )⌉ − 1 (i.e., a non-negative integer whose binary representation has at most ⌈log(n)⌉ bits) chosen u.a.r. If for a given level L all groups have at least one agent, then we presume that this level has still too much support. This is reasonable to assume from a coupon collection argument: For each level L there are between L and 2L groups belonging to that level. Each agent which sampled level L (there are expectedly n/2L of these agents) samples one group u.a.r. If all groups are chosen by at least one agent we conclude that the number agents on that level was sufficiently large to sample the full set. It is well known that in expectation Θ(L log(L)) agents are needed to collect all groups. Since we are looking for a level of order log n, this works, as we show below. If we now assume that level/group tuples are ordered lexicographically, we look for the first tuple which was not sampled and output the level of that group. Hence, we are looking for the first missing value of the tuples.

Counting in Population Protocols on Graphs

3.1

Formal Description

The algorithm consists of two parts. First, agent v use the random bits sampled by Protocol 4 to determine its random variable levelv . After that the agent samples its random variable groupv (whose range is a function of levelv ), again using Protocol 4. Finally that agents are looking for the first missing value in the lexicographic order. We first describe the sampling of levelu and groupu and then the computation of the first missing value. Sampling Level and Group. SampleLevelAndGroup samples the levelu and groupu values. To control its behavior, each agent has two Boolean fields: isSampling, initialized to True, indicates whether sampling is ongoing, and levelDone, initialized to False, indicates whether sampling the level value has finished (so that the protocol may proceed sampling the group value). SampleLevelAndGroup first generates a random bit using Protocol 4 from the previous section. If an agent has a bit available (meaning that rand = ̸ ⊥), it uses it to build up level and group values as follows. level is initialized to 1 and then incremented for each coin flip showing 1; if the coin shows 0, sampling the level is done. The final value of level is therefore the number of fair coin flips until the first zero is observed. It has distribution Geom(1/2) as desired. The possible values for groupw , from which we want to sample u.a.r., are exactly those integers whose binary representation have at most ⌈log levelw ⌉ bits. Their binary representation has the distribution of a sequence of levelw bits sampled independently and uniformly at random. The protocol samples groupw in exactly this way. Protocol 5 SampleLevelAndGroup(u, v) 1

2 3 4 5 6 7 8 9 10

GenerateRandomBit(u, v) for w ∈ {u, v} with randw ̸= ⊥ and isSamplingw = True do if ¬ levelDonew then if randw = 1 then levelw ← levelw +1 else levelDonew ← True else groupw ← groupw +2groupBitsSampledw · randw groupBitsSampledw ← groupBitsSampledw +1 if groupBitsSampledw = ⌈log levelw ⌉ then isSamplingw ← False

Coupon Collection. We consider the lexicographic order for set S = {(l, g) ∈ N+ × N0 | g < 2⌈log(l)⌉ } of valid (levelv , groupv ) tuples. In this order, we have for two tuples (l1 , g1 ), (l2 , g2 ) ∈ S that (l1 , g1 ) ≤lex (l2 , g2 ) ⇐⇒ (l1 < l2 ) ∨ (l1 = l2 ∧ g1 ≤ g2 ). This is a total order on S, so that we can define maxlex and minlex in the usual way. Furthermore, let succlex ((l, g)) = minlex {(l′ , g ′ ) ∈ S | (l′ , g ′ ) >lex (l, g)} be the successor function for this order, which is well-defined and computable as succlex ((l, g)) =

( (l + 1, 0), (l, g + 1),

If g = 2⌈log(l)⌉ − 1, otherwise.

We determine the first missing value among agents’ tuples under this order: The first missing value of a set S ⊆ S is FMVlex (S) = min{(l, g) ∈ S | (l, g) ̸∈ S}, lex

P. Berenbrink, R. Elsässer, T. Friedetzky, T. Götte, L. Hintze, and D. Kaaser

so that the value we compute is FMV({(leveli , groupi ) | i ∈ [n]}). The first missing value among tuples will thus have as its first entry the lowest level where a group is missing, and as its second entry the numerically smallest missing group. The protocol Approximate computes this first missing value via broadcasts: In the protocol Approximate, agents have fields bcLevelv and bcGroupv which are both initialized to 1 and 0 (so that the initial value of (bcLevelv , bcGroupv ) is minlex (S) = (1, 0)). Whenever agent v has (levelv , groupv ) = (bcLevel, bcGroup), the agent knows for sure that the tuple (bcLevel, bcGroup) is not missing and thus sets it to the successor tuple, which, as far as it knows, might be missing. This continues as long as successive tuples are not missing. Crucially, for the first tuple that is missing, no further increase is possible, so that the protocol will converge. Protocol 6 Protocol 1. Approximate(u, v), extended version 1 2

3 4

5 6

if isSamplingu or isSamplingv then SampleLevelAndGroup(u, v) else w.l.o.g. let (bcLevelu , bcGroupu ) ≥lex (bcLevelv , bcGroupv )

▶ otherwise, exchange u and v

if ∃i ∈ {u, v} : (leveli , groupi ) = (bcLevelu , bcGroupu ) then (bcLevelu , bcGroupu ) ← succlex (bcLevelu , bcGroupu ) ▶ start looking for the next value (bcLevelv , bcGroupv ) ← (bcLevelu , bcGroupu )

3.2

▶ broadcast the maximum

Proof of Theorem 1

The analysis in this section is split into two parts. First, we analyze the running time and the space requirements of our protocols. Then we determine the approximation quality of our estimation. We show the following theorem. ▶ Theorem 1. Protocol Approximate uses O(log4 (n)) states w.h.p., and stabilizes after O(log2 (n) · B(G)) interactions w.h.p. When it stabilizes we have bcLevelv = ℓ̂ for all agents v. For ℓ̂ we have with probability 1 − 4/nc that ℓ̂ ∈ [log n − 2 log log n − log c,

log n − log log n + 4 + 2c].

For die-hard readers we present tighter bounds in Lemma 9. The proof of the theorem directly follows from Lemma 6 and Observation 7. ▶ Lemma 6. Protocol Approximate uses O(log4 (n)) states w.h.p., and stabilizes after O(log2 (n) · B(G)) interactions w.h.p. Proof. GenerateRandomBit uses a constant number of states (as all fields used by it have a fixed set of values). Approximate additionally uses some Boolean fields (which have 2 states each) and the four fields level, group, bcLevel and bcGroup. W.h.p., maxi∈[n] {leveli } = O(log(n)), and hence also maxi∈[n] {groupi } = O(log(n)) (since groupi < 2 leveli ). Since the bcLevel and bcGroup values are at most one larger than the maximum values of level and group among all agents, they are in O(log(n)) as well, leading to the claimed stat count. To bound the stabilization time we have to bound the times until agents are done with the sampling of level and group fields, as well as the time it takes for bcLevel and bcGroup to converge.

Counting in Population Protocols on Graphs

Sampling. W.h.p. the maximum value of levelu is O(log(n)), agent u needs at most O(log(n)) random bits to sample level, w.h.p. For sampling groupu agent u needs ⌈log level⌉ random bits. It is easy to see that ⌈log level⌉ ∈ O(log log n) = o(log(n)). From Theorem 4 it follows that within O(|E|/δ(G) · log(n)) interactions, agent v will have sampled sufficiently many random bits, with probability at least 1 − n−2 . Taking a union bound over all agents we see that with a probability at least 1 − n−1 this is true for all agents within O(|E|/δ(G) · log n) interactions, where δ(G) is the minimum degree from G. Now note that the expected time until a node u with degree deg(u) participates in an interaction is |E|/deg(u). Hence |E|/δ(G) is a lower bound on the expected broadcast time and |E|/δ(G) = O(B(G)), recalling B(G) is defined as the expected (worst-case) broadcast time of G. From this follows that with a probability at least 1 − n−1 the running time of SampleLevelAndGroup is O(|E|/|Nv | · log(n)). First Missing Value. Now we bound the time for the bcLevelu and bcGroupu values to stabilize. To that end, define T as the time where all agents u have finished sampling levelu and groupu and consider Approximate(u, v) from T onward. By construction, for all t ≥ T we have (levelu (t), groupu (t)) = (levelu (T ), groupu (T )). For ease of presentation we drop T in level and group in the remainder of the proof. Let (ML , MG ) = FMVlex ({(levelu , groupu ) | u ∈ V }). By definition there must be agents u1 , u2 , . . . , uk ∈ V such that (levelu1 , groupu1 ) = (1, 0), (ML , MS ) = succlex ((leveluk , groupuk )), and for all j ∈ [k − 1] we have (leveluj+1 , groupuj+1 ) = succlex ((leveluj , groupuj )). Whenever an agent uj first interacts with an agent v having (bcLevelv , bcGroupv ) = (leveluj , groupuj ) the agents uj and v both set their (bcLevel, bcGroup) to succlex ((leveluj , groupuj )). This increased value of (bcLevel, bcGroup) is now propagated via broadcast through the graph. The propagation might be preempted if there appears a (bcLevel, bcGroup)-tuples with even larger values. From this it follows that the time to reach a configuration where all agents have (bcLevel, bcGroup) = (ML , MG ) is bounded by k times the broadcast time. It remains to bound the value of k. Since ML = O(log(n)) w.h.p. (Lemma 9) and there are at most 2L groups at level L we have k = O(log2 (n)) w.h.p. Hence the time in question is bounded by the time of O(log2 (n)) consecutive broadcasts resulting in an expected running time of O(log2 n · B(G)). From simple Markov bounds it follows that with a probability of 1/2 each of these broadcasts is finished after time 2B(G), Applying a standard Chernoff bound one can argue that w.h.p. the running time of Approximate is bounded by O(log2 n · B(G)). ◀

P. Berenbrink, R. Elsässer, T. Friedetzky, T. Götte, L. Hintze, and D. Kaaser

Next we present the following observation describing the values sampled by our algorithm. ▶ Observation 7. Consider the variables determined by Protocol 5 and Protocol 1. For all agents, the value of bcLevelv is non-decreasing over time. After executing Approximate(u, v), we have bcLevelu = bcLevelv . Assume at time t all agents v have isSamplingu = False and (bcLevelv , bcGroupv ) = FMVlex ({(levelu , groupu ) | u ∈ V }), then bcLevelv does not change anymore. For each node v we define tv as the time when agent v finishes the sampling via the protocol SampleLevelAndGroup. Then we have levelv (tv ) ∼ Geom(1/2),

and

groupv (tv ) ∼ U {1, . . . , 2⌈log levelv (T1 )⌉ }.

Approximation Quality. In this section we estimate the approximation quality of our regime. For the ease of presentation we use in the lemma Li instead of leveli and Gi instead of groupi . We will need the following Chernoff bound. ▶ Theorem 8 (Theorem 7 in [16]). Let X1 , X2 , . . . , Xn be independent random variables Pn taking values in {0, 1}. Let X = i=1 Xi and let µ = E[X] denote X’s expected value. Then Pr[X > R] ≤ 2−xR for x > 0 and R ≥ (2x e − 1)µ. ▶ Lemma 9. Let (Li )i∈[n] be i.i.d. Geom(1/2) r.v.s, and for all i ∈ [n] let Gi ∼ U({0, . . . , 2⌈log Li ⌉ − 1}) chosen independently from all other values (except of course Li ). Let (ML , MG ) = FMVlex ({(Li , Gi ) | i ∈ [n]}). 1. Pr[ML ≤ log(n)−log log n+2+log(e)+2c] ≥ 1−2n−c for all c > 0 and n ≥ max{16, 22/c }. 2. Pr[ML ≥ log(n) − log log n − log(c ln(n) + 2 ln log(n))] ≥ 1 − 2n−c for all c ≥ 1 and n ≥ 3. Proof. (1) Let Nl be the number of is for which Li = l, i.e., Nl = |{i ∈ [n] | Li = l}|. If Nl < l (and hence Nl ≤ 2⌈log(l)⌉ ) for some level l, there must be a g ∈ {0, . . . , 2⌈log Li ⌉ − 1} such that there is no i with (Li , Gi ) = (l, g), so that Ml ≤ l. Now consider some c > 0 and 2−2c 2−2c l = log(n)−log log(n)+2+log(e)+2c. Then Pr[Li = l] = log(n) n · 4e and E[Nl ] = 4e log(n). To use the tail bound of Theorem 8, see that we hence have (22c e − 1)E[Nl ] ≤ 14 log(n) ≤ 1 1 2/c ), so that 2 log(n) − 2c (for n ≥ 2 Pr[Nl >

1 1 1 log(n) − ] ≤ 2−2c( 2 log(n)−1/(2c)) = 2n−c . 2 2c

And so as long as log log(n) ≤ 12 log(n) (which holds for n ≥ 16) we have Pr[ML > l] ≤ Pr[Nl ≥ l] ≤ Pr[Nl >

1 1 log n − ] ≤ 2n−c . 2 2c

(2) Let Al,g be 1 if and only if there is no i with (Li , Gi ) = (l, g), and 0 otherwise. Then for all l and g ∈ {0, . . . , 2⌈log(l)⌉ − 1}, E[Al,g ] = Pr[Al,g = 1] =

1−

1 2l 2⌈log(l)⌉

≤

1−

1 2l l

n ≤ exp − l . 2l

Counting in Population Protocols on Graphs

Now for ˆl = log n − log log n − log(c ln n + 2 ln log n) (which is at most log n for c ≥ 1 as long as n ≥ 3), we have ! −n n ≤ exp = exp(−c ln(n) − 2 ln log n) = n−c log−2 (n). exp − n · log n 2l̂ ˆl (log n)(c ln n+2 ln log n) Pl P2⌈log(l)⌉ −1 Now ML ≤ l if and only if l′ =1 g=0 Al′ ,g ≥ 1 (i.e., some level-group-tuple is missing up to that value of l). So by Markov’s inequality and linearity of expectation,   l′ ⌉ l′ ⌉ l 2⌈log l̂ 2⌈log l̂ X X −1 X X −1 X ′ Pr[ML ≤ ˆl] ≤ Pr[ Al′ ,g ≥ 1] ≤ E Al′ ,g  ≤ 2⌈log l ⌉ E[Al′ ,g ] l′ =1

≤

l̂ X

g=0

l′ =1

g=0

l′ =1

h i 2l′ E Al̂,g ≤ 2ˆl2 n−c log−2 ≤ 2 log2 n · n−c log−2 (n) = 2n−c .

◀

l′ =1

Counting the Exact Population Size

P. Berenbrink, R. Elsässer, T. Friedetzky, T. Götte, L. Hintze, and D. Kaaser

red tokens are only allowed to balance with agents having no red tokens. Since agents are only allowed to balance the load with their neighbors it is clear that the number of red tokens on nodes with a small distance in the graph is highly correlated. For this reason we swap the tokens in interactions where both agents have already red tokens. Note that these dependencies complicate the analysis of our protocol considerably.

4.1

Formal Description of our Protocol

Our counting protocol consists of two parts, the outer protocol CountExact(u,v) and the subroutine Balance(u,v). We assume that there is a unique agent l for which the field isLeaderl = True, and isLeaderv = False for all other agents v = ̸ l. In addition to the fields of Approximate, agent v has fields logRedv and bluev storing the logarithm of the number of red tokens and the number of blue tokens, respectively. Initially, the leader starts with 2r(bcLevel) red tokens, and red tokens are converted into 2b(bcLevel) blue tokens, where r and b are given by r(x) = max{0, ⌊x − 12 + log(x − 8)⌋}

and

b(x) = ⌈2(x + 2 log(x) + 7)⌉ + 3 − r(x). (1)

2 3 4 5 6 7

Counting in Population Protocols on Graphs

Protocol 3. Balance(u,v) 1 2 3

4 5

6 7

10 11 12 13

4.2

Proof of Theorem 2

For the following analysis assume that Approximate has stabilized on the correct value. Hence, we condition on the high probability event that the statements from Theorem 1 holds and prove the following theorem. ▶ Theorem 2. Assume CountExact is started on a graph G = (V, E) with n = |V | nodes e and exactly one of the nodes is marked as leader. The protocol uses O(n) states, w.h.p. CountExact stabilizes w.h.p. in O(B(G) · log2 (n) + L(G) · log(n)) interactions, and at that time each agent outputs the correct value of n w.h.p. Proof. We first show the bound on the running time and the correctness, and then the bound on the number of states. Running Time and Correctness. The proof of the running time follows from Theorem 1 and Lemmas 11–13. Let T0 be the first time when Approximate stabilizes such that all nodes have the same value of bcLevel. Theorem 1 shows that T0 = O(log2 (n) · B(G)) w.h.p. Let T1 be the first time when all agents have at most one red token such that logRedu ≤ 0 for any node u. Lemma 13 shows that T1 − T0 = O(log(n) · L(G)) w.h.p. Let T2 be the first time when all red tokens have been converted into blue tokens such that logRedu = ⊥ for any node u. Lemma 12 shows that T2 − T1 = O(log(n) · L(G)) w.h.p. Let T3 be the first time when all blue tokens are balanced up to discrepancy 3 such that maxu {blueu } − minv {bluev } ≤ 3. Lemma 11 shows that T3 − T2 = O(log(n · L(G)) w.h.p. Taking the union bound over the individual statements, it follows w.h.p. that after O(B(G) · log2 (n) + L(G) · log(n)) all nodes u have the same value of bcLevelu , have logRedu = ⊥, and have blueu = M/n ± 2, where M = R · B = 2r(bcLevelu ) · 2b(bcLevelu ) is the total number of blue tokens in the system.

P. Berenbrink, R. Elsässer, T. Friedetzky, T. Götte, L. Hintze, and D. Kaaser

Observe that the output of node u is ρ(bcLevelu , blueu ) = round(M/ blueu ). From Observation 10 it follows that M = Ω(n2 ) (where the constant can be made arbitrarily large by adjusting Equation (1)). This allows us to apply the same analysis as in [12]. From the same calculations as in the proof of Lemma 4.2 from [12] it follows that rounding all values in [⌊M/(blueu +2)⌋, ⌈M/(blueu −2)⌉] gives always the same integer. This integer is precisely the value of n. State Space Complexity. It remains to show that CountExact uses O(n polylog(n)) states w.h.p. To this end, recall that Protocol 1 (Approximate) uses O(log4 (n)) states w.h.p. (Lemma 6). logRed is either ⊥ or a non-negative integer with maximum value r(bcLevel), where bcLevel = O(log(n)) w.h.p. (see Theorem 1). blue has maximum value 2 · 2b(bcLevel) + 3 + 2b(bcLevel) = O(2b(bcLevel) ) (this follows form our protocol Balance)). To bound this value, we bound b(bcLevel) by first considering r(x) for sufficiently large x. We have r(x) = ⌊x − 12 + log(x − 8)⌋, and thus, b(x) = ⌈2(x + 2 log(x) + 7)⌉ + 3 − ⌊x − 12 + log(x − 8)⌋ ≤ 2(x + 2 log(x) + 7) + 4 − x + 12 − log(x − 8) = x + 4 log(x) − log(x − 8) + 30 ≤ x + 3 log(x) + 32 with the last inequality holding for x ≥ 32/3. At the time where Approximate has stabilized (which is the maximum value of bcLevel ever encountered as it is non-decreasing by Observation 7), we know from Lemma 9 that w.h.p. bcLevel ≥ log(n) − O(log log(n)). Hence we can apply the above estimation with x = bcLevel. Since bcLevel ≤ log(n) − log log(n) + O(1) w.h.p. by Lemma 9 we obtain that, w.h.p., b(bcLevel) = x + 3 log(x) + 32 ≤ log(n) + 2 log log n + O(1). So, for sufficiently large n, w.h.p., b(bcLevel) ≤ log n + 2 log log n + O(1), so that 2b(bcLevel) = n log2 n · 2O(1) = O(n log2 n). The claim follows by union bound and multiplying the state counts of all fields together.

◀

In the following observation we bound the number of red and blue tokens coming from a correct approximation by protocol Approximate. ▶ Observation 10. Assume Protocol 1 (Approximate) has stabilized with a correct approximation of n. Let R = 2r(bcLevel) denote the number of red tokens generated by CountExact and let B = 2b(bcLevel) denote the number of blue tokens generated by Protocol 3 ( Balance) for each red token. Then we have, for n large enough, n 4c 1. 14 ≤R≤ n with probability 1 − O(1/nc ). 2 (c log n + 2 log log n) 128 2.

226 n(log n)2 236 4c n(log n + 2c + 4)3 ≤B≤ with probability 1 − O(1/nc ). c log n + 2 log log n log n

Counting in Population Protocols on Graphs

3. The total number of blue tokens M generated by Protocol 3 ( Balance) is at least M =R·B ≥

212 n2 (log2 n) 212 n2 (log2 n) 210 ≥ = 2 · n2 , w.h.p. (for c ≥ 2) 2 2 (c log n + 2 log log n) (2c log n) c

Proof. These are tedious but otherwise straightforward calculations based on Equation (1) and the detailed bounds of Lemma 9. ◀

4.3

Balancing Blue Tokens

▶ Lemma 11. Let T0 be the first time when the Approximate has stabilized on the correct value and let T2 ≥ T0 be the first time when all red tokens are converted into blue tokens (i.e., logRedv = ⊥). We define T3 to be the first time when maxu {blueu } − minv {bluev } ≤ 3. Then w.h.p. T3 − T2 = O(log(n) · L(G)). Proof. Let Bu (t) = blueu (t) be the number of blue tokens of node u after step t and define ⃗ ⃗ B(t) = (Bu (t))u∈V . Observe that the total number of blue tokens ∥B(t)∥ 1 can only change if a red token converts into multiple blue tokens. Therefore, after time T1 the total number ⃗ ⃗ of blue tokens remains fixed with ∥B(t)∥ 1 = ∥B(T1 )∥1 for any t ≥ T2 . ⃗ The discrepancy of a load vector B(t) is defined as maxu {Bu (t)} − minv {Bv (t)}. A red token can only convert into blue tokens if blueu ≤ 2·2b(bcLevelu ) +3 (see Line 12 in Protocol 2). ⃗ 1 )) = O(poly(n)) w.h.p. Hence, Bu (T1 ) ≤ 3 · 2b(bcLevelu ) + 3 for any node u and thus disc(B(T Our goal is to apply a variant of Theorem 2.3 from [8] for the following asynchronous ⃗ load balancing process with randomized rounding. For a given load vector B(t) at time t, ⃗ + 1) is obtained from B(t) ⃗ the load vector B(t by choosing an edge {u, v} ∈ E(G) uniformly at random and balancing the loads of nodes u and v over this edge as evenly as possible. So-called excess tokens which arise due to load being discrete are assigned randomly to either u or v. Formally, m j k l Bu (t)+Bv (t) v (t)  Bu (t)+B , , 2 2 k l m (Bu (t + 1), Bv (t + 1)) = j  Bu (t)+Bv (t) , Bu (t)+Bv (t) , 2 2

with probability 1/2, with probability 1/2,

while Bw (t + 1) = Bw (t) for all w ̸∈ {u, v}. Observe that this load balancing process is equivalent to our population protocol for balancing the blue tokens. Indeed, in our protocol we choose an oriented edge (u, v) uniformly at random and assign the rounded-up value to the initiator u and the rounded-down value to the responder v, with both edge orientations (u, v) and (v, u) chosen with the same ⃗ 1 ) = O(poly(n)). We apply Theorem probability 1/2. Observe furthermore that disc B(T 2.3 from [8] (and the remarks that follow the theorem) to the load balancing process with ⃗ 1 ). This gives us for a τ = O(n log(n) · d(G) · (1 − λ(P(G)))) and any initial load vector B(T ∆(G) constant c > 0 that ⃗ )) ≤ 3] ≥ 1 − exp(− log1−c (n)). Pr[disc(B(τ d(G) The lemma now follows from the definition L(G) = n log(n) ∆(G) (1 − λ(P(G)))−1 , where the high probability is achieved by repeating the load balancing process up to log n times. ◀

P. Berenbrink, R. Elsässer, T. Friedetzky, T. Götte, L. Hintze, and D. Kaaser

4.4

Eliminating Red Tokens

▶ Lemma 12. Let T0 be the first time when the Approximate has stabilized on the correct value and let T1 ≥ T0 be the first time in which all agents have at most one red token (i.e., logRedv ≤ 0). We define T2 to be the first time at which all red tokens are converted into blue tokens (i.e., logRedv = ⊥). Then w.h.p. T2 − T1 = O(L(G) · log n). Proof. Since at time T1 each node holds at most one red token. For ease of presentation we call the nodes holding a red token red nodes. On a high level, the proof proceeds by dividing the execution into non-overlapping epochs and showing that in every second epoch the number of red nodes decreases by a constant factor with constant probability. Recall that a red node will be able to convert its red token into blue tokens as soon as a node interacts with a node holding a small enough number of blue tokens. Fortunately we are able to show that there is a sufficient number of nodes which can be used for the conversion since agents constantly balance their blue tokens. We partition time into epochs of length 2 · L(G). For i ≥ 0 let ti denote the first step of epoch i, and let R(i) denote the number of red nodes at time ti . For our proof it will be necessary to distinguish between the blue tokens a node has at the beginning of an epoch and the blue tokens it receives due to conversions in that phase. Hence, we refer to the tokens which are on a node at the beginning of an epoch as old blue tokens. Respectively, all blue tokens added in epoch i are new blue tokens. In the following we refer to the set of old blue tokens which are on the nodes at the beginning of epoch i as B ′ (i). Note that we can assume w.l.o.g. that our protocol balances the old blue tokens and the new blue tokens independently. By [8], the old blue tokens from epoch i are balanced at the beginning of epoch i + 1 with constant probability, and the discrepancy is at most 3 . Since the total number of blue tokens generated by Protocol 3 (Balance) is bounded by n · 2b(bcLevel) there are at most n · 2b(bcLevel) old blue tokens. Hence, each node holds at most 2b(bcLevel) + 3 old blue tokens at the end of each epoch. Now consider an arbitrary red node u at time ti+1 , i.e., the beginning of epoch (i + 1). In the following we call a red node good in step t if its number of blue tokens is small enough such that the node is able to convert its red token into blue ones during its next interaction. Formally, node u is good in step t if it holds 2b(bcLevel) or fewer blue tokens in step t. Otherwise we call u blocked in step t. Our goal is to show that R(i + 2) ≤ 23 R(i) for all even i. We now distinguish three cases depending on the number of red nodes R(i + 1). 1. If R(i + 1) ≤ 23 R(i) we are done as the number of red nodes is monotonically decreasing. 2. Suppose R(i + 1) ≥ 23 R(i) and at least half of the red nodes in R(i + 1) are good at time ti+1 . We want to show that these nodes convert their token on their next interaction. For this, they must (still) have less than 2 · 2b(bcLevel) + 3 after their next interaction. By the definition, good red nodes have 2b(bcLevel) or fewer blue token. Further, any other node has at most 2 · 2b(bcLevel) + 3 + 2b(bcLevel) ≤ 3(2b(bcLevel) + 1) blue token in any step. This can be easily verified by contradiction: Let v be the first node with more than 2 · 2b(bcLevel) + 3 + 2b(bcLevel) blue tokens. Suppose that the node received the tokens in Section 4 of Protocol 3. Then, it would have executed the line with more than 2 · 2b(bcLevel) + 3 blue token. This contradicts Section 4 of Protocol 3. Otherwise, if received the tokens in Section 4, either v or its interaction partner must have had 2 · 2b(bcLevel) + 3 + 2b(bcLevel) blue tokens before. Thus, v is not the first node with that

Counting in Population Protocols on Graphs

condition. This contradicts our assumption. Thus, no matter with which node they interact, they are able to convert their red token into blue ones during the next interaction as 1 b(bcLevel) 2 + 3(2b(bcLevel) + 1) ≤ 2 · 2b(bcLevel) + 3. 2 Thus, the node meets the condition of Section 4 and converts the red token. As within L(G) steps each node interacts w.h.p. at least once, again w.h.p. at least 13 R(i) red tokens are eliminated. 3. Suppose R(i + 1) ≥ 23 R(i) and fewer than half of the red nodes in R(i + 1) are good at time ti+1 . In the following we show that this case cannot happen. From the definition of goodness it follows that ≥ 13 R(i) of the red nodes are blocked at time ti+1 and each of them has 2 · 2b(bcLevel) + 3 blue tokens. Since at most 2b(bcLevel) + 3 of these tokens are old blue tokens at time ti+1 and each blocked node has at least 2 · 2b(bcLevel) + 3 blue tokens in step ti+1 , it holds there are b(bcLevel) b(bcLevel) 1 R(i) · 2 · 2 + 3 − (2 + 3) = 13 R(i) · 2b(bcLevel) 3 “new” blue tokens in step ti+1 due to conversions in epoch i. Since each red token is converted to at most 2b(bcLevel) “new” blue tokens, the number of red tokens eliminated during epoch i is at least 1 b(bcLevel) 3 R(i) · 2 2b(bcLevel)

≥ 13 R(i).

This contradicts the assumption that R(i + 1) ≥ 32 R(i). As regards the probability, with constant probability the number of red nodes decreases every two epochs by at least a constant factor. The result follows immediately by considering Θ(log n) epochs and applying Chernoff bounds. ◀

4.5

Balancing Red Tokens

▶ Lemma 13. Let T0 be the first time when protocol Approximate has stabilized on the correct value and let T1 be the first time when all agents have at most one red token (i.e., logRedu ≤ 0). Then w.h.p. T1 − T0 = O(log(n) · L(G)). First we present an overview of our proof. The main idea of the proof is to track the positions of individual red tokens and to bound the time until each token is the sole red token on its host node. P We number the red tokens as integers 1 through k = v 2logRedv (T0 ) . Recall that, if a node u has 2logRedu ≥ 2 tokens and its interaction partner v none at all, the tokens are evenly split between u and v (see lines 2 to 5 in Protocol 3 Balance). We call such an operation a halving step, and model the locations by moving a uniformly random subset of u’s tokens of size 2logRedu −1 from u to v. If, in line 7 of Balance, u and v swap their logRed values, we say that all tokens exchange places, except if logRedu = logRedv , then we only do so with probability 1/2. Under this assignment of locations, every red token, when considered by itself, performs a lazy random walk on the graph until it is converted (see Observation 15). Note that initially

P. Berenbrink, R. Elsässer, T. Friedetzky, T. Götte, L. Hintze, and D. Kaaser

all red tokens are on the same node, and that tokens which are on the same node travel together until they are separated due to a halving step. However, once tokens are on separate nodes, they can never be on the same node again. To prove the theorem we fix a red token i and consider disjoint epochs of length O(L(G)). Now we consider, for each epoch j, the last interaction of token i in epoch j. Our goal is show that there is a constant probability of i being involved in a halving step in exactly that interaction (unless, of course, it has already halved earlier in epoch j). Since in the beginning, if Approximate stabilized on a correct value, there are at most n/c red tokens (for a constant c) i must be alone after log2 n halving steps. It remains to show that for token i the probability of a halving step is constant per epoch. A halving step occurs exactly when the node holding token i interacts with a node not having any red tokens. Since there is only a constant fraction of n/c red tokens (see Observation 10) there must be many such nodes without red tokens. If halving steps only occurred at the end of an epoch, the stacks of red tokens would be distributed (more or less) uniformly among the nodes of the graph by the end of the epoch (see Lemma 17). Hence, it would be straightforward to show that interacting with an empty node would happen with constant probability, and we would be done. The usual method to deal with such situations is to simply assume that, since there are at most n/c red tokens, the worst-case probability to interact during the last step of an epoch with an empty node is still 1 − 1/c. However, stacks of red tokens can be halved at any time during an epoch, and we cannot focus on the last step due to significant dependencies between red tokens which started out on the same node at the beginning of the epoch. We address the problem as follows (see Lemma 14). Let I be the set of red tokens which are, at the start of epoch j, in the same stack of red tokens (at the same node) as token i. Tokens in I stay together until they undergo a halving step. Tokens in I and tokens not in I do not move completely independently at random, since they can never be be at the same node, but they move independently otherwise (we make this precise in Lemma 17). Now let v be the node interacting with the node holding i in the final interaction of the epoch. There are three disjoint cases: v has no tokens at all, v has tokens from I, or v has tokens, but not from I. The first case is easy: there will be a halving step then and there (unless, of course, i is already alone, in which case there must have been a halving step before). In the second case it is easy to see that there has been a halving step before, since the tokens in I are no longer all on the same node. Hence, only the third case is problematic. In this case we bound the probability of a halving step by using the fact that tokens starting at different nodes behave almost independently (again Lemma 17) This allows us to bound the expected number of tokens at v not from I by a constant less than 1. One complication we have omitted so far is that there are also blue tokens on the nodes and red tokens can only be converted into blue tokens if there are not too many of them at the node (lines 12 and 13 in Protocol 3 Balance). This is somewhat annoying to deal with formally, but otherwise unproblematic. Apart from this, the red tokens behave independently of blue tokens, so that it is fine to consider the red tokens by themselves.

Proof of Lemma 13. For each token i, let Tialone ≥ T0 be the first time where i is alone (or converted into blue tokens, if those happen in the same step). As we have logRedv (T0 +τ ) ≤ 0 for all v exactly when all tokens are either alone or have been converted to blue tokens, and tokens must be alone before being converted, we have T1 = maxi∈[k] Tialone . To bound Tialone for a fixed token i, we divide time into disjoint epochs as follows: Let T0,i = T0 , and let, for

Counting in Population Protocols on Graphs

j ≥ 1, Tj,i =

( Tj,i−1 + L(G),

if Wi j,i−1 (T

min{t ≥ Tj,i+1 + L(G) | Wi j,i+1

+L(G))

∈ e(t)},

+L(G))

= ⊥,

otherwise.

Then epoch j is the time interval [Tj−1,i + 1, Tj,i ]. Call epoch j ≥ 1 successful if token i is alone at the beginning of the epoch, if it has been converted into blue tokens by the end of the epoch, or if it has undergone a halving step during the epoch. Let Ei be the index of the ⌊log n⌋th successful epoch for i. Now at time TEi ,i , token i is either alone or has been converted into blue tokens. This is because i becomes alone exactly when it participates in its logRedv (T0 )th halving step: There are 2logRedv (T0 ) ≤ n tokens at i’s position at time T0 (including i), and in general 2logRedv (T0 +τ0 )−j tokens at i’s position after the jth halving step. Hence Tialone ≤ TEi ,i . To bound the latter, by Lemmas 14 and 16 (which we state and prove below), the 1 probability that an epoch is successful is at least 40 − n−6 = Ω(1). And so we have Ei = O(log n) w.h.p. And TEi ,i − TEi ,i − T0 is Ei · L(G) plus the time until a node interacts Ei times. Since Ei ≥ ⌊log n⌋, the time until a node interacts Ei times is in O(nEi ) w.h.p., which is in O(n log(n)) ⊆ O(L(G)) w.h.p. And so TEi ,i − T0,i = O(log(n)L(G)) with probability at least 1 − n−2 . The claim then follows by union bound over all i. ◀ So it remains to state and prove the lemmas referred to in the preceding proof. Throughout, (τ ) we write Wi for the position of token i at time T0 + τ , or ⊥ if token i has been converted into blue tokens at or before time T0 + τ . The following lemma gives two ways to bound from below the probability of a token i being involved in a halving step in some time interval. The idea is to observe the first interaction of i’s location after some fixed time. Then the probability of a halving step occurring at or that interaction can be bounded from below both by the probability of the node holding i interacting with a node having a token which started at a different location from i, or alternatively by the probability of the token having been converted into blue tokens already. ▶ Lemma 14. Fix a sequence of (undirected) edges (e(τ ))∞ τ =τ0 chosen by the scheduler (but not their orientations). Let w ⃗ be a location vector, and let token i be a token that is not alone in w. ⃗ Let T > τ0 + L(G) be the first step in which token i participates in an interaction, and let U be the random variable denoting the interaction partner (or ⊥ if no such interaction exists). Define the following events: EH : token i participates in a halving step in the time interval [τ0 , T ] (T −1) EO : there is a token j with wj ̸= wi and Wj = U ̸= ⊥ Then (τ +L(G))

⃗ (τ0 ) = w] ⃗ (τ0 ) = w], Pr[EH | W ⃗ ≥ max{1 − Pr[EO | W ⃗ Pr[Wi 0

⃗ (τ0 ) = w]}. =⊥|W ⃗ (2)

⃗ (τ0 ) = w Proof. We condition on W ⃗ and the edge sequence throughout. We write I = {j | wj = wi } for the set of tokens sharing a location with i in w ⃗ (including i itself), and O = {j | wj ̸= wi } for the set of tokens not sharing a location with i in w. ⃗ (T ) We define event EI as the event that there is a token j with wj = wi and Wj 1 = U = ̸ ⊥. Furthermore we let Eempty be the event that U is empty at time T −1 (i.e., immediately before (τ +L(G)) the interaction at time T happens). Lastly, we let E⊥ be the event that Wi 0 = ⊥. As tokens from I and tokens from O start at different positions at time τ0 ≤ T , no node v will ever have a token in I and a token in O at time T . So EI and EO are mutually exclusive,

P. Berenbrink, R. Elsässer, T. Friedetzky, T. Götte, L. Hintze, and D. Kaaser

as are all pairings with E⊥ and Eempty by definition of the events. And the only possibility not covered by these four events is that token i is placed at some node, but that node never interacts anymore. But this occurs only with probability 0 for the random scheduler, so we can safely ignore this case. So we have Pr[E⊥ ] + Pr[EI ] + Pr[EO ] + Pr[Eempty ] = 1.

(3)

Now first, as i was not alone at time τ0 , we must have E⊥ ⊆ EH . This is because a token can only be deleted at time τ0 + L(G) if it was alone at a prior time, implying that it must have participated in a halving step in the time interval [τ0 , τ0 + L(G)]. Next, consider Eempty holding. If i is alone at time T , then it must have participated in a halving step since time τ0 (as it was not alone then), so that EH holds. If i is not alone at time T , then it participates in a halving step at time T (since U is empty), so that EH also holds. So Eempty ⊆ EH . Lastly, if EI holds, then at time T there are tokens in I which are on a different node than i ∈ I. This necessarily means that i had participated in a halving step between time τ0 and T (since all tokens in I were at the same node at time τ0 ), so that EI ⊆ EH . This all together implies E⊥ ∪ EI ∪ Eempty ⊆ EH , and so combined with Equation (3) and disjointness of E⊥ , EI , and Eempty we get Pr[EH ] ≥ Pr[E⊥ ] + Pr[EI ] + Pr[Eempty ] = 1 − Pr[EO ] which directly implies the claim.

◀

In order to derive bounds for the right-hand-side of Equation (2), we consider the random walks which are performed by not-yet-converted tokens: When an edge at the node where a token is placed is chosen by the scheduler, the token moves to the other side with probability 1/2, and stays in place otherwise (and perhaps is converted afterwards). More formally, fix the sequence (e(τ ))τ of edges chosen by the scheduler (but not their orientations!), and let M(τ ) ∈ [0, 1]V ×V be the stochastic matrix given by    21 , if {u, v} ∩ e(τ ) ̸= ∅,  ) M(τ 1, if u = v ̸∈ e(τ ), u,v =   0, otherwise. Furthermore, let M[τ1 ,τ2 ] = M(τ1 ) · M(τ1 +1) · · · M(τ2 ) . ▶ Observation 15. Fix an edge sequence (e(τ ))∞ τ =τ0 , fix a token j and two nodes u, v. Then for any τ , (τ )

Pr[Wj

(τ −1)

= v | Wj

= u] ≤ Mu,v ,

and more generally for any τ1 < τ2 (τ )

(τ −1)

Pr[Wj 2 = v | Wj 1

1 ,τ2 ] = u] ≤ M[τ . u,v

Note that the inequalities in Observation 15 would hold with equality, if tokens could not be deleted. Of course, these random walks of different tokens are not independent. The next lemma now bounds the probabilities on the right-hand-side of Equation (2). ▶ Lemma 16. In the setting of Lemma 14, we have 1 1 (τ ) ⃗ (τ0 ) = w], ⃗ (τ0 ) = w]} max{1 − Pr[EO | W ⃗ Pr[Wi 1 = ⊥ | W ⃗ ≥ − −6 . 40 n

Counting in Population Protocols on Graphs

(t ) ⃗ (t0 ) = Proof. Let u = wi be the initial position of token i, and note that Pr[Wi 1 = v | W (t1 ) (t0 ) [t0 ,t1 ] w] ⃗ = Pr[Wi = v | Wi = u] ≤ M for any t1 > t0 (see Observation 15). First, note that by the second display equation in the proof of Corollary 8.3 in the full version of [8] and definition of L(G), for any t0 , we have   2 ⃗ 1 1 [t +1,t0 +L(G)] ≤ 7  ≥ 1 − n−6 , Prmax Mu,·0 − u n n 2

[t +1,t +L(G)]

0 0 and consequently Pr[maxu,v |Mu,v − n1 | ≤ n−3.5 ] ≥ 1 − n−6 . As n ≥ 2, we have −3.5 −2.5 n ≤2 /n < 5/n, so that 1 1 [t0 +1,t0 +L(G)] Pr max Mu,v − ≤ ≥ 1 − n−6 . (4) u,v n 5n

(t )

Now assume that there more than n/2 nodes v for which Pr[Wi 1 = v | Wi 0 = u] < 0.75/n, and let V ′ be the set of such nodes. Then X (t ) (t ) (t ) (t ) Pr[Wi 1 = ⊥ | Wi 0 = u] = 1 − Pr[Wi 1 = v | Wi 0 = u] v∈V

Mu,v −

v∈V

≥

(t )

Pr[Wi 1 = v | Wi 0 = u]

v∈V (t )

(t )

(Mu,v − Pr[Wi 1 = v | Wi 0 = u])

v∈V ′

(Mu,v − (Mu,v − 0.05/n)) − n−6 >

v∈V ′

n 0.05 · − n−6 2 n

1 − n−6 , 40

where the first strict inequality uses Equation (4). (t ) (t ) Otherwise, there are at most n/2 nodes v where Pr[Wi 1 = v | Wi 0 = u] ≥ 0.75/n; let V ′ be the set of such v. Then (t )

(t )

Pr[Wi 1 ∈ V ′ | Wi 0 = u] ≥

3 n 0.75 · = . 2 n 8

And for all u ∈ V ′ , all v ̸= u, and j ∈ O: (t ) (t ) Pr[Wi 1 = u ∧ Wj 1 = v] (t1 ) (t1 ) Pr[Wj = v | Wi = u] = (t ) Pr[Wi 1 = u] (t ) (t ) Pr[{Wi 1 , Wj 1 } ⊆ {u, v}]

≤

0.75/n 4n (t ) (t ) ≤ · Pr[Wi 1 ∈ {u, v}] · Pr[Wj 1 ∈ {u, v}] 3 4n 2.4 2.4 8 ≤ · · < , 3 n n n where the first inequality is by implication and the fact that u ∈ V ′ , and the second inequality is by Lemma 17 (using that j ∈ O), which we state and prove further below due to its technical nature. And so in particular (t )

(t )

max Pr[Wj 1 = v | Wi 1 = u] < v̸=u

8 . n

P. Berenbrink, R. Elsässer, T. Friedetzky, T. Götte, L. Hintze, and D. Kaaser

Now if we continue until the time T of the next interaction involving node u, the position of (t+τ ) (t ) token j is a Markov chain on V \ {u} ∪ {⊥}, and so maxv̸=u Pr[Wj = v | Wi 1 = u] is non-increasing in τ for τ < T . And hence, for all v ̸= u, (T −1)

Pr[Wj

(t )

= v | Wi 1 = u] <

8 . n

So by Markov’s inequality and linearity of expectation, as there are at most n/16 tokens by assumption, (T −1)

Pr[{j ∈ O | Wj

(t )

= v} ≥ 1 | Wi 1 = u] <

1 . 2

By the law of total probability over all possible values of U , and since U ̸= u we then get (T −1)

Pr[{j ∈ O | Wj

(t )

= U } ≥ 1 | Wi 1 = u] <

1 . 2

So then combining the above we get, (T −1)

Pr[{j ∈ O | Wj

= U } ≥ 1] (T −1)

= Pr[{j ∈ O | Wj

(t )

= U } ≥ 1 | Wi 1 ∈ V ′ ] · Pr[Wi 1 ∈ V ′ ]

(T −1)

+ Pr[{j ∈ O | Wj = U } ≥ 1 | Wi 1 ̸∈ V ′ ] · Pr[Wi 1 ̸∈ V ′ ] 1 (t ) (t ) < · Pr[Wi 1 ∈ V ′ ] + 1 · Pr[Wi 1 ̸∈ V ′ ] 2 1 1 (t ) = + · (1 − Pr[Wi 1 ∈ V ′ ]) 2 2 13 1 1 5 ≤ + · = . 2 2 8 16 1 1 −6 This yields the claim as max{1 − 13 } = 40 − n−6 . 16 , 40 − n

◀

The following and final lemma for this section, which we deferred due to its technical nature, is an adaptation of Lemma 5.1 from the full version of [8]. ▶ Lemma 17. Fix the sequence of edges chosen by the scheduler (but not their orientations). Let i = ̸ j be tokens, let w ⃗ be a location vector where wi = ̸ wj . Then for all u = ̸ v and t > t0 : (t)

(t)

⃗ (t0 ) = w] Pr[{Wi , Wj } ⊆ {u, v} | W ⃗ (t)

≤ Pr[Wi

(t) ⃗ (t0 ) = w] ⃗ (t0 ) = w]. ∈ {u, v} | W ⃗ · Pr[Wj ∈ {u, v} | W ⃗

⃗ (t0 ) = w Proof. We condition on W ⃗ throughout and omit writing out this conditioning. Let S = {u, v}. To reduce clutter, we write, for b > a (t)

∈ S | Wi

(t)

∈ S | Wj

Pa(b) = Pr[Wi

(b−1)

= Wi ]

(a)

(b−1)

= Wj ]

and Q(b) a = Pr[Wj

(a)

Let F (τ ) be the filtration revealing the random choices up to time τ , and hence in particular ⃗ (τ ) at time τ . We show below for all τ ∈ [t0 , t] that the locations W h i (τ ) (τ ) +1) E Pτ(τ +1) · Q(τ | F (τ −1) ≤ Pτ −1 · Qτ −1 . (5) τ

Counting in Population Protocols on Graphs

(t+1)

Now Pt

= 1W (t) ∈S and Qt

(t+1)

= 1W (t) ∈S since here, the conditioning is trivial. So the j

claim follows by inductively applying Equation (5): h i (t) (t) (t+1) (t+1) (t +1) (t +1) Pr[{Wi , Wj } ⊆ {u, v}] = E Pt · Qt ≤ Pt0 0 · Qt00 (t)

= Pr[Wi

(t)

∈ S] · Pr[Wj

∈ S],

⃗ t0 where the last equality crucially uses the implicit conditioning ⃗i h on W = w. (τ +1) (τ ) (τ −1) |F So it remains to show Equation (5). Note that E Pτ = Pτ −1 and h i h i (τ +1) (a) (τ ) (a) | F (τ −1) = Qτ −1 by definition, and that E Pτ −1 | F (τ −1) = Pτ −1 and E Qτ h i (a) (a) E Qτ −1 | F (τ −1) = Qτ −1 for any a since the locations of i and j at time τ − 1 are (a)

(a)

determined under F (τ −1) so that Pτ −1 and Qτ −1 are deterministic. We write e(τ ) for the edge chosen by the scheduler at time τ . (τ −1) (τ ) (τ +1) If Wj ̸∈ e(τ ), then j cannot move nor be deleted at time τ , so we have Qτ −1 = Qτ , and hence h i h i (τ ) +1) E Pτ(τ +1) · Q(τ | F (τ −1) = E Pτ(τ +1) · Qτ −1 | F (τ −1) τ h i (τ ) (τ ) (τ ) = E Pτ(τ +1) | F (τ −1) · Qτ −1 = Pτ −1 · Qτ −1 . (τ −1)

And by symmetry, the same holds when Wi ̸∈ e(t). (τ −1) (τ −1) Otherwise we have {Wi , Wj } = e(τ ). In that case, we have ( (τ ) (τ ) (Wi , Wj ) =

(τ −1)

(Wj

(τ −1)

, Wi

)

with probability at most 1/2,

(τ −1) (τ −1) (Wi , Wj )

with probability at most 1/2,

with the remaining probability taken up by cases where at least one of the tokens i and j is deleted, so that they remain deleted until time t and thus the associated random variables are 0. And so h i +1) (τ −1) E Pτ(τ +1) · Q(τ | F τ h i 1 h i 1 (τ +1) (τ +1) (τ +1) (τ +1) ≤ · E Qτ −1 · Pτ −1 | F (τ −1) + · E Pτ −1 · Qτ −1 | F (τ −1) 2h 2 i (τ +1) (τ +1) = E Pτ −1 · Qτ −1 | F (τ −1) (τ +1)

= Pτ −1

(τ +1)

≤

Pτ −1

(τ +1)

· Qτ −1

(τ +1)

+ Qτ −1 2

!2 (τ )

(τ )

= Pτ −1 · Qτ −1 , (τ −1)

where the final equality is because e(τ ) = {Wi

(τ −1)

, Wj

◀

Impossibility of Termination

P. Berenbrink, R. Elsässer, T. Friedetzky, T. Götte, L. Hintze, and D. Kaaser

that it has terminated. We follow the definition by Doty and Eftekhari [19] and augment each node u with a Boolean variable terminatedu that indicates termination. Ideally, this variable would be set to True once the agent has computed the correct value of n, and remain True thereafter, at least with some non-trivial probability. As it turns out, however, this is impossible in our model. More precisely, if the protocol has no a priori knowledge about the underlying graph, then no agent can reliably detect that the correct value of n has been computed, even in the presence of a unique leader. ▶ Theorem 3. Let P be a graph-uniform population protocol that computes the size of an interaction graph. Suppose there is a graph H on which P terminates correctly with positive probability in bounded time tH for some initial configuration. 1. If the protocol starts with a unique leader then there is an infinite sequence of graphs (Gi )i∈N with |V (Gi )| < |V (Gi+1 )| for all i so that the probability of P terminating incorrectly on Gi is constant. 2. Without a unique leader there is an infinite sequence of graphs (G′i )i∈N with |V (G′i )| < |V (G′i+1 )| for all i so that the probability of P terminating incorrectly on G′i is 1 − exp(−Θ(|V (G′i )|)). We actually show something more general: we are not just concerned with protocols computing the exact size of an interaction graph, but even broader properties of the size (like parity, computing a constant-factor approximation of the size of the graph, etc.). Formally, let S be a family of “size properties”, i.e., a family of subsets of N. We say that a protocol computes S if its output function is of the form1 ρ : Q → S, where Q is the state space of the protocol. A configuration of the protocol is called terminated correctly if there exists a terminated agent, and if for all agents having terminatedv = True we have |V | ∈ ρ(qv ) (where qv is the state of v). Examples for families of size properties are Scount = {{n} | n ∈ N} or Sparity = {{2k | k ∈ N0 }, {2k +1 | k ∈ N0 }}. A protocol computing Scount is equivalent to one computing the exact number of nodes, and a protocol computing Sparity is equivalent to one determining parity. We say that a family of size properties is complete if every n ∈ N is contained in some set in said family. Note that for correct termination to be possible for all graphs, S must be complete. We say a family S of size properties is strongly increasing if for all n there are infinitely many n′ > n so that all S ∈ S with n ∈ S do not contain n′ . The sets in S may be overlapping: For example, consider the strongly increasing family consisting of the intervals [max{1, 2k−10 }, 2k+10 ] for k ∈ N. In this example, we may consider the output as an approximation of log(|V |) up to 10. In a correctly configuration with a terminated node, there thus may be different outputs present as long as all are correct. The families Scount and Sparity we gave above are also strongly increasing families. We say that P is given (only) an arbitrary initial leader when its initial set of configurations (v) (v) on a graph G is of the form IG = {⃗i(v) | v ∈ V } ⊆ {q0 , q1 }V , where ⃗iv = q1 , and ⃗iu = q0 for all u ̸= v. So IG consists of the set of all configurations where exactly one agent (the leader) is in q1 and all other agents are in q0 . The following lemmas imply the two parts of Theorem 3 by taking S = Scount . ▶ Lemma 18. Let P be a graph-uniform population protocol given (only) an arbitrary initial leader. Assume P computes a strongly increasing complete family of size properties S. 1

Of course one may consider protocols where not all states have a corresponding output. But since we are concerned only with the output of agents which have terminated, and surely a missing output from a terminated agent would be incorrect, we assume each state having a corresponding output for simplicity.

Counting in Population Protocols on Graphs

Assume there is a graph H and some initial configuration such that P terminates correctly with positive probability in bounded time. Then there is an infinite sequence of graphs (Gi )i∈N with |V (Gi )| < |V (Gi+1 )| so that the probability of P terminating incorrectly on Gi is in Ω(1). Proof. By assumption P terminates on H in at most tH interactions, for some value tH , with some positive probability pH > 0 on some initial configuration ⃗iH in which a leader is given. Note that |E(H)|, tH , and pH are all constants. Let |V (H)| < n1 , n2 , . . . be an infinite sequence such that no S ∈ S contains both n and ni for any i. Such a sequence exists since S is strongly increasing. Now let Gi ̸= H be a (connected) graph of size ni containing H as an induced subgraph (i.e., there is a set VH ⊆ V (Gi ) such that G[VH ] ≃ H),2 such that the cut between H and V (G) \ H contains just a single edge. Let ⃗iGi be the initial configuration which is equal to ⃗iH when restricted to H (so in particular the leader is in the copy of H contained in Gi ). Now consider the subsequence of the first tH interactions of the population protocol on Gi involving at least one node in VH , without regard to who is initiator or responder. This tH subsequence does not contain a node in V (Gi ) \ VH with probability 1 − (|E(H)| + 1)−1 , which is a positive constant independent of ni as |E(H)| and tH are constants independent of ni . Conditioned on this event, from the perspective of the nodes in VH , the execution of the protocol on Gi behaves identically to an execution of the protocol on H, so that v will have terminated with an output ρ(qv ) ∋ |V (H)| with probability ≥ pH . So the overall probability of this termination is in Ω(1). But since Gi is of size ni , we must have |V (Gi )| = ni ̸∈ ρ(vq ), so the termination was incorrect. ◀ ▶ Lemma 19. Let P be a graph-uniform population protocol with all agents initialized to a fixed initial state q0 computing a strongly increasing complete family of size properties S. Assume there there is a graph H on which P terminates correctly with positive probability in bounded time. Then there is an infinite sequence of graphs (Gi )i∈N with |V (Gi )| < |V (Gi+1 )| so that the probability of P terminating correctly on Gi is exp(−Θ(|V (Gi )|)). Proof. We let H, tH , pH , ⃗iH , and the n1 , n2 , . . . be defined as in the proof of Lemma 18. We now define Gi as follows: Let ki = ⌊(ni − 1)/|V (H)|⌋. Then to a clique of ni − ki · |V (H)| nodes, connect ki disjoint copies H1 , . . . , Hki of H by a single edge each (in an arbitrary way) so that indeed Gi has ni nodes. We consider an initial configuration ⃗iGi on Gi so that it is equal to ⃗iH when restricted to any of the copies H1 , . . . , Hki . The k subsequences of interactions involving at least one node in the copies H1 , . . . , Hk are disjoint, so the events whether the prefixes of length tH contain the edge to the central clique are independent. The probability of this edge not being present in a single given t −1 H subsequence is 1 − (|E(H)| + 1) , which is a constant independent of ni since |E(H)| and tH are constants. As in the proof of Lemma 18, conditioned on this event, from the perspective of the nodes in the respective copy of H, the execution of the protocol on Gi behaves identically to an execution of the protocol on H, so that v will have terminated with an output ρ(qv ) ∋ |V (H)| with probability ≥ pH . So for a fixed copy of H, the overall probability of such a termination is bounded from below by a positive constant cH . But since Gi is of size ni , we must have |V (Gi )| = ni ̸∈ ρ(vq ), so that such a termination is incorrect in Gi . 2

To spell it out, there is an injective function ϕ : V (H) → V (G) such that {ϕ(u), ϕ(v)} ∈ E(G) if and only if {u, v} ∈ E(H).

P. Berenbrink, R. Elsässer, T. Friedetzky, T. Götte, L. Hintze, and D. Kaaser

So for the protocol to terminate correctly on Gi , it must be the case that none of the ki copies of H in Gi have such a termination, which happens with probability at most k (1 − cH ) i . Now ki = Θ(ni /|V (H)|) = Θ(ni ) as |V (H)| is independent of ni . that this probability is in exp(Θ(ni )), as claimed. ◀

Generating Independent Random Bits

In this section we present the full analysis of our protocol for generating random bits. For sake of readability we restate the definitions from Section 2.4 before we give the proof. Our final result is a uniform protocol for generating independent, fair, unbiased random bits. These bits will be used as a basic primitive in our counting protocol. While it is not surprising that such a protocol exists, we are not aware of a rigorous analysis; thus, we provide one here. Just as all other protocols (we are aware of) for sampling bits in graphical population protocols [3, 4], our protocol derives randomness from the orientation of the edge selected by the scheduler in each step. Instead of using static coloring as in [25] to decide which of the two interaction partners may use the random bit implied by the direction, our protocol uses dynamic 2-coloring to produce a non-monochromatic edge with constant probability. In a nutshell, the protocol works as follows. Each node u maintains a color, either black or white, stored in the field coloru . Whenever nodes u and v interact and have different colors, the black node generates a random bit. Suppose that u is black. Then the bit is stored in the field randu , taking value 1 if u is the initiator, i.e., if the scheduler activated edge (u, v), and value 0 otherwise. The white node v sets randv to ⊥, meaning that it created no random bit in this interaction. If both endpoints have the same color, the corresponding values randu and randv are both set to ⊥. At the end of the step, the colors of u and v are updated to black and white, respectively. Protocol 4. GenerateRandomBit(u, v) 1 2 3 4 5 6 7

▶ The black node u is initiator, assign bit 1 ▶ The black node v is responder, assign bit 0

We now prove the following theorem, stating that the protocol produces unbiased, independent random bits and within a moderate time each node receives a large number of random bits. ▶ Theorem 4. Let T be an arbitrary step and assume that node u interacts in steps Tu ⊆ [T ]. For tj ∈ Tu , let Ru (tj ) be the value of randu ∈ {0, 1, ⊥} at the end of the interaction in step tj . For node u, define Ru′ (T ) = {Ru (ti ) | Ru (ti ) ∈ {0, 1}, ti ∈ Tu }. 1. For all R(ti ) ∈ Ru′ (T ) we have Pr[Ru′ (ti ) = 1] = Pr[Ru′ (ti ) = 0] = 21 . S 2. All variables in v∈V Rv′ (T ) are mutually independent.

Counting in Population Protocols on Graphs

3. For any step t ≥ 1, each node u generates a random bit in steps [t, t + 4|E(G)|/δ(G)] with probability at least 1/96. This probability is independent for non-overlapping time intervals. The remainder of this section contains the proof of Theorem 4 and various necessary technical lemmas, claims and observations. Before we present the formal proofs, we make the underlying probability space texplicit. ⃗ The scheduler determines a sequence of directed edges M (t) ∈ (a, b) | {a, b} ∈ E . Here, (a, b) denotes an interaction in which node a is the initiator and node b is the responder. Each element M (i) = (ai , bi ), for i ∈ [t] is drawn uniformly at random from the set of all directed edges obtained by replacing each undirected edge {a, b} ∈ E with the two arcs (a, b) and (b, a). For an easier notation when we condition on the sequence m(t) ⃗ of all random choices until step t, write h i ⃗ (t) = m(t) Pr [·] = Pr · | M ⃗ . (6) m(t) ⃗

Recall that per assumption, all choices of the scheduler are independent. Therefore, for each step t, directed pair (a, b) ∈ E, and sequence m(t ⃗ − 1) ∈ E t−1 , it holds Pr [M (t) = (a, b)] = Pr[M (t) = (a, b)] = m(t−1) ⃗

1 . 2|E|

(7)

For the analysis of our theorem, we furthermore define the following random variables: Bu (t) ∈ {0, 1} is the indicator that u is black at the beginning of step t. Wu (t) ∈ {0, 1} id the indicator that u is white at the beginning of step t. Su (t) ∈ {0, 1} is the indicator that u is black and interacts with a white node in step t. Having these definitions out of the way, we begin with the analysis. We divide the analysis into three parts, one for each of the three properties of Theorem 4. In Section 6.1, we show that the sampled bits are uniformly distributed in {0, 1}, i.e., we show the first property. Then, in Section 6.2, we prove the second property and show that the sampled bits are independent. Finally, we show the third property in Section 6.3 and furthermore prove that this property implies that each node samples many bits within O(|E(G)|/δ(G) log n) steps.

6.1

Bits are Uniform

In this section we show the first statement of Theorem 4. In fact we show a slightly stronger statement that we will reuse for the other proofs. We show that, given the entire history of the protocol up to step t, the following holds: If a random bit is chosen in step t, then the probability that the random bit is 0 or 1 is uniform. Formally: ▶ Lemma 20. Fix a node u and a step t ≥ 1. Let m(t ⃗ − 1) be a sequence of t − 1 directed edges, s.t., it holds Pr [Su (t) = 1] > 0. Then, m(t−1) ⃗

Pr [randu (t) = 1 | Su (t) = 1] = Pr [randu (t) = 0 | Su (t) = 1] = 12 .

m(t−1) ⃗

Proof. Recall that Su (t) indicates that u is black, and we know that at the beginning of step t it has at least one white neighbor. On a high level, we want to show that conditioning on u being black and any neighbor being white does not affect the probability of drawing a

P. Berenbrink, R. Elsässer, T. Friedetzky, T. Götte, L. Hintze, and D. Kaaser

certain bit. For each v ∈ V , the variables Bv (t) and Wv (t) can be expressed as functions of m(t ⃗ − 1). Formally, there is a function: ( fB,u (m(t ⃗ − 1)) =

if Bu (t) = 1,

else.

We only prove this for Bu (t), as if a node is not black, it is white. Hence, if Bu (t) is a function of M (t − 1), so is Wu (t). Node u is black exactly when u was the initiator in its last interaction before step t (if such an interaction exists). Let τu (m(t ⃗ − 1)) =

( max{i < t | m(i) = (a, b), u ∈ {a, b}} ⊥

if such i exists, else.

For readability, denote τu (m(t ⃗ − 1)) simply as τ . With definition , it easy to verify that

1{m(τ ) = (u, a)} if τ ̸= ⊥,

( Bu (t) = fB,u (m(t ⃗ − 1)) =

else.

Thus, Bu (t) is completely decided by m(t ⃗ − 1) as claimed. We now define the set of white neighbors of u at the beginning of step t as Nuw (m(t ⃗ − 1)) = {v ∈ Nu | fB,v (m(t ⃗ − 1)) = 0}. Note that, just as Bv (t) and Wv (t), this set is fixed given m(t ⃗ − 1). Further, note that |Nuw (m(t−1))| ⃗ ≥ 1 as we conditions on an m(t−1) ⃗ where Pr [Su (t) = 1] ≥ 0 and, therefore, m(t−1) ⃗

u has at least one white neighbor. We now describe the events {randu (t) = 1} and {Su (t) = 1} with respect to the random choice in step t. Conditioned on m(t ⃗ − 1), event Su (t) = 1 occurs precisely if M (t) = (at , bt ) w with either at = u and bt ∈ Nu (m(t ⃗ − 1)), or bt = u and at ∈ Nuw (m(t ⃗ − 1)). Hence, X Pr [Su (t) = 1] = Pr [M (t) = (u, v)] + Pr [M (t) = (v, u))] . m(t−1) ⃗

v∈Nuw (m)

m(t−1) ⃗

Since the edge sampled in step t is independent of m(t ⃗ − 1) and each orientation of each edge is chosen with probability 1/(2|E|), we obtain Pr [Su (t) = 1] =

m(t−1) ⃗

(Pr[M (t) = (u, v)] + Pr[M (t) = (v, u))])

v∈Nuw (m)

X v∈Nuw (m)

1 1 + 2|E| 2|E|

|Nuw (m(t ⃗ − 1))| . |E|

On the other hand, randu (t) = 1 occurs precisely when M (t) = (u, v) for some v ∈ Nuw (m). Thus, X Pr [randu (t) = 1] = Pr [M (t) = (u, v)] m(t−1) ⃗

v∈Nuw (m(t−1)) ⃗

X v∈Nuw (m(t−1)) ⃗

m(t−1) ⃗

Pr[M (t) = (u, v)] =

|Nuw (m)| . 2|E|

Counting in Population Protocols on Graphs

Since the event {randu (t) = 1} is included in the event {Su (t) = 1}, we have {randu (t) = 1} ∩ {Su (t) = 1} = {randu (t) = 1}. By the definition of conditional probability we conclude Pr [{randu (t) = 1} ∩ {Su (t) = 1}]

Pr [randu (t) = 1 | Su (t) = 1] =

m(t−1) ⃗

Pr [Su (t) = 1]

m(t−1) ⃗

Pr [randu (t) = 1]

m(t−1) ⃗

Pr [Su (t) = 1]

m(t−1) ⃗

|Nuw (m(t−1))| ⃗ 2|E| Nuw (m(t−1)) ⃗ |E|

1 . 2

◀

By using the law of total probability, this proves the first statement of the theorem and shows that the distribution of each individual bit uniform.

6.2

Bits are Independent

In this section we show the second statement of Theorem 4. More precisely, we formally show that all the generated bits are independent of each other. Intuitively, this follows because the value is determined by orientation of the edge in step t and this orientation is used only for one random bit (with other node receiving ⊥ in the step). Given that the orientations of edges in different steps are independently chosen by the scheduler, the independence of our bit follows. To make it more formal, we will show that in any possible order which the bits are picked, they are always independent of past and future bits. Intuitively, we will show that, given that in step t where are all previous random bits match a fixed bitstrings, the probability that the next bit matches is 12 . This is true because the distribution of each new bit is uniform independent of the entire processes’ history including all previously sampled bits. This follows directly from Lemma 20. Given this intuition, we now want show it formally in the following lemma ▶ Lemma 21. For each u ∈ V and ℓ ≥ 1, let Ru (ℓ) ∈ {0, 1} be the ℓ-th bit sampled by u. Then all random variables (Ru (ℓ))u∈V,ℓ≥1 are independent and uniformly distributed. Proof. We prove that every finite collection of sampled bits is independent and uniformly distributed. For each agent u ∈ V , let su ≥ 0 be an integer, and fix an arbitrary bitstring bu (1), . . . , bu (su ) ∈ {0, 1} of length su . For each agent u and step t, let Su (t) ∈ {0, 1} indicate Pt whether u samples a bit in step t, and let Su (t) = τ =1 Su (τ ) be the number of bits sampled by u up to step t. For each u ∈ V and step t, define the indicator   1 if Su (t) > su ,    1 if S (t) = 0, u Yu (t) =  1 if Su (t) = 1 and Ru (Su (t)) = bu (Su (t)),     0 otherwise. Thus, Yu (t) = 0 only if u samples one of the first su bits in step t and this bit does not match the prescribed bitstring. Once u has already sampled more than su bits, we always Q Qt set Yu (t) = 1. Furthermore, define Z(t) = u∈V τ =1 Yu (τ ). Then Z(t) = 1 if and only if all relevant bits sampled up to step t match their prescribed bitstrings, that is, Z(t) = 1 if and only if for all u ∈ V and all j ≤ min{Su (t), su }, it holds that Ru (j) = bu (j). Let T be the first step at which P every agent u has sampled at least su bits. It is enough to −

u u∈V show that Pr[Z(T ) = 1] = 2 . Indeed, since the integers su and the target bits bu (j) were chosen arbitrarily, this implies that every finite collection of sampled bits is independent and uniformly distributed.

P. Berenbrink, R. Elsässer, T. Friedetzky, T. Götte, L. Hintze, and D. Kaaser

P min{Su (t),su } To this end, for every t ≥ 0 define Z ′ (t) = 2 u∈V · Z(t) Given this definition, we prove the stronger statement that, for every t ≥ 0, E[Z ′ (t)] = 1.

(8)

Applying this statement at time T , we have min{Su (T ), su } = su for every u ∈ V . Therefore, P P h P i s s s 1 = E[Z ′ (T )] = E 2 u∈V u Z(T ) = 2 u∈V u · E[Z(T )] = 2 u∈V u · Pr[Z(T ) = 1]. Note that the last equality follows since Z(T ) ∈ {0, 1} is an indicator. Thus, solving the previous for Pr[Z(T ) = 1] gives P − su u∈V Pr[Z(T ) = 1] = 2 . This proves that every finite collection of sampled bits is independent and uniformly distributed. It remains to prove Equation (8). We will the statement by induction on t. For t = 0, this is immediate, since Z(0) = 1 and Su (0) = 0 for all u ∈ V . Now assume that the statement holds for t − 1. Let V ⋆ (t) = {u ∈ V : Su (t − 1) < su } be the set of agents that have not yet sampled all their prescribed bits before step t. Then, it easy to verify that it holds Y Z ′ (t) = Z ′ (t − 1) · 2Su (t) Yu (t). u∈V ⋆ (t)

⃗ (t − 1) = m In the following, we condition on the full configuration M ⃗ before step t. By the law of total expectation,   i X h Y ⃗ (t − 1) = m E[Z(t)] = Pr M ⃗ · EZ(t − 1) · 2Su (t) Yu (t) m ⃗

m ⃗

u∈V ⋆ (t)

 =

X m ⃗

⃗ (t − 1) = m Pr M ⃗ · E[Z(t − 1)] · E m ⃗

m ⃗

 Y

2Su (t) Yu (t).

u∈V ⋆ (t)

The second equality follows as Z ′ (t − 1) is completely determined by m ⃗ and therefore E[Z(t − 1)] is a constant and not a random variable. It remains to evaluate the last m ⃗

conditional expectation. By assumption, in each step at most one agent samples a bit, so P ⋆ u∈V ⋆ (t) Su (t) ∈ {0, 1}. If no agent in V (t) samples a bit in step t, then Su (t) = 0 and Q Yu (t) = 1 for all u ∈ V ⋆ (t), and therefore u∈V ⋆ (t) 2Su (t) Yu (t) = 1. Otherwise, there is a ⃗ (t − 1) = m unique agent u⋆ ∈ V ⋆ (t) with Su⋆ (t) = 1. Conditioned on M ⃗ and on the event that u⋆ samples a bit in step t, the sampled bit is uniform and independent of all previously sampled bits. Thus, by Lemma 20, it holds Pr [Ru⋆ (Su⋆ (t)) = bu⋆ (Su⋆ (t)) | Su⋆ (t) = 1] =

m(t) ⃗

1 . 2

Consequently, h i 1 E 2Su⋆ (t) Yu⋆ (t) | Su⋆ (t) = 1 = 2 · = 1. m ⃗ 2 All other factors in the product are equal to 1. Hence, in both cases,   Y E 2Su (t) Yu (t) = 1. m ⃗

u∈V ⋆ (t)

Counting in Population Protocols on Graphs

Plugging this back into the previous display gives E[Z(t)] =

 h i Y ⃗ (t − 1) = m Pr M ⃗ · E[Z(t − 1)] · E m ⃗

m ⃗

 2Su (t) Yu (t)

u∈V ⋆ (t)

h i ⃗ (t − 1) = m Pr M ⃗ · E[Z(t − 1)] = E[Z ′ (t − 1)] = 1. m ⃗

m ⃗

◀

where the last equality follows from the induction hypothesis.

6.3

Bits are Sampled Frequently

In this section, we prove the third statement of Theorem 4 and show that each node will regularly generate new random bits. Recall that this property is crucial as, up until now, we only argued that all bits a node gets are unbiased but never argued that it will actually get bits. To conclude our analysis of Theorem 4, we therefore show the following lemma. ▶ Lemma 22. For each node, let Tu be expected time in which the node interacts once on |E| expectation, i.e., Tu = |N . Further, let T = maxu∈V Tu = |E(G)| δ(G) . Fix a step t. Then, for u| t any m ∈ E , it holds: "t+4T # X 1 ′ ⃗ . Pr Sv (t ) > 0 | M (t) = m(t) ⃗ ≥ 96 ′ t =t

Proof. For easier notation, we assume w.l.o.g. that the process starts in step 0 and omit ⃗ (t) = m(t)}. the conditioning on {M ⃗ For each x ∈ Nv and each step t ≥ 0, let Wx (t) and Bv (t) be the indicators that x is white and v is black in step t, respectively. Further, let Ax (t) ∈ {0, 1} be the indicator that x interacts in step t. Then " 4T # " 4T # X X X E Sv (t) = E (Av (t) · Ax (t)) · (Bv (t) · Wx (t)) (9) t=0 x∈Nv

t=0

4T X X

E[Av (t) · Ax (t)] · E[Bv (t) · Wx (t)]

(10)

t=0 x∈Nv 4T

1 X X E[Bv (t) · Wx (t)]. |E| t=0

(11)

x∈Nv

Here, Equation (9) follows from the definition of Sv (t), Equation (10) follows because the scheduler chooses the interacting pair independently of the colors, and Equation (11) follows since every edge is picked uniformly at random. By Lemma 23 (that we will show below), for all t ≥ 2T and all x ∈ Nv , we have Pr[Bv (t) · Wx (t) = 1] ≥ 18 . Hence, using only the interval {2T , . . . , 4T − 1}, we obtain " 4T # 4T −1 X 1 X X 1 1 |Nv | E Sv (t) ≥ Pr[Bv (t) · Wx (t) = 1] ≥ · 2T · |Nv | · = , (12) |E| |E| 8 4δ t=0 t=2T x∈Nv

where we used T = |E|/δ. It remains to lower-bound the probability that at least one such successful interaction occurs. Define X=

4T −1 X t=2T

Sv (t)

and

Y =

4T −1 X t=2T

Av (t)

P. Berenbrink, R. Elsässer, T. Friedetzky, T. Götte, L. Hintze, and D. Kaaser

as the number of steps in this interval in which v samples a bit and interacts respectively. Since v independently interacts in any fixed step with probability |Nv |/|E|, this means that Y is binomially distributed. Therefore, E[Y ] = 2T

|Nv | |Nv | =2 |E| δ

and Var[Y ] = 2T

|Nv | |E|

|Nv | 1− |E|

|Nv | |Nv | =2 1− < E[Y ]. δ |E|

Using the definition of variance, we get |Nv | |Nv |2 2 2 E Y 2 = Var[Y ] + E[Y ] ≤ E[Y ] + E[Y ] = 2 +4 2 . δ δ Recall X ≤ Y because every successful sampling requires an interaction. Furthermore, both X and Y are non-negative. This implies E X 2 ≤ E Y 2 and therefore |Nv | |Nv |2 +4 2 . E X2 ≤ E Y 2 ≤ 2 δ δ

(13)

Finally, note that X ≥ 0 and X has finite variance. Then, by the Paley-Zygmund inequality (see Theorem 27) , applied with threshold 0, " 4T # " 4T # X X Pr Sv (t) > 0 ≥ Pr Sv (t) > 0 = Pr[X > 0] t=0

t=2T 2

≥

|Nv | 4δ

|N |

v E[X] 1 δ = ≥ ≥ . 2 |Nv | |Nv | |Nv | E[X 2 ] 96 2 +4 2 32 + 64

◀

This proves the lemma, assuming Lemma 23. ▶ Lemma 23. For all t ≥ 2T and all x ∈ Nv , it holds that Pr[Wx (t) · Bv (t) = 1] ≥

1 . 8

Proof. For each agent y ∈ V and each step t > 0, define t⋆y as the last step before t in which y was active, or ∞ if y was inactive in all steps before t: ( max{t′ ∈ {0, . . . , t − 1} : Ay (t′ ) = 1} if such a step exists, ⋆ ty = ∞ otherwise. Let T = {t⋆v ̸= ∞, t⋆x = ̸ ∞} be the event that both v and x have interacted at least once before step t. First, we lower-bound the probability of T. For a fixed node u, the probability that it does not interact during the first 2T steps is 2T 2T 2T |Nu | δ 1 1− ≤ 1− = 1− ≤ e−2 . |E| |E| T Thus, by the union bound, for every t ≥ 2T , Pr[T] ≥ 1 − Pr[t⋆v = ∞] − Pr[t⋆x = ∞] ≥ 1 − 2e−2 ≥

1 . 2

(14)

Counting in Population Protocols on Graphs

Conditioned on T, the last interaction of v before step t determines its current color. In this last interaction, v is the initiator with probability 1/2. Hence Pr[Bv (t) = 1 | T] =

1 . 2

(15)

Here, we used T and therefore t⋆x and t⋆v are only determined by the interaction pairs until step t but not the initiators and responders. It remains to lower-bound the probability that x is white, conditioned on v being black and on T. If t⋆x = t⋆v , then the last interaction of both nodes was their mutual interaction. Since v is black in that interaction, x is white with probability 1. Otherwise, if t⋆x ̸= t⋆v , then the last interaction of x is different from the last interaction of v, and x is white with probability 1/2. Therefore Pr[Wx (t) = 1 | Bv (t) = 1, T] = Pr[t⋆x = t⋆v | Bv (t) = 1, T] · 1 + Pr[t⋆x ̸= t⋆v | Bv (t) = 1, T] ·

1 1 ≥ . 2 2

(16)

Combining Equation (14), Equation (15), and Equation (16), we get Pr[Wx (t) · Bv (t) = 1] ≥ Pr[T] · Pr[Bv (t) = 1 | T] · Pr[Wx (t) = 1 | Bv (t) = 1, T] 1 1 1 1 ≥ · · = . 2 2 2 8 This proves the lemma.

◀

Finally, we show that the third property of Theorem 4 implies that, w.h.p., all nodes will nodes will repeatedly sample unbiased and independent random bits. Formally, we show the following corollary. ▶ Corollary 5. Let ℓ ≥ 1 be an integer. 1. In O |E(G)| δ(G) · ℓ steps, a node u draws at least ℓ random bits with probability at least 1 − 2−ℓ . · ℓ steps, each node draws at least ℓ random bits with 2. For ℓ ≥ (c + 1) log n, in O |E(G)| δ(G) probability at least 1 − n−c . Proof. First, we note that the second statement follows directly from the first. Assume that the first statement holds. Choosing ℓ = (c + 1) log n gives each node u a probability of at least 1 − e−ℓ = 1 − n−(c+1) to sample ℓ bits. Thus, with probability at most n−(c+1) , node u samples less than ℓ bits. Denote this event by Fu . Note that the events (Fu )u∈V are not independent. However, by the union bound, the probability that any of these n events happens is at most n1c . Therefore, it is sufficient to prove the first statement. For the proof, fix an agent u. We divide the time into non-overlapping phases of length 4|E(G)|/δ(G). More iprecisely, for each i ≥ 1, phase i consists of the steps h |E(G)| (i − 1) · 4 |E(G)| δ(G) , i · 4 δ(G) − 1 . We show that within L = 96Cℓ phases, where C ≥ 4 is a

sufficiently large constant, agent u samples at least ℓ bits with probability at least 1 − e−ℓ . For each phase i ∈ {1, . . . , L}, let Xi ∈ {0, 1} be the random variable that indicates whether u successfully samples a bit in phase i. If Xi = 1, we call phase i successful. Since each successful phase produces at least one random bit, the number of successful phases is a PL lower bound for the number of sampled bits. It remains to show that X = i=1 Xi ≥ ℓ with probability at least 1 − e−ℓ . As each phase has length 4|E(G)|/δ(G), the total number of steps is in O(ℓ |E(G)| δ(G) ), which proves the statement.

P. Berenbrink, R. Elsässer, T. Friedetzky, T. Götte, L. Hintze, and D. Kaaser

By property (3) of Theorem 4, for every possible configuration m ⃗ at the beginning of 1 phase i the probability of success is at least 96 . Thus, we have for every i ≥ 1 and every vector (xi−1 , . . . , x1 ) ∈ {0, 1}i−1 that E[Xi | Xi−1 = xi−1 , . . . , X1 = x1 ] ≥ Moreover, this implies "L # Y 1 E Xi ≥ ( )L 96 i=1

1 . 96

and

E[X ] =

L X

E[Xi ] ≥

i=1

L = Cℓ. 96

Although the random variables X1 , . . . , XL are not independent, the conditional lower bound above is sufficient to apply the multiplicative Chernoff bound with µ = Cℓ as our variables 1 . Hence, for every α ∈ (0, 1), dominate Bernoulli distributed values with parameter p = 96 α2 Cℓ Pr[X ≤ (1 − α)Cℓ] ≤ exp − . 2 L = C1 · Cℓ = ℓ. Thus, If we choose α = 1 − C1 , we have (1 − α) 96

1 − C1 Pr[X ≤ ℓ] ≤ exp − 2

Cℓ

! .

(1− C1 ) C For every C ≥ 4, we have ≥ 1, it holds, Pr[X ≤ ℓ] ≤ e−ℓ . as desired. Since the 2 number of successful phases is a lower bound for the number of bits sampled by u, it follows that u samples at least ℓ bits within L = 96Cℓ phases with probability at least 1 − e−ℓ . This proves the first statement and the corollary. ◀

Baseline: Space-Efficient Uniform Counting

In this appendix we present UniformCounting, a simple uniform population protocol that counts the population within O(H(G) · n log n) interactions. Recall that H(G) denotes the maximal hitting time of a random walk on G. The protocol is a direct extension of the leader-election protocol of Beauquier, Blanchard, and Burman [7]. For its analysis, we use results of Alistarh, Rybicki, and Voitovych [4]. At a high level, UniformCounting works as follows. Each agent is either active or inactive, as indicated by the field active ∈ {0, 1}. An active agent holds one or more tokens and stores its current token count. An inactive agent holds no tokens and stores a the highest number of tokens it observed so far. We represent both quantities by a positive integer field val. The meaning of this field depends on whether the agent is active or inactive. For an active agent, val is its current token count. For an inactive agent, val is its current estimate, which is propagated using the maximum rule described below. In either case, the output of an agent u is valu . Thus, the protocol stabilizes when {valu = n} for every u ∈ V . Initially, every agent is active and holds exactly one token. The transition rules are as follows. Suppose that two active agents u and v, holding valu and valv tokens, respectively, interact, and assume without loss of generality that u is the initiator. Agent v transfers all its tokens to u and becomes inactive. After the interaction, u is active with value valu + valv , while v is inactive with the same value valu + valv .

Counting in Population Protocols on Graphs

If two inactive agents u and v, storing values valu and valv , respectively, interact, both update their stored value to max{valu , valv }. Suppose that an active agent u, holding valu tokens, interacts with an inactive agent v, storing value valv . The agents exchange roles: agent v becomes active and receives the valu tokens held by u, while u becomes inactive. After the interaction, v stores the previous value valu , while u stores max{valu , valv }. Protocol 7 UniformCounting(u, v) 1

2 3 4

5 6

7 8 9

10 11 12

m ← max{valv , valu } if activeu = activev = 1 then ▶ If both are active, move all tokens to the initiator (activeu , activev ) ← (1, 0) (valu , valv ) ← (valv + valu , valv + valu ) else if activeu = activev = 0 then (valu , valv ) ← (m, m)

▶ If both are inactive, propagate the largest value

else if activeu = 1 ▶ Otherwise, swap states and propagate largest value to inactive agent (activeu , activev ) ← (activev , activeu ) (valu , valv ) ← (m, valu ) else (activeu , activev ) ← (activev , activeu ) (valu , valv ) ← (valv , m) output function: ρ(activeu , valu ) = valu

7.1

Analysis of UniformCounting

We now analyze UniformCounting and prove the following theorem. ▶ Theorem 24. UniformCounting is a uniform population protocol using O(n) states on populations of size n such that, on every connected interaction graph G = (V, E) with |V | = n, all agents eventually stabilize to output n. Moreover, with high probability, stabilization occurs within O(H(G) · n log n) interactions. Proof. We first establish correctness. The protocol maintains the invariant that the token counts of all active agents sum to n. This invariant holds initially because every agent holds one token. An interaction between two active agents transfers tokens between them but neither creates nor destroys any tokens. An interaction between an active and an inactive agent only moves an existing collection of tokens from one agent to another. Finally, an interaction between two inactive agents does not affect any tokens. Hence, every transition preserves the invariant. An interaction between two active agents decreases the number of active agents by one. Every other interaction leaves the number of active agents unchanged. Thus, the number of active agents never increases. It can never become zero, because the active agents collectively hold all n tokens. Consequently, once only one active agent s remains, the invariant implies that s holds all n tokens and therefore stores the value n. From that point onward, the value n spreads as an epidemic. Call an agent informed if its stored value is n. If two inactive agents interact and one of them is informed, the maximum rule makes both agents informed. If the active agent interacts with an inactive agent, then the active agent transfers all n tokens to the inactive agent and stores n upon becoming inactive. Thus, both agents are informed after the interaction. In particular, once

P. Berenbrink, R. Elsässer, T. Friedetzky, T. Götte, L. Hintze, and D. Kaaser

only one active agent remains, an informed agent can never become uninformed. Because G is connected and every edge is selected infinitely often with probability one, every agent is eventually informed. Hence, all agents eventually stabilize to output n. We next bound the time complexity. We use Claim 25, which is proved immediately after this theorem. By Claim 25, with high probability a unique active agent s remains within O(H(G) · n log n) interactions. As argued above, this agent stores the value n. The epidemic then informs every agent within an additional O(B(G)) interactions, with high probability. Once all agents store n, every subsequent transition preserves their outputs, so the protocol has stabilized. Using the standard inequality B(G) ≤ H(G), the dissemination time is dominated by O(H(G) · n log n). Finally, we establish the state complexity. Each agent stores the bit active, indicating whether it is active or inactive, and a positive integer val. No value reachable in an execution on n agents can exceed n. Indeed, by the token invariant, an active agent never holds more than n tokens. Moreover, every value stored by an inactive agent is equal to a token count held by an active agent at the same or an earlier interaction. This property follows by induction over the interactions. An active–active interaction assigns the newly inactive agent the new token count of the surviving active agent, while the other two rules either copy an active token count or retain the maximum of two previously stored estimates. Therefore, the value of an inactive agent cannot exceed n either. It follows that, on a population of size n, every reachable state consists of one bit and one value in [1, n]. Thus, at most 2n states are reachable. The transition rules themselves do not depend on n, so the protocol is uniform. Together with Claim 25, this completes the proof. ◀

We now prove the claim used in the time analysis. ▷ Claim 25. With high probability, exactly one active agent remains after O(H(G) · n log n) interactions. Proof. Consider the leader-election protocol of Beauquier, Blanchard, and Burman [7], together with the analysis of Alistarh, Rybicki, and Voitovych [4]. In that protocol, every agent is initially black. When two black agents interact, the initiator remains black and the responder becomes white. When a black agent and a white agent interact, they exchange colors. An interaction between two white agents does not change their colors. We couple the two protocols by using the same sequence of ordered interactions and identifying active agents with black agents and inactive agents with white agents. Initially, this correspondence holds because every agent is both active in our protocol and black in the leader-election protocol. An active–active interaction has the same effect on activity statuses as a black–black interaction has on colors. Similarly, an active–inactive interaction swaps the two activity statuses, just as a black–white interaction swaps the two colors. Finally, neither an inactive–inactive interaction nor a white–white interaction changes the corresponding statuses. The correspondence therefore holds after every interaction. It follows that the number of active agents in our protocol is always equal to the number of black agents in the leader-election protocol. The analysis in [4] shows that, with high probability, only one black agent remains after O(H(G) · n log n) interactions. Therefore, with high probability, exactly one active agent remains after the same number of interactions. ◀

REFERENCES

Tools from Probability Theory

▶ Theorem 26 (Chernoff bound ). Let X1 , . . . , Xn be independent Bernoulli random variables, Pn and define X = i=1 Xi and µ = E[X]. For every 0 < δ < 1, Pr[X ≤ (1 − δ)µ] ≤

e−δ (1 − δ)1−δ

2 δ µ ≤ exp − . 2

▶ Theorem 27 (Paley–Zygmund inequality). Let Z ≥ 0 be a random variable with finite variance. Then, for every θ ∈ [0, 1], 2

Pr[Z > θ · E[Z]] ≥ (1 − θ)2 ·

E[Z] . E[Z 2 ]

References [1] D. Alistarh, J. Aspnes, D. Eisenstat, R. Gelashvili, and R. L. Rivest. “Time-Space Trade-offs in Population Protocols.” In: Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA. 2017, pp. 2560–2579. [2] D. Alistarh, J. Aspnes, and R. Gelashvili. “Space-Optimal Majority in Population Protocols.” In: Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA. 2018, pp. 2221–2239. [3] D. Alistarh, R. Gelashvili, and J. Rybicki. “Fast Graphical Population Protocols.” In: 25th International Conference on Principles of Distributed Systems, OPODIS. 2021, 14:1–14:18. [4] D. Alistarh, J. Rybicki, and S. Voitovych. “Near-Optimal Leader Election in Population Protocols on Graphs.” In: Distributed Comput. 38.3 (2025), pp. 207–245. [5] D. Angluin, J. Aspnes, Z. Diamadi, M. J. Fischer, and R. Peralta. “Computation in networks of passively mobile finite-state sensors.” In: Distributed Comput. 18 (2006), pp. 235–253. [6] D. Angluin, J. Aspnes, and D. Eisenstat. “Fast computation by population protocols with a leader.” In: Distributed Comput. 21 (2008), pp. 183–199. [7] J. Beauquier, P. Blanchard, and J. Burman. “Self-stabilizing Leader Election in Population Protocols over Arbitrary Communication Graphs.” In: Principles of Distributed Systems - 17th International Conference, OPODIS. 2013, pp. 38–52. [8] P. Berenbrink, R. Elsässer, T. Friedetzky, H. Hosseinpour, D. Kaaser, P. Kling, and T. Sauerwald. “(Almost) Perfect Discrete Iterative Load Balancing.” In: 2026 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA. 2026, pp. 4224–4237. [9] P. Berenbrink, R. Elsässer, T. Friedetzky, D. Kaaser, P. Kling, and T. Radzik. “A Population Protocol for Exact Majority with O(log5/3 n) Stabilization Time and Θ(log n) States.” In: 32nd International Symposium on Distributed Computing, DISC. 2018, 10:1–10:18. [10] P. Berenbrink, G. Giakkoupis, and P. Kling. “Optimal Time and Space Leader Election in Population Protocols.” In: 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC. 2020, pp. 119–129. [11] P. Berenbrink, D. Kaaser, P. Kling, and L. Otterbach. “Simple and Efficient Leader Election.” In: 1st Symposium on Simplicity in Algorithms, SOSA. Vol. 61. 2018, 9:1– 9:11. [12] P. Berenbrink, D. Kaaser, and T. Radzik. “On Counting the Population Size.” In: 2019 ACM Symposium on Principles of Distributed Computing, PODC. 2019, pp. 43–52.

REFERENCES

[13] L. Cardelli and A. Csikász-Nagy. “The cell cycle switch computes approximate majority.” In: Scientific reports 2 (2012), p. 656. [14] H.-P. Chen and H.-L. Chen. “Self-Stabilizing Leader Election in Regular Graphs.” In: PODC ’20: ACM Symposium on Principles of Distributed Computing. 2020, pp. 210– 217. [15] Y.-J. Chen, N. Dalchau, N. Srinivas, A. Phillips, L. Cardelli, D. Soloveichik, and G. Seelig. “Programmable chemical controllers made from DNA.” In: Nature nanotechnology 8.10 (2013), p. 755. [16] M. B. Dillencourt, M. T. Goodrich, and M. Mitzenmacher. “Leveraging parameterized Chernoff bounds for simplified algorithm analyses.” In: Inf. Process. Lett. 187 (2025), p. 106516. [17] D. Doty and M. Eftekhari. “A survey of size counting in population protocols.” In: Theor. Comput. Sci. 894 (2021), pp. 91–102. [18] D. Doty and M. Eftekhari. “Dynamic Size Counting in Population Protocols.” In: 1st Symposium on Algorithmic Foundations of Dynamic Networks, SAND. 2022, 13:1– 13:18. [19] D. Doty and M. Eftekhari. “Efficient Size Estimation and Impossibility of Termination in Uniform Dense Population Protocols.” In: 2019 ACM Symposium on Principles of Distributed Computing, PODC. 2019, pp. 34–42. [20] D. Doty, M. Eftekhari, L. Gasieniec, E. E. Severson, P. Uznanski, and G. Stachowiak. “A time and space optimal stable population protocol solving exact majority.” In: 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS. 2021, pp. 1044–1055. [21] D. Doty, M. Eftekhari, O. Michail, P. G. Spirakis, and M. Theofilatos. “Brief Announcement: Exact Size Counting in Uniform Population Protocols in Nearly Logarithmic Time.” In: 32nd International Symposium on Distributed Computing, DISC. Vol. 121. 2018, 46:1–46:3. [22] P. Flajolet and G. Nigel Martin. “Probabilistic counting algorithms for data base applications.” In: Journal of Computer and System Sciences 31.2 (1985), pp. 182–209. [23] D. Kaaser and M. Lohmann. “Dynamic Size Counting in the Population Protocol Model.” In: 43rd ACM Symposium on Principles of Distributed Computing, PODC. 2024, pp. 50–60. [24] V. Kanade, F. Mallmann-Trenn, and T. Sauerwald. “On Coalescence Time in Graphs: When Is Coalescing as Fast as Meeting?” In: ACM Trans. Algorithms 19.2 (2023), 18:1–18:46. [25] H. Kanaya, R. Eguchi, T. Sasada, and M. Inoue. “Almost Time-Optimal LooselyStabilizing Leader Election on Arbitrary Graphs Without Identifiers in Population Protocols.” In: 28th International Conference on Principles of Distributed Systems, OPODIS. 2025, 37:1–37:17. [26] D. R. Kowalski and M. A. Mosteiro. “Polynomial Counting in Anonymous Dynamic Networks with Applications to Anonymous Dynamic Algebraic Computations.” In: J. ACM 67.2 (2020), 11:1–11:17. [27] D. A. Levin, Y. Peres, and E. L. Wilmer. Markov Chains and Mixing Times. American Mathematical Soc., 2009. [28] T. M. Liggett. Interacting Particle Systems. Springer, 1985. [29] G. Louchard, H. Prodinger, and M. D. Ward. “The number of distinct values of some multiplicity in sequences of geometrically distributed random variables.” In: Discrete Mathematics & Theoretical Computer Science, DMTCS Proceedings (2005).

REFERENCES

[30] J. Rybicki, J. Solnerzik, O. Stietel, and R. Vacus. “Space-efficient population protocols for exact majority on general graphs.” In: 2026 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA. 2026, pp. 574–612. [31] D. Soloveichik, M. Cook, E. Winfree, and J. Bruck. “Computation with finite stochastic chemical reaction networks.” In: Nat. Comput. 7.4 (2008), pp. 615–633. [32] Y. Sudo, F. Ooshita, T. Izumi, H. Kakugawa, and T. Masuzawa. “Logarithmic ExpectedTime Leader Election in Population Protocol Model.” In: 2019 ACM Symposium on Principles of Distributed Computing, PODC. 2019, pp. 60–62.

Counting in Population Protocols on Graphs

Analyze & explore related research in Conceptio

Related documents