TY - GEN
T1 - Almost logarithmic-time space optimal leader election in population protocols
AU - Gąsieniec, Leszek
AU - Stachowiak, Grzegorz
AU - Uznański, Przemysław
N1 - Publisher Copyright:
© 2019 Association for Computing Machinery.
PY - 2019/6/17
Y1 - 2019/6/17
N2 - The model of population protocols refers to a large collection of simple indistinguishable entities, frequently called agents. The agents communicate and perform computation through pairwise interactions. We study fast and space efficient leader election in population of cardinality n governed by a random scheduler, where during each time step the scheduler uniformly at random selects for interaction exactly one pair of agents. We present the first o(log2)-time leader election protocol. It operates in expected parallel time O(log n log log n) which is equivalent to O(n log n log log n) pairwise interactions. This is the fastest currently known leader election algorithm in which each agent utilises asymptotically optimal number of O(log log n) states. The new protocol incorporates and amalgamates successfully the power of assorted synthetic coins with variable rate phase clocks.
AB - The model of population protocols refers to a large collection of simple indistinguishable entities, frequently called agents. The agents communicate and perform computation through pairwise interactions. We study fast and space efficient leader election in population of cardinality n governed by a random scheduler, where during each time step the scheduler uniformly at random selects for interaction exactly one pair of agents. We present the first o(log2)-time leader election protocol. It operates in expected parallel time O(log n log log n) which is equivalent to O(n log n log log n) pairwise interactions. This is the fastest currently known leader election algorithm in which each agent utilises asymptotically optimal number of O(log log n) states. The new protocol incorporates and amalgamates successfully the power of assorted synthetic coins with variable rate phase clocks.
KW - Distributed algorithm
KW - Leader election
KW - Population protocols
KW - Randomised algorithm
UR - http://www.scopus.com/inward/record.url?scp=85068720874&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85068720874&partnerID=8YFLogxK
U2 - 10.1145/3323165.3323178
DO - 10.1145/3323165.3323178
M3 - Conference contribution
AN - SCOPUS:85068720874
T3 - Annual ACM Symposium on Parallelism in Algorithms and Architectures
SP - 93
EP - 102
BT - SPAA 2019 - Proceedings of the 31st ACM Symposium on Parallelism in Algorithms and Architectures
PB - Association for Computing Machinery
T2 - 31st ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2019
Y2 - 22 June 2019 through 24 June 2019
ER -