Enhanced Phase Clocks, Population Protocols, and Fast Space Optimal Leader Election
- 17 November 2020
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 68 (1), 1-21
- https://doi.org/10.1145/3424659
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 article, the emphasis is on the space complexity of fast leader election in population protocols governed by the random scheduler, which uniformly at random selects pairwise interactions between n agents. One of the main results of this article is the first fast space optimal leader election protocol, which works with high probability. The new protocol operates in parallel time O(log2 n) equivalent to O(nlog2 n) sequential pairwise interactions with each agent’s memory space limited to O(log log n) states. This double logarithmic space utilisation matches asymptotically the lower bound ½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 Reference [7]. 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.Keywords
Funding Information
- Polish National Science Centre (DEC-2012/06/M/ST6/00459)
This publication has 25 references indexed in Scilit:
- Leader election for anonymous asynchronous agents in arbitrary networksDistributed Computing, 2013
- Trade-offs Between the Size of Advice and Broadcasting Time in TreesAlgorithmica, 2009
- Fast computation by population protocols with a leaderDistributed Computing, 2008
- A simple population protocol for fast robust approximate majorityDistributed Computing, 2008
- Phase clocks for transient fault repairIEEE Transactions on Parallel and Distributed Systems, 2000
- Computing on anonymous networks. I. Characterizing the solvable casesIEEE Transactions on Parallel and Distributed Systems, 1996
- Better computing on the anonymous ringJournal of Algorithms, 1991
- Computing on an anonymous ringJournal of the ACM, 1988
- Electing a leader in a synchronous ringJournal of the ACM, 1987
- An O ( n log n ) Unidirectional Algorithm for the Circular Extrema ProblemACM Transactions on Programming Languages and Systems, 1982