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. In: 25th International Colloquium on Structural Information and Communication Complexity (SIROCCO ) 2018, 2018-6-18 - 2018-6-21, Maale HaHawisha Israel.

[img] Text
SIROCCO_2018_paper_23.pdf - Author Accepted Manuscript

Download (677kB)


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: 19 Jan 2023 06:33
Related URLs: