Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH scholarly article en Blondin, Michael; Esparza, Javier; Jaax, Stefan http://www.dagstuhl.de/lipics License
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-85116
URL:

; ;

Large Flocks of Small Birds: on the Minimal Size of Population Protocols

pdf-format:


Abstract

Population protocols are a well established model of distributed computation by mobile finite-state agents with very limited storage. A classical result establishes that population protocols compute exactly predicates definable in Presburger arithmetic. We initiate the study of the minimal amount of memory required to compute a given predicate as a function of its size. We present results on the predicates x >= n for n \in N, and more generally on the predicates corresponding to systems of linear inequalities. We show that they can be computed by protocols with O(log n) states (or, more generally, logarithmic in the coefficients of the predicate), and that, surprisingly, some families of predicates can be computed by protocols with O(log log n) states. We give essentially matching lower bounds for the class of 1-aware protocols.

BibTeX - Entry

@InProceedings{blondin_et_al:LIPIcs:2018:8511,
  author =	{Michael Blondin and Javier Esparza and Stefan Jaax},
  title =	{{Large Flocks of Small Birds: on the Minimal Size of Population Protocols}},
  booktitle =	{35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)},
  pages =	{16:1--16:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-062-0},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{96},
  editor =	{Rolf Niedermeier and Brigitte Vall{\'e}e},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8511},
  URN =		{urn:nbn:de:0030-drops-85116},
  doi =		{10.4230/LIPIcs.STACS.2018.16},
  annote =	{Keywords: Population protocols, Presburger arithmetic}
}

Keywords: Population protocols, Presburger arithmetic
Seminar: 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)
Issue date: 2018
Date of publication: 2018


DROPS-Home | Fulltext Search | Imprint Published by LZI