Simple and fast approximate counting and leader election in populations

Michail, Othon ORCID: 0000-0002-6234-3960, Spirakis, Paul G ORCID: 0000-0001-5396-3749 and Theofilatos, Michail ORCID: 0000-0002-3699-0179 (2022) Simple and fast approximate counting and leader election in populations. INFORMATION AND COMPUTATION, 285. p. 104698.

This is the latest version of this item.

Text
MST20-Information and Computation.pdf - Author Accepted Manuscript
Download (633kB) | Preview

Official URL: http://dx.doi.org/10.1016/j.ic.2021.104698

Abstract

We study leader election and population size counting for population protocols: networks of finite-state anonymous agents that interact randomly. We provide simple protocols for approximate counting of the size of the population and for leader election. We show a protocol for leader election that terminates in [Formula presented] parallel time, where m is a parameter that belongs to Ω(log⁡n) and O(n), using O(max⁡{log⁡m,log⁡log⁡n}) bits. By adjusting m between log⁡n and n, we obtain a leader election protocol whose time and space can be smoothly traded off between [Formula presented] to O(log⁡n) time and O(log⁡log⁡n) to O(log⁡n) bits. We also give a protocol which provides a constant factor approximation of log⁡n of the population size n, or an upper bound ne which is at most na for some constant a>1. This protocol assumes the existence of a unique leader and stabilizes in Θ(log⁡n) parallel time.

Item Type:	Article
Uncontrolled Keywords:	Population protocol, Epidemic, Leader election, Counting, Approximate counting, Polylogarithmic time protocol
Divisions:	Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science
Depositing User:	Symplectic Admin
Date Deposited:	13 Jun 2022 10:50
Last Modified:	18 Jan 2023 21:33
DOI:	10.1016/j.ic.2021.104698
Related URLs:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3133682