Prof. Dr. Javier Esparza, TU München

Abstract:

Population protocols are a mathematical model of distributed computation introduced by Angluin et al. in 2004. The original purpose of Angluin et al. was the theoretical study of systems consisting of identical, cheap mobile devices with tiny computational resources, like sensor networks. However, since its introduction the model has also been used to analyze the behaviour of chemical systems and of people in social networks.

Population protocols help us to pose and study many fundamental questions about distributed systems: What can be computed by agents wishing to remain anonymous? Are leader processes necessary for optimal speed? Can macroscopic ``phase transitions'' be ``programmed'' at microscopic level? Is it possible to check automatically that a protocol works correctly? Is it possible to automatically synthesize a protocol for a given task?

In the talk I will introduce the population protocol model with the help of several examples. More precisely, I will present the problem of the Black Ninjas in the Dark, and the different solutions given to it by their Senseis. I will also show animated simulations of some protocols.