Fast Approximate Counting and Leader Election in Populations

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.

16 pages, 5 figures, to be published in SIROCCO 2018 proceedings - Brief Announcement

References in corpus (1)

• Time and Space Optimal Counting in Population Protocols