Population protocols are a model of distributed computation by indistinguishable agents, close to VASs. We consider population protocols with one input state. These protocols compute predicates $\mathbb{N} \rightarrow \{0,1\}$. (For definitions see https://arxiv.org/abs/1801.00742)
For every $n \geq 1$, let $f(n)$ be the largest number such that some protocol with at most $n$ states computes the predicate $x < f(n)$.
It is shown in the above paper that $f(n) \in 2^{2^{\Omega(n)}}$ for protocols with leaders. This is all we know about $f(n)$.
Open problems:
- Give a bound on $f(n)$ for protocols with leaders.
- Give a bound on $f(n)$ for protocols without leaders.