|This site is powered by Aigaion - A PHP/Web based management system for shared and annotated bibliographies.
For more information visit Aigaion.nl.|
|Type of publication:||Article|
|Title||Terminating Population Protocols via some Minimal Global Knowledge Assumptions|
|Bibtex cite ID||RACTI-RU1-2015-3|
|Journal ||Journal of Parallel and Distributed Computing (JPDC)|
|Year published ||2015|
|Note ||To appear|
|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 represents a known upper bound on the cover time of a random walk. The cover-time service 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 log n with input commutativity, where n is the number of nodes in the network. We also give a log n-space, but nondeterministic this time, upper bound. Finally, we prove interesting similarities of this model to linear bounded automata.
MS15-JPDC.pdf (main file) |