research unit 1

This site is powered by Aigaion - A PHP/Web based management system for shared and annotated bibliographies. For more information visit


Type of publication:Inproceedings
Entered by:
TitleTerminating Population Protocols via some Minimal Global Knowledge Assumptions
Bibtex cite IDRACTI-RU1-2012-24
Booktitle 14th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS 2012)
Series Lecture Notes in Computer Science
Year published 2012
Volume 7596
Pages 77-89
Publisher Springer-Verlag Berlin Heidelberg
DOI 10.1007/978-3-642-33536-5_8
Keywords population protocol,cover-time service,rendezvous-based communication,interaction,counter machine,absence detector,linear-bounded automaton
We extend the population protocol model with a cover-time service that informs a walking state every time it covers the whole network. This is simply a known upper bound on the cover time of a random walk. This allows us to introduce termination into population protocols, a capability that is crucial for any distributed system. By reduction to an oracle-model we arrive at a very satisfactory lower bound on the computational power of the model: we prove that it is at least as strong as a Turing Machine of space logn with input commutativity, where n is the number of nodes in the network. We also give a logn-space, but nondeterministic this time, upper bound. Finally, we prove interesting similarities of this model to linear bounded automata.
Michail, Othon
Chatzigiannakis, Ioannis
Spirakis, Paul
MCS-SSS12.pdf (main file)
Publication ID973