Doty, David, Eftekhari, Mahsa, Michail, Othon 
ORCID: 0000-0002-6234-3960, Spirakis, Paul G ORCID: 0000-0001-5396-3749 and Theofilatos, Michail ORCID: 0000-0002-3699-0179
(2018)
Exact size counting in uniform population protocols in nearly
logarithmic time.
CoRR, abs/18.
![[img]](https://livrepository.liverpool.ac.uk/style/images/fileicons/text.png) |
Text
1805.04832v1.pdf - Submitted version Download (878kB) |
Abstract
We study population protocols: networks of anonymous agents that interact under a scheduler that picks pairs of agents uniformly at random. The _size counting problem_ is that of calculating the exact number $n$ of agents in the population, assuming no leader (each agent starts in the same state). We give the first protocol that solves this problem in sublinear time. The protocol converges in $O(\log n \log \log n)$ time and uses $O(n^{60})$ states ($O(1) + 60 \log n$ bits of memory per agent) with probability $1-O(\frac{\log \log n}{n})$. The time complexity is also $O(\log n \log \log n)$ in expectation. The time to converge is also $O(\log n \log \log n)$ in expectation. Crucially, unlike most published protocols with $\omega(1)$ states, our protocol is _uniform_: it uses the same transition algorithm for any population size, so does not need an estimate of the population size to be embedded into the algorithm. A sub-protocol is the first uniform sublinear-time leader election population protocol, taking $O(\log n \log \log n)$ time and $O(n^{18})$ states. The state complexity of both the counting and leader election protocols can be reduced to $O(n^{30})$ and $O(n^{9})$ respectively, while increasing the time to $O(\log^2 n)$.
| Item Type: | Article |
|---|---|
| Uncontrolled Keywords: | cs.DC, cs.DC, cs.CC |
| Depositing User: | Symplectic Admin |
| Date Deposited: | 22 May 2018 10:13 |
| Last Modified: | 19 Jan 2023 06:33 |
| Related URLs: | |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3021613 |
Share
Share
