Oberseminar
Felix Biermeier University of Hamburg
November 27, 2020, 11:00, zoom: https://uni-hamburg.zoom.us/j/94889228942
Title: Time and Space Optimal Exact Majority Population Protocols
In this talk I will present the following paper of Gasieniec, Stachowiak and Uznanski about exact majority in population protocols.
In this paper they study population protocols governed by the random scheduler, which uniformly at random selects pairwise interactions between n agents. The main result of this paper is the first time and space optimal exact majority population protocol which also works with high probability. The new protocol operates in the optimal parallel time O(log n), which is equivalent to O(n log n) sequential pairwise interactions, where each agent utilises the optimal number of O(log n) states. The time optimality of the new majority protocol is possible thanks to the novel concept of fixed-resolution phase clocks introduced and analysed in this paper. The new phase clock allows to count approximately constant parallel time in population protocols.