We use cookies to ensure that we give you the best experience on our website. You can change your cookie settings at any time. Otherwise, we'll assume you're OK to continue.

Durham University

Computer Science



Algorithms and Complexity (ACiD) Seminar: Optimal Time and Space Leader Election in Population Protocols

Presented by Petra Berenbrink, University of Hamburg
10 December 2019 13:00 in E245

Population protocols are a model of distributed computing, where n agents with limited computational power and memory interact randomly, in order to jointly perform a global task. A fundamental problem in this setting is that of leader election, where all agents start from the same state, and they seek to reach and maintain a global state where exactly one agent is in a dedicated leader state. We establish that if agents have Omega(\log\log n) states, the expected time complexity of leader election is Theta(n \log n). Unlike existing protocols, ours does not decrease the set of candidate leaders monotonically. Our protocol has both optimal time and space complexity. Joint work with George Giakkoupis and Peter Kling

Contact for more information