The Expressive Power of Uniform Population Protocols with Logarithmic Space

Population protocols are a model of computation in which indistinguishable mobile agents randomly interact in pairs to decide whether their initial configuration satisfies a given property. The decision is taken by stable consensus; eventually all agents agree on whether the property holds or not, and never change their mind again. While originally introduced to model sensor networks [4], population protocols are also very close to chemical reaction networks [24], a model in which agents are molecules and interactions are chemical reactions.

Originally agents were assumed to have a finite number of states [4, 5, 6], however many predicates then provably require at least $\mathrm{\Omega }(n)$ time to decide [20, 7, 1], as opposed to recent breakthroughs of $𝒪(\log n)$ time using $𝒪(\log n)$ or even fewer states for important tasks like leader election [9] and majority [18]. Limitting the number of states to logarithmic is important in most applications, especially the chemical reaction setting, since a linear in $n$ number of states would imply the unrealistic number of approximately ${10}^{23}$ different chemical species. Therefore most recent literature focuses on the polylogarithmic time and space setting, and determines time-space tradeoffs for various important tasks like majority [3, 1, 2, 21, 8, 18], leader election [1, 21, 9] or estimating/counting the population size [19, 15, 10, 16, 17].

This leads to the interesting open problem of characterizing the class of predicates which can be computed in polylogarithmic time using a logarithmic or polylogarithmic number of states. There is however a fundamental problem with working on this question: Despite the focus on $𝒪(\log n)$ number of states in recent times, the expressive power for this number of states has not yet been determined. While it is known that protocols with $o(\log n)$ number of states can only compute semilinear predicates [6, 14] and with $f(n)\in \mathrm{\Omega }(n)$ states the expressive power is $\mathrm{𝖴𝖭𝖲𝖯𝖠𝖢𝖤}(n\log f(n))$ [14], i.e. predicates which can be decided in $\mathrm{𝖭𝖲𝖯𝖠𝖢𝖤}(n\log f(n))$, when the input is encoded in unary, the important case of having logarithmically many states is unknown. To the best of our knowledge, the only research in this direction is [12], where the expressive power is characterised for $\mathrm{polylog}(n)$ number of states for a similar model – not population protocols themselves. Their results do not lead to a complete characterization for $\mathrm{\Theta }(\log n)$ states since their construction is slightly too space-inefficient, simulating a $\log \log n$-space TM by approximately ${\log }^{2}n$ space protocols.

In this paper, we resolve this gap by proving that for functions $f(n)\in \mathrm{\Omega }(\log n)\cap 𝒪(n^{1-\epsilon })$, where $\epsilon >0$, we have $\mathrm{𝖴𝖯𝖯}(f(n))=\mathrm{𝖴𝖭𝖲𝖯𝖠𝖢𝖤}(f(n)\cdot \log n)$, i.e. predicates computable by population protocols using $𝒪(f(n))$ number of states are exactly the predicates computable by a non-deterministic Turing machine using $𝒪(f(n)\cdot \log n)$ space with the input encoded in unary. The “U” in $\mathrm{𝖴𝖯𝖯}(f(n))$ stands for uniform: Modern population protocol literature distinguishes between uniform and non-uniform protocols. In a non-uniform protocol, a different protocol is allowed to be used for every population size. While we have stated the expressive power for uniform protocols here, our complexity characterization also holds for non-uniform population protocols.

Our results complete the picture of the expressive power of uniform protocols: For $o(\log n)$ only semilinear predicates can be computed (open for non-uniform), for a class of reasonable functions $f(n)\in \mathrm{\Omega }(\log n)\cap 𝒪(n^{1-\epsilon })$ , which contains most practically relevant functions¹¹1This will be clarified in the next section. we have $\mathrm{𝖴𝖭𝖲𝖯𝖠𝖢𝖤}(\log (n)\cdot f(n))$ by our results, and for $f\in \mathrm{\Omega }(n)$ we have $\mathrm{𝖴𝖭𝖲𝖯𝖠𝖢𝖤}(n\cdot \log f(n))$. (A slight gap between $𝒪(n^{1-\epsilon })$ and $\mathrm{\Omega }(n)$ remains.)

We let $\mathbb{N}$ denote the set of natural numbers including $0$ and let $\mathbb{Z}$ denote the set of integers. We write $\log n$ for the binary logarithm ${\log }_{2}n$.

A multiset over a set $Q$ is a multiplicity function $f:Q\to \mathbb{N}$, which maps every $q\in Q$ to its number of occurances in the multiset $f$. We denote multisets using a set notation with multiplicities, i.e. $\{f(q_1)\cdot q_1,\mathrm{\dots },f(q_m)\cdot q_m\}$. We define addition $f+f^{\prime }$ on multisets via $(f+f^{\prime })(q)=f(q)+f^{\prime }(q)$ for all $q\in Q$. Multisets are compared via inclusion, defined as $f\subseteq f^{\prime }\iff f(q)\le f^{\prime }(q)$ for all $q\in Q$. If $f\subseteq f^{\prime }$, then subtraction $f^{\prime }-f$ is defined via $(f^{\prime }-f)(q)=f^{\prime }(q)-f(q)$ for all $q\in Q$. The number of elements of $f$ is denoted $|f|$ and defined as ${\sum }_{f(q)\ne 0}f(q)$ if only finitely many $q\in Q$ fulfill $f(q)\ne 0$, and $|f|=\mathrm{\infty }$ otherwise. Elements $q$ of $Q$ are identified with the multiset $\{1\cdot q\}$. The set of all finite multisets over $Q$ is denoted ${\mathbb{N}}^Q$. Given a function $g:A\to B$, its extension $\widehat{g}$ to finite multisets is $\widehat{g}:{\mathbb{N}}^A\to {\mathbb{N}}^B,\widehat{g}(f)={\sum }_{f(a)\ne 0}f(a)\cdot \{g(a)\}$.

A configuration of $𝒫$ is a finite multiset $C\in {\mathbb{N}}^Q$. A step $C\to C^{\prime }$ in $𝒫$ consists of choosing a multiset $\{q_1,q_2\}\subseteq C$ and replacing $\{q_1,q_2\}$ by $\{\delta (q_1,q_2)\}$ or $\{\delta (q_2,q_1)\}$, i.e. $C^{\prime }=(C-\{q_1,q_2\}+\{\delta (q_1,q_2)\})$. The intuition is that the configuration describes for every $q$ the number of agents in $q$, and a step consists of an agent in $q_1$ exchanging messages with $q_2$, upon which these two agents change into the states $\delta (q_1,q_2)$. Observe that the transition function $\delta$ distinguishes between the initiator of the exchange and the responder, while in the configuration all agents are anonymous. The number of agents is denoted $n:=|C|$.

We write ${\to }^{\ast }$ for the reflexive and transitive closure of $\to$, and say that a configuration $C^{\prime }$ is reachable from $C$ if $C{\to }^{\ast }{C}^{\prime }$. A configuration $C$ is initial if there exists a multiset $w\in {\mathbb{N}}^{\mathrm{\Sigma }}$ such that $\widehat{I}(w)=C$. In that case $C$ is the initial configuration for input $w$.

A configuration $C$ is a $b$-consensus for $b\in \{0,1\}$ if $O(q)=b$ for all $q$ such that $C(q)\ne 0$, i.e. if every state which occurs in the configuration has output b. A configuration $C$ is stable with output $b$ if every configuration $C^{\prime }$ reachable from $C$ is a $b$-consensus.

A run $\rho$ is an infinite sequence of configurations $\rho =(C_0,C_1,\mathrm{\dots })$ such that $C_i\to C_{i+1}$ for all $i\in \mathbb{N}$. A run is fair if for all configurations $C$ which occur infinitely often in $\rho$, i.e. such that there are infinitely many $i$ with $C_i=C$, also every configuration $C^{\prime }$ reachable from $C$ occurs infinitely often in $\rho$. A run has output $b$ if some configuration $C_i$ along the run is stable with output $b$ (and hence all $C_j$ for $j\ge i$ are also stable with output $b$).

An input $w\in {\mathbb{N}}^{\mathrm{\Sigma }}$ has output $b$ if every fair run starting at its corresponding initial configuration $\widehat{I}(w)$ has output $b$. The protocol scheme $𝒫$ computes a predicate if every input $w$ has some output. In that case the computed predicate is the mapping ${\mathbb{N}}^{\mathrm{\Sigma }}\to \{0,1\}$, which maps $w$ to the output of $\widehat{I}(w)$.

We now define the state complexity of a protocol scheme. A state $q\in Q$ is coverable from some initial configuration $C_0$ if there exists a configuration $C$ reachable from $C_0$ which fulfills $C(q)>0$. The state complexity $S(n)$ of $𝒫$ for $n$ agents is the number of states $q\in Q$ which are coverable from some initial configuration with $n$ agents.

As defined so far, protocol schemes are not necessarily computable. Hence actual population protocols require some uniformity condition, and that $S(n)$ is finite for all $n$.

We remark that “linear space” then in terms of our $n$, the number of agents, is $𝒪(\log S(n))$ space (since the input of the machine is a representation of a state).

In the literature on uniform population protocols, e.g. [13, 14, 19, 15], often agents are defined as TMs and states hence automatically assumed to be represented as binary strings. We avoid talking about the exact implementation of a protocol via TMs because it introduces an additional logarithm in the number of states and potentially confuses the reader, while most examples are clearly computable.

Next we define a more general class of population protocols, which we call weakly uniform. This class includes all known population protocols, and our results also hold for this class, which shows that having a different protocol for every $n$ does not strengthen the model.

The configurations of $𝒫$ with $n$ agents are exactly the configurations of ${𝒫}_n$ with $n$ agents, and accordingly the semantics of steps, runs and acceptance are inherited from ${𝒫}_n$.

The protocol for a given population size $n$ is allowed to differ completely from the protocol for $n-1$ agents, as long as TMs are still able to evaluate transitions, input and output. Usually this is not fully utilised, with the most common case of a non-uniform protocol being that $\log n$ is encoded into the transition function [18].

Clearly uniform population protocols are weakly uniform. Namely let $𝒫=(Q,\mathrm{\Sigma },\delta ,I,O)$ be a protocol scheme. Then for every $n\in \mathbb{N}$ we let $Q_n$ be the set of states coverable by some initial configuration with $n$ agents, similar to the definition of state complexity, and define ${𝒫}_n:=(Q_n,\mathrm{\Sigma },{{\delta }_n|}_{Q_n^2},I,{O|}_{Q_n})$, where ${f|}_A$ is the restriction of $f$ to inputs in $A$. This protocol family computes the same predicate, and is weakly-uniform with the same state complexity.

Next we define the complexity classes for our main result. Let $f:\mathbb{N}\to \mathbb{N}$ be a function. $f$ is space-constructible if there exists a TM $M$ which computes $f$ using $𝒪(f(n))$ space. Given a space-constructible function $f:\mathbb{N}\to \mathbb{N}$, we denote by $\mathrm{𝖭𝖲𝖯𝖠𝖢𝖤}(f(n))$ the class of predicates computable by a non-deterministic Turing-machine in $𝒪(f(n))$ space. Similarly, let $\mathrm{𝖴𝖯𝖯}(f(n))$ be the class of predicates computable by uniform population protocols with $𝒪(f(n))$ space, and $\mathrm{𝖶𝖴𝖯𝖯}(f(n))$ be the class of predicates computable by weakly-uniform population protocols with $𝒪(f(n))$ space.

Population protocols decide predicates on multisets $w\in {\mathbb{N}}^{\mathrm{\Sigma }}$, or equivalently predicates on ${\mathbb{N}}^k$ for $k=|\mathrm{\Sigma }|$. In order to compare the complexity classes defined on predicates with those defined on languages over an alphabet we define the unary encoding of a predicate $\phi :{\mathbb{N}}^k⟶\{0,1\}$ as the language $L_{\phi }≔\{1^{x_1}\mathrm{\#}{1}^{x_2}\mathrm{\#}\mathrm{\cdots }\mathrm{\#}{1}^{x_k}\mid \phi (x_1,x_2,\mathrm{\dots },x_k)=1\}$. For any complexity class $𝒞$ we can now define $\mathrm{𝖴𝖤𝖭𝖢}(𝒞)≔\{\phi :{\mathbb{N}}^k⟶\{0,1\}\mid k\in \mathbb{N},L_{\phi }\in 𝒞\}$ as the class of predicates whose unary encoding lies in $𝒞$. More specificaly we define $\mathrm{𝖴𝖭𝖲𝖯𝖠𝖢𝖤}(f(n))≔\mathrm{𝖴𝖤𝖭𝖢}(\mathrm{𝖭𝖲𝖯𝖠𝖢𝖤}(f(n)))$ ²²2Previous work has instead used the complexity class $\mathrm{𝖲𝖭𝖲𝖯𝖠𝖢𝖤}(f(n))$ consisting of the symmetric languages (i.e. languages closed under permutation) over the alphabet $\mathrm{\Sigma }$ in $\mathrm{𝖭𝖲𝖯𝖠𝖢𝖤}(f(n))$ to reflect that the agents in a population protocol are unordered. We find it more intuitive to think about a unary encoding with separators, but languages with either encoding can be polynomially reduced to the other..

We give a characterisation for the expressive power of both uniform and weakly uniform population protocols with $f(n)$ states, where $f\in \mathrm{\Omega }(\log n)\cap 𝒪(n^{1-\epsilon })$, for some $\epsilon >0$. For technical reasons, we must place two limitations on $f(n)$:

1. 1.

   $f(n)=g(\lfloor \log n\rfloor )$ for some $g:\mathbb{N}\to \mathbb{N}$, i.e. $f$ is computable knowing only $\lfloor \log n\rfloor$.

2. 2.

   $f(n)$ is space-constructible, i.e. the function $f$ can be computed in $\mathrm{𝖲𝖯𝖠𝖢𝖤}(f(n))$, and

3. 3.

   $f(n)$ is monotonically increasing.

All practically relevant functions fulfil these properties. For the first, we remark that “usually” $f(n)\in \mathrm{\Theta }(f(2^{\lfloor \log n\rfloor }))$.³³3The exceptions are plateau functions with large jumps. For example, while $\sqrt{n}$ is not computable from $\lfloor \log n\rfloor$, we can instead use $\sqrt{2^{\lfloor \log n\rfloor }}$, which is asymptotically equivalent.

In the remainder of this paper, a function $f$ with these properties is called reasonable.

Our bound applies to uniform and weakly uniform protocols. As mentioned in the previous section, the latter includes, to the best of our knowledge, all non-uniform constructions from the literature.

In this section, we prove the following.

To do this we first fix a reasonable function $f\in \mathrm{\Omega }(\log n)\cap 𝒪(n^{1-\epsilon })$ and a predicate $\phi :{\mathbb{N}}^{\mathrm{\Sigma }}⟶\{0,1\}$ with $\phi \in \mathrm{𝖴𝖭𝖲𝖯𝖠𝖢𝖤}(f(n)\log n)$. With a slight modification to the classic 3-counter simulation of a $f(n)$ space-bounded Turing machine described in [23], we obtain a counter machine $𝒞ℳ$ with $|\mathrm{\Sigma }|$ input registers and 3 computation registers that decides $\phi$ using $𝒪\left(2^{f(n)\log n}\right)$ space.

We now construct a population protocol $𝒫=(Q,\mathrm{\Sigma },\delta ,I,O)$ simulating $𝒞ℳ$. There are three main difficulties involved in this construction:

Firstly, in order to sequence multiple operations such that an operation only starts once the previous one has finished, we need a way of performing a zero-check, i.e. detecting whether an agent with a certain state exists. We achieve this by counting the number of agents using a binary encoding similar as to [12]. By keeping track of the agents already seen in an additional counter, we can then perform loops over all agents, and so detect absence of a certain state.

Secondly, we need to encode the counters of $𝒞ℳ$, which can hold values up to $𝒪\left(2^{f(n)\log n}\right)$. The two counter encodings described in existing literature of either counting in unary the number of agents in a special state [5], or the binary encoding of [12] both cannot encode numbers this large. We improve on the binary encoding by using digits in a higher base of $\mathrm{\Theta }\left(\frac{n}{f(n)}\right)$ and counting in unary within each digit. Manipulating these digits makes heavy use of the looping construct mentioned above.

The final problem, which is inherent to all population protocols, is that an arbitrary number of agents may not participate in any interactions for an arbitrary long amount of time. These errors are detected at some point, but this can happen arbitrarily late. At that point, we solve this by providing a way for the simulation to re-initialize itself.

The protocol consists of multiple phases:

1. 1.

   We count the number of agents and initialize the additional counters to zero. This process is detailed in Section 4.2. Section 4.3 describes how the counters are manipulated, and Section 4.4 presents a macro for looping over all agents using the counters for bookkeeping.

2. 2.

   We set up the digits, which encode the counters of $𝒞ℳ$. This phase is described in Section 4.6.

3. 3.

   The instructions of $𝒞ℳ$ are simulated. This is described in Section 4.7.

As a technical aside, as is usual we assume that the protocol is started with a sufficient number of agents (i.e. exceeding some constant). We argue in the proof of Theorem 9 why this is not a problem.