Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.DISC.2018.46
URN: urn:nbn:de:0030-drops-98359
URL: https://drops.dagstuhl.de/opus/volltexte/2018/9835/
Doty, David ; Eftekhari, Mahsa ; Michail, Othon ; Spirakis, Paul G. ; Theofilatos, Michail
Brief Announcement: Exact Size Counting in Uniform Population Protocols in Nearly Logarithmic Time
| pdf-format: |
|
Abstract
We study population protocols: networks of anonymous agents whose pairwise interactions are chosen 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((log log n)/n). 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.
BibTeX - Entry
@InProceedings{doty_et_al:LIPIcs:2018:9835,
author = {David Doty and Mahsa Eftekhari and Othon Michail and Paul G. Spirakis and Michail Theofilatos},
title = {{Brief Announcement: Exact Size Counting in Uniform Population Protocols in Nearly Logarithmic Time}},
booktitle = {32nd International Symposium on Distributed Computing (DISC 2018)},
pages = {46:1--46:3},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-092-7},
ISSN = {1868-8969},
year = {2018},
volume = {121},
editor = {Ulrich Schmid and Josef Widder},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9835},
URN = {urn:nbn:de:0030-drops-98359},
doi = {10.4230/LIPIcs.DISC.2018.46},
annote = {Keywords: population protocol, counting, leader election, polylogarithmic time}
}
| Keywords: | population protocol, counting, leader election, polylogarithmic time | |
| Seminar: | 32nd International Symposium on Distributed Computing (DISC 2018) | |
| Issue date: | 2018 | |
| Date of publication: | 04.10.2018 |
