Homonym population protocols

DOI10.1007/S00224-017-9833-2zbMATH Open1392.68095arXiv1602.03540OpenAlexW2259303103MaRDI QIDQ722223FDOQ722223

Authors: Olivier Bournez, Johanne Cohen, Mikaël Rabie 

Publication date: 23 July 2018

Published in: Theory of Computing Systems (Search for Journal in Brave)

Abstract: The population protocol model was introduced by Angluin emph{et al.} as a model of passively mobile anonymous finite-state agents. This model computes a predicate on the multiset of their inputs via interactions by pairs. The original population protocol model has been proved to compute only semi-linear predicates and has been recently extended in various ways. In the community protocol model by Guerraoui and Ruppert, agents have unique identifiers but may only store a finite number of the identifiers they already heard about. The community protocol model provides the power of a Turing machine with a $O(nlogn)$ space. We consider variations on the two above models and we obtain a whole landscape that covers and extends already known results. Namely, by considering the case of homonyms, that is to say the case when several agents may share the same identifier, we provide a hierarchy that goes from the case of no identifier (population protocol model) to the case of unique identifiers (community protocol model). We obtain in particular that any Turing Machine on space $O(lo{g}^{O(1)}n)$ can be simulated with at least $O(lo{g}^{O(1)}n)$ identifiers, a result filling a gap left open in all previous studies. Our results also extend and revisit in particular the hierarchy provided by Chatzigiannakis emph{et al.} on population protocols carrying Turing Machines on limited space, solving the problem of the gap left by this work between per-agent space $o(loglogn)$ (proved to be equivalent to population protocols) and $O(logn)$ (proved to be equivalent to Turing machines).

Full work available at URL: https://arxiv.org/abs/1602.03540

Recommendations

• The computational power of population protocols
• Population protocols on graphs: a hierarchy
• Global versus local computations: fast computing with identifiers (short paper)
• Mediated population protocols
• Global versus local computations: fast computing with identifiers

zbMATH Keywords

distributed computingcomputation theorypopulation protocolsanonymitymodels of computationhomonyms

Mathematics Subject Classification ID

Distributed systems (68M14) Network protocols (68M12)

Cites Work

• The computational power of population protocols
• Title not available (Why is that?)
• Nondeterministic Space is Closed under Complementation
• The method of forced enumeration for nondeterministic automata
• Storage Modification Machines
• Names Trump Malice: Tiny Mobile Agents Can Tolerate Byzantine Failures
• Computation in networks of passively mobile finite-state sensors
• Byzantine agreement with homonyms
• Passively mobile communicating machines that use restricted space
• Homonym population protocols

Cited In (6)

• Passively mobile communicating machines that use restricted space
• A Survey on Analog Models of Computation
• Global versus local computations: fast computing with identifiers
• Global versus local computations: fast computing with identifiers (short paper)
• Homonym population protocols
• Population protocols on graphs: a hierarchy

This page was built for publication: Homonym population protocols

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q722223)