19.15 The busy beaver problem for population protocols

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.