On the State Complexity of Population Protocols

Population protocols are a model of distributed computing in which replicated, mobile agents with limited computational power interact stochastically to achieve a common task. They provide a simple and elegant formalism to model, e.g., networks of passively mobile sensors and chemical reaction networks. A classical result establishes that population protocols compute exactly predicates definable in Presburger arithmetic. However, little is known on the minimal number of states required for a protocol to compute a given Presburger-definable predicate.

In this talk, I will introduce population protocols and discuss their state complexity. I will focus on the predicates of the form x ≥ n, and more generally on the predicates corresponding to systems of linear inequalities. We will see that they can be computed by protocols with O(log n) states, and that, surprisingly, some families of predicates can be computed by protocols with O(log log n) states.

Some matching lower bounds will also be presented.

This talk is based on a STACS'18 paper and joint work with Javier Esparza 

and Stefan Jaax.