Contact

Director

Prof. Dr. Ernst-Rüdiger Olderog

Department of Computing Science
FK II
University of Oldenburg
D-26111 Oldenburg, Germany

Coordinator

Ira Wempe

Department of Computing Science
FK II
University of Oldenburg
D-26111 Oldenburg, Germany

[Invited Talk 12.11.2018] Esparza

Black Ninjas in the Dark: Analyzing Population Protocols

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.

(Changed: 19 Jan 2024)  | 
Zum Seitananfang scrollen Scroll to the top of the page