Mediated population protocols

Michail, Othon ORCID: 0000-0002-6234-3960, Chatzigiannakis, Ioannis and Spirakis, Paul G ORCID: 0000-0001-5396-3749 (2011) Mediated population protocols. THEORETICAL COMPUTER SCIENCE, 412 (22). pp. 2434-2450.

Text tcs11b.pdf - Author Accepted Manuscript Download (479kB)

Abstract

We extend here the Population Protocol (PP) model of Angluin et al. (2004, 2006) [2,4] in order to model more powerful networks of resource-limited agents that are possibly mobile. The main feature of our extended model, called the Mediated Population Protocol (MPP) model, is to allow the edges of the interaction graph to have states that belong to a constant-size set. We then allow the protocol rules for pairwise interactions to modify the corresponding edge state. The descriptions of our protocols preserve both the uniformity and anonymity properties of PPs, that is, they do not depend on the size of the population and do not use unique identifiers. We focus on the computational power of the MPP model on complete interaction graphs and initially identical edges. We provide the following exact characterization of the class MPS of stably computable predicates: a predicate is in MPS iff it is symmetric and is in NSPACE(n2). © 2010 Elsevier B.V. All rights reserved.

Item Type:	Article
Uncontrolled Keywords:	Population protocol, Diffuse computation, Finite-state agent, Intermittent communication, Stable computation, Passive mobility
Depositing User:	Symplectic Admin
Date Deposited:	20 Sep 2016 07:30
Last Modified:	19 Jan 2023 07:29
DOI:	10.1016/j.tcs.2011.02.003
Related URLs:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3003387