On the State Complexity of Population Protocols
Michael Blondin ( TU Munich )

11:00 29th March 2018 ( week 11th, Hilary Term 2018 )Room 441  Dept. of Computer Science
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 Presburgerdefinable 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.