State Complexity of Counting Population Protocols With Leaders
share
Population protocols are a model of computation in which an arbitrary number of anonymous finite-state agents are interacting in order to decide by stable consensus if an initial configuration extended with some extra agents called leaders satisfies some property. In this paper, we focus on n-counting predicates that ask, given an initial configuration, if the number of agents in a given state is at least n. In a recent work it was exhibited for infinitely many n, a population protocol with at most O(loglog(n)) states that decides the n-counting predicate. We prove that this bound is almost optimal, by observing that any population protocol deciding such a predicate requires at least Ω((loglog(n))^1/3) states.
READ FULL TEXT