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]](https://livrepository.liverpool.ac.uk/style/images/fileicons/text.png) |
Text
SIROCCO_2018_paper_23.pdf - Author Accepted Manuscript 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: | 19 Jan 2023 06:33 |
| Related URLs: | |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3021478 |
Share
Share
