← All problems
Unverified
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 . (For definitions see https://arxiv.org/abs/1801.00742 ) For every , let be the largest number such that some protocol with at most states computes the predicate . It is shown in the above paper that for protocols with leaders. This is all we know about . Open problems: Give a bound on for protocols with leaders. Give a bound on for protocols without leaders.
