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:Article
Entered by:ichatz
TitleMediated Population Protocols
Bibtex cite IDRACTI-RU1-2011-12
Journal Theoretical Computer Science
Year published 2011
Month May
Volume 412
Number 22
Pages 2434-2450
DOI 10.1016/j.tcs.2011.02.003
We extend here the Population Protocol model of Angluin et al. [2004,2006] 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 edges of the communication 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. Protocol specifications preserve both uniformity and anonymity. We first focus on the computational power of the MPP model on complete communication graphs and initially identical edges. We provide the following exact characterization for the class MPS of stably computable predicates: A predicate is in MPS iff it is symmetric and is in NSPACE(n^2)$. We finally ignore the input to the agents and study MPP's ability to compute graph properties.
Michail, Othon
Chatzigiannakis, Ioannis
Spirakis, Paul
tcs10.pdf (main file)
Publication ID852