The seminar is open to public and does not require any form of registration.
Population protocols are a model of distributed computation by anonymous mobile agents with little computational power. Such protocols allow for modeling systems such as networks of passively mobile sensors and chemical reaction networks. Agents of a population protocol interact by meeting at random. In well-designed protocols, for every initial configuration of agents and every computation starting from this configuration, all agents eventually agree on a consensus value.
In this talk, I will discuss the problem of automatically computing an asymptotic bound on the expected time a protocol needs to reach consensus. I will present the first algorithm that, when successful, outputs a function f(n) such that the expected time to consensus is bounded by O(f(n)), where n is the number of agents executing the protocol. As we will see, experimental results show that this algorithm terminates and provides good bounds for many of the protocols found in the literature.
This talk is based on joint work with Javier Esparza and Antonín Kučera.