Enhanced Phase Clocks, Population Protocols, and Fast Space Optimal Leader Election



Gasieniec, Leszek ORCID: 0000-0003-1809-9814 and Stachowiak, Grzegorz
(2021) Enhanced Phase Clocks, Population Protocols, and Fast Space Optimal Leader Election. Journal of the ACM, 68 (1). pp. 1-21.

This is the latest version of this item.

[img] Text
jacm.pdf - Author Accepted Manuscript
Available under License : See the attached licence file.

Download (1MB) | Preview

Abstract

<jats:p> The model of <jats:italic>population protocols</jats:italic> refers to the growing in popularity theoretical framework suitable for studying <jats:italic>pairwise interactions</jats:italic> within a large collection of simple indistinguishable entities, frequently called <jats:italic>agents</jats:italic> . In this article, the emphasis is on the space complexity of fast <jats:italic>leader election</jats:italic> in population protocols governed by the <jats:italic>random scheduler</jats:italic> , which uniformly at random selects pairwise interactions between <jats:italic>n</jats:italic> agents. </jats:p> <jats:p> One of the main results of this article is the first fast space optimal <jats:italic>leader election protocol</jats:italic> , which works with high probability. The new protocol operates in <jats:italic>parallel time</jats:italic> <jats:italic>O</jats:italic> (log <jats:sup>2</jats:sup> <jats:italic>n</jats:italic> ) equivalent to <jats:italic>O</jats:italic> ( <jats:italic>n</jats:italic> log <jats:sup>2</jats:sup> <jats:italic>n</jats:italic> ) sequential <jats:italic>pairwise interactions</jats:italic> with each agent’s memory space limited to <jats:italic>O</jats:italic> (log log <jats:italic>n</jats:italic> ) states. This double logarithmic space utilisation matches asymptotically the lower bound ½log log <jats:italic>n</jats:italic> on the number of states utilised by agents in any leader election algorithm with the running time <jats:italic>o</jats:italic> ( <jats:italic>n</jats:italic> \polylog <jats:italic>n</jats:italic> ); see Reference [7]. </jats:p> <jats:p>Our new solution expands also on the classical concept of phase clocks used to synchronise and to coordinate computations in distributed algorithms. In particular, we formalise the concept and provide a rigorous analysis of phase clocks operating in nested modes. Our arguments are also valid for phase clocks propelled by multiple leaders. The combination of the two results in the first time-space efficient leader election algorithm. We also provide a complete formal argumentation, indicating that our solution is always correct, fast, and it works with high probability.</jats:p>

Item Type: Article
Uncontrolled Keywords: Population protocols, leader election, randomised algorithm, distributed algorithm
Divisions: Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science
Depositing User: Symplectic Admin
Date Deposited: 23 Jun 2021 12:16
Last Modified: 20 Feb 2023 22:50
DOI: 10.1145/3424659
Related URLs:
URI: https://livrepository.liverpool.ac.uk/id/eprint/3127427

Available Versions of this Item