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.
Seminar
Broadcast Population Protocols
- Date
- 20.10.2020, 11:00
- Place
- online
- Speaker
- Javier Esparza (Technische Universitaet Muenchen)
Population protocols are a model of distributed computation in which indistinguishable finite-state agents cooperate to decide a property of their initial configuration (or, equivalently, whether their initial configuration belongs to a given set). In standard population protocols agents interact in pairs, and they can decide exactly the properties corresponding to sets expressible in Presburger arithmetic. We show that this is well below their potential.Intuitively, while population protocols have enough resources to compute much more, they are not able to use them due to the limitations of the model. We show that broadcast population protocols, where agents interact by reliable broadcasts, increase the expressive power by one exponential. Further, we prove that for every decidable property there is a broadcast protocol that decides it in parallel logarithmic time in the number of agents. This also stands in contrast with the standard model, where some properties need linear time. Joint work with Michael Blonidn, Philipp Czerner, and Stefan Jaax