License: 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: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9835/
Go to the corresponding LIPIcs Volume Portal

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:
LIPIcs-DISC-2018-46.pdf (0.3 MB)

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
Collection: 32nd International Symposium on Distributed Computing (DISC 2018)
Issue Date: 2018
Date of publication: 04.10.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI