Search

The population protocol model describes a network of anonymous agents that interact asynchronously in pairs chosen at random. Each agent starts in the same initial state $s$. We introduce the *dynamic size counting* problem: approximately counting the number of agents in the presence of an adversary who at any time can remove any number of agents or add any number of new agents in state $s$. A valid solution requires that after each addition/removal event, resulting in population size $n$, with high probability each agent "quickly" computes the same constant-factor estimate of the value $\log_2 n$ (how quickly is called the *convergence* time), which remains the output of every agent for as long as possible (the *holding* time). Since the adversary can remove agents, the holding time is necessarily finite: even after the adversary stops altering the population, it is impossible to *stabilize* to an output that never again changes. We first show that a protocol solves the dynamic size counting problem if and only if it solves the *loosely-stabilizing counting* problem: that of estimating $\log n$ in a *fixed-size* population, but where the adversary can initialize each agent in an arbitrary state, with the same convergence time and holding time. We then show a protocol solving the loosely-stabilizing counting problem with the following guarantees: if the population size is $n$, $M$ is the largest initial estimate of $\log n$, and s is the maximum integer initially stored in any field of the agents' memory, we have expected convergence time $O(\log n + \log M)$, expected polynomial holding time, and expected memory usage of $O(\log^2 (s) + (\log \log n)^2)$ bits. Interpreted as a dynamic size counting protocol, when changing from population size $n_{prev}$ to $n_{next}$, the convergence time is $O(\log n_{next} + \log \log n_{prev})$.

The population protocol model describes a network of $n$ anonymous agents who cannot control with whom they interact. The agents collectively solve some computational problem through random pairwise interactions, each agent updating its own state in response to seeing the state of the other agent. They are equivalent to the model of chemical reaction networks, describing abstract chemical reactions such as $A+B \rightarrow C+D$, when the latter is subject to the restriction that all reactions have two reactants and two products, and all rate constants are 1. The counting problem is that of designing a protocol so that $n$ agents, all starting in the same state, eventually converge to states where each agent encodes in its state an exact or approximate description of population size $n$. In this survey paper, we describe recent algorithmic advances on the counting problem.