Terminating population protocols via some minimal global knowledge assumptions

Michail, Othon ORCID: 0000-0002-6234-3960 and Spirakis, Paul G ORCID: 0000-0001-5396-3749 (2015) Terminating population protocols via some minimal global knowledge assumptions. JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING, 81-82. pp. 1-10.

Text jpdc15.pdf - Author Accepted Manuscript Download (302kB)

Abstract

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 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.

Item Type:	Article
Uncontrolled Keywords:	Population protocol, Cover-time service, Rendezvous-based communication, Interaction, Counter machine, Absence detector, Linear-bounded automaton
Depositing User:	Symplectic Admin
Date Deposited:	20 Sep 2016 07:31
Last Modified:	19 Jan 2023 07:29
DOI:	10.1016/j.jpdc.2015.02.005
Related URLs:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3003386