کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
432672 | 689026 | 2015 | 10 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Terminating population protocols via some minimal global knowledge assumptions Terminating population protocols via some minimal global knowledge assumptions](/preview/png/432672.png)
• We introduce a variant of population protocols capable of termination.
• The ability to terminate is modeled by an oracle detecting absence of states.
• We prove that the new model simulates Turing Machines of space lognlogn.
• We demonstrate similarities to linear bounded automata.
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 lognlognwith input commutativity , where nn is the number of nodes in the network. We also give a lognlogn-space, but nondeterministic this time, upper bound. Finally, we prove interesting similarities of this model to linear bounded automata.
Journal: Journal of Parallel and Distributed Computing - Volumes 81–82, July 2015, Pages 1–10