TY - GEN
T1 - Fast space optimal leader election in population protocols
AU - Gasieniec, Leszek
AU - Stachowiak, Grzegorz
N1 - Publisher Copyright:
© Copyright 2018 by SIAM.
PY - 2018
Y1 - 2018
N2 - The model of population protocols refers to the growing in popularity theoretical framework suitable for studying pairwise interactions within a large collection of simple indistinguishable entities, frequently called agents. In this paper the emphasis is on the space complexity in fast leader election via population protocols governed by the random scheduler, which uniformly at random selects pairwise interactions from the population of n agents. The main result of this paper is a new fast and space optimal leader election protocol. The new protocol operates in parallel time O(log2 n) equivalent to O(n log2 n) sequential pairwise interactions, in which each agent utilises O(log log n) states. This double logarithmic space utilisation matches asymptotically the lower bound 1 2 log log n on the number of states utilised by agents in any leader election algorithm with the running time o( n polylog n), see [7]. Our solution relies on the concept of phase clocks, a fundamental synchronisation and coordination tool in the field of Distributed Computing. We propose a new fast and robust population protocol for initialisation of phase clocks to be run simultaneously in multiple modes and intertwined with the leader election process. We also provide the reader with the relevant formal argumentation indicating that our solution is always correct and fast with high probability.
AB - The model of population protocols refers to the growing in popularity theoretical framework suitable for studying pairwise interactions within a large collection of simple indistinguishable entities, frequently called agents. In this paper the emphasis is on the space complexity in fast leader election via population protocols governed by the random scheduler, which uniformly at random selects pairwise interactions from the population of n agents. The main result of this paper is a new fast and space optimal leader election protocol. The new protocol operates in parallel time O(log2 n) equivalent to O(n log2 n) sequential pairwise interactions, in which each agent utilises O(log log n) states. This double logarithmic space utilisation matches asymptotically the lower bound 1 2 log log n on the number of states utilised by agents in any leader election algorithm with the running time o( n polylog n), see [7]. Our solution relies on the concept of phase clocks, a fundamental synchronisation and coordination tool in the field of Distributed Computing. We propose a new fast and robust population protocol for initialisation of phase clocks to be run simultaneously in multiple modes and intertwined with the leader election process. We also provide the reader with the relevant formal argumentation indicating that our solution is always correct and fast with high probability.
UR - http://www.scopus.com/inward/record.url?scp=85045571281&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85045571281&partnerID=8YFLogxK
U2 - 10.1137/1.9781611975031.169
DO - 10.1137/1.9781611975031.169
M3 - Conference contribution
AN - SCOPUS:85045571281
T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
SP - 2653
EP - 2667
BT - 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018
A2 - Czumaj, Artur
PB - Association for Computing Machinery
T2 - 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018
Y2 - 7 January 2018 through 10 January 2018
ER -