Black Ninjas in the Dark: Analyzing Population Protocols
10 October 2018
About the lecture
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 behavior of chemical systems and 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 a 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.
Technical University of Munich, Germany
- Prof. Esparza studied physics in Zaragoza (Spain), where he also completed his doctorate in computer science in 1990.
- After qualifying as a lecturer in computer science (Hildesheim, 1994), he was appointed associate professor at TUM (1994-2001).
- He was a professor at Edinburgh University between 2001 and 2003 and held a Chair at the University of Stuttgart between 2003 and 2007.
- He has been a full professor at TUM since 2007.
- The Chair held by Prof. Esparza develops methods, algorithms, and tools to locate and eliminate errors in software systems or verify their correctness.
- The mathematical techniques used in this work include logic, automata theory, and complexity theory.