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.2020.6
URN: urn:nbn:de:0030-drops-130848
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/13084/
Amir, Talley ;
Aspnes, James ;
Doty, David ;
Eftekhari, Mahsa ;
Severson, Eric
Message Complexity of Population Protocols
Abstract
The standard population protocol model assumes that when two agents interact, each observes the entire state of the other. We initiate the study of message complexity for population protocols, where an agent’s state is divided into an externally-visible message and externally-hidden local state.
We consider the case of O(1) message complexity. When time is unrestricted, we obtain an exact characterization of the stably computable predicates based on the number of internal states s(n): If s(n) = o(n) then the protocol computes semilinear predicates (unlike the original model, which can compute non-semilinear predicates with s(n) = O(log n)), and otherwise it computes a predicate decidable by a nondeterministic O(n log s(n))-space-bounded Turing machine. We then introduce novel O(polylog(n)) expected time protocols for junta/leader election and general purpose broadcast correct with high probability, and approximate and exact population size counting correct with probability 1. Finally, we show that the main constraint on the power of bounded-message-size protocols is the size of the internal states: with unbounded internal states, any computable function can be computed with probability 1 in the limit by a protocol that uses only 1-bit messages.
BibTeX - Entry
@InProceedings{amir_et_al:LIPIcs:2020:13084,
author = {Talley Amir and James Aspnes and David Doty and Mahsa Eftekhari and Eric Severson},
title = {{Message Complexity of Population Protocols}},
booktitle = {34th International Symposium on Distributed Computing (DISC 2020)},
pages = {6:1--6:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-168-9},
ISSN = {1868-8969},
year = {2020},
volume = {179},
editor = {Hagit Attiya},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/13084},
URN = {urn:nbn:de:0030-drops-130848},
doi = {10.4230/LIPIcs.DISC.2020.6},
annote = {Keywords: population protocol, message complexity, space-optimal}
}
