← 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 N→{0,1}\mathbb{N} \rightarrow \{0,1\}. (For definitions see https://arxiv.org/abs/1801.00742 ) For every n≥1n \geq 1, let f(n)f(n) be the largest number such that some protocol with at most nn states computes the predicate x<f(n)x < f(n). It is shown in the above paper that f(n)∈22Ω(n)f(n) \in 2^{2^{\Omega(n)}} for protocols with leaders. This is all we know about f(n)f(n). Open problems: Give a bound on f(n)f(n) for protocols with leaders. Give a bound on f(n)f(n) for protocols without leaders.

Coming soon

Organizer

Boyuan Wang portraitBoyuan Wang
Minghan Wang portraitMinghan Wang
Bochao Li portraitBochao Li
Hongwei Hu portraitHongwei Hu