Almost Logarithmic-Time Space Optimal Leader Election in Population Protocols



Gasieniec, LA ORCID: 0000-0003-1809-9814, Stachowiak, Grzegorz and Uznanski, Przemyslaw
(2019) Almost Logarithmic-Time Space Optimal Leader Election in Population Protocols. In: SPAA '19: 31st ACM Symposium on Parallelism in Algorithms and Architectures, 2019-6-22 - 2019-6-24, Phoenix, USA.

[img] Text
spaa.pdf - Author Accepted Manuscript

Download (586kB) | Preview

Abstract

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.

Item Type: Conference or Workshop Item (Unspecified)
Uncontrolled Keywords: Population protocols, leader election, randomised algorithm, distributed algorithm
Depositing User: Symplectic Admin
Date Deposited: 12 Jun 2019 15:38
Last Modified: 25 Nov 2023 13:42
DOI: 10.1145/3323165.3323178
Related URLs:
URI: https://livrepository.liverpool.ac.uk/id/eprint/3045572