Gasieniec, Leszek 
ORCID: 0000-0003-1809-9814 and Stachowiak, Grzegorz
(2018)
Fast Space Optimal Leader Election in Population Protocols.
.
![[img]](https://livrepository.liverpool.ac.uk/style/images/fileicons/text.png) |
Text
1704.07649v1.pdf - Published version Download (772kB) |
Abstract
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 within the population of n agents. The main result of this paper is a new fast and space optimal leader election protocol. The new protocol utilises O(log^2 n) parallel time (which is equivalent to O(n log^2 n) sequential pairwise interactions), and each agent operates on O(log log n) states. This double logarithmic space usage matches asymptotically the lower bound 1/2 log log n on the minimal number of states required by agents in any leader election algorithm with the running time o(n/polylog n). Our solution takes an advantage of the concept of phase clocks, a fundamental synchronisation and coordination tool in 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.
| Item Type: | Conference or Workshop Item (Unspecified) |
|---|---|
| Additional Information: | 21 pages, 2 figures, published in SODA 2018 proceedings |
| Uncontrolled Keywords: | cs.DC, cs.DC |
| Depositing User: | Symplectic Admin |
| Date Deposited: | 07 Jul 2017 09:55 |
| Last Modified: | 19 Jan 2023 07:04 |
| DOI: | 10.1137/1.9781611975031.169 |
| Related URLs: | |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3007458 |
Dimensions
Dimensions
