March 21, 2019 (15:00 | SR 6): CT-Talk with Prof. Robert Elsässer

on "Recent Results in Population Protocols for Exact Majority"

Abstract: Population protocols act in a simple and natural framework to solve fundamental problems in networks. Given a population of n anonymous nodes (also called agents), a scheduler chooses in discrete time steps two nodes for interaction, which then exchange their current states and perform a so called state transition. We focus on the random scheduler, which selects in each step two nodes uniformly at random for interaction, and on the problems of exact majority. In exact majority, initially the nodes possess one of two opinions, A or B, and the population is required to converge to a configuration, in which every node has the opinion of the initial majority. The goal is to design protocols, which require a small number of states and reach a correct final configuration as fast as possible. In this talk we give an overview of the most recent results in population protocols for exact majority.

Bio: Robert Elsässer graduated as “Diplom-Informatiker” in 1998 at the University of Paderborn, Germany. In 2002 he obtained a PhD in Computer Science at the same university, and was appointed to Junior Professor at the Institute for Computer Science of the University of Paderborn. For his PhD Thesis, he received the faculty award for an excellent dissertation. From April 2005 to March 2006, Robert Elsässer visited the Department of Mathematics at the University of California, San Diego, USA. In September 2007, he was a visiting professor at INRIA-Futurs, Bordeaux, and from October 2009 to September 2010 he headed the Chair of Algorithms and Complexity at the University of Freiburg as a visiting professor. The main research interests of Robert Elsässer include parallel and distributed algorithms, as well as the structure and spectra of graphs and networks. He served as member in the program committee of several international conferences, and as a referee for several Funding Agencies, as well as for numerous international conferences and journals. Since 2012, Robert Elsässer is the head of the Efficient Algorithms Group at the University of Salzburg.