LSV Seminar
The LSV seminar takes place on Tuesday at 11:00 AM. The usual location is the conference room at Pavillon des Jardins (venue). If you wish to be informed by e-mail about upcoming seminars, please contact Stéphane Le Roux and Matthias Fuegger.
The seminar is open to public and does not require any form of registration.
Past Seminars
Automatic analysis of expected termination time for population protocols
- Date
- Tuesday, May 15 2018 at 11:00AM
- Place
- Salle de Conférence (Pavillon des Jardins)
- Speaker
- Michael Blondin (Technical University of Munich)
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.