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
(2018) Fast Approximate Counting and Leader Election in Populations. .

[img] Text
SIROCCO_2018_paper_23.pdf - Accepted Version

Download (677kB)

Abstract

We study the problems of leader election and population size counting for population protocols: networks of finite-state anonymous agents that interact randomly under a uniform random scheduler. We show a protocol for leader election that terminates in $O(\log_m(n) \cdot \log_2 n)$ parallel time, where $m$ is a parameter, using $O(\max\{m,\log n\})$ states. By adjusting the parameter $m$ between a constant and $n$, we obtain a single leader election protocol whose time and space can be smoothly traded off between $O(\log^2 n)$ to $O(\log n)$ time and $O(\log n)$ to $O(n)$ states. Finally, we give a protocol which provides an upper bound $\hat{n}$ of the size $n$ of the population, where $\hat{n}$ is at most $n^a$ for some $a>1$. This protocol assumes the existence of a unique leader in the population and stabilizes in $\Theta{(\log{n})}$ parallel time, using constant number of states in every node, except the unique leader which is required to use $\Theta{(\log^2{n})}$ states.

Item Type: Conference or Workshop Item (Unspecified)
Additional Information: 16 pages, 5 figures, to be published in SIROCCO 2018 proceedings - Brief Announcement
Uncontrolled Keywords: cs.DC, cs.DC
Depositing User: Symplectic Admin
Date Deposited: 22 May 2018 07:59
Last Modified: 04 Jul 2022 07:17
Related URLs:
URI: https://livrepository.liverpool.ac.uk/id/eprint/3021478