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:Inproceedings
Entered by:
TitleAll Symmetric Predicates in NSPACE(n^2) are Stably Computable by the Mediated Population Protocol Model
Bibtex cite IDRACTI-RU1-2010-7
Booktitle 35th International Symposium on Mathematical Foundations of Computer Science (MFCS)
Series Lecture Notes in Computer Science
Year published 2010
Month August
Publisher Springer-Verlag Berlin Heidelberg
Location Brno, Czech Republic
Keywords population protocols,mediated population protocols,diffuse computation,passive mobility,wireless sensor networks,stable computation
This work focuses on the computational power of the Mediated Population Protocol model on complete communication graphs and initially identical edges (SMPP). In particular, we investigate the class MPS of all predicates that are stably computable by the SMPP model. It is already known that MPS is in the symmetric subclass of NSPACE(n^2). Here we prove that this inclusion holds with equality, thus, providing the following exact characterization for MPS: A predicate is in MPS iff it is symmetric and is in NSPACE(n^2).
Chatzigiannakis, Ioannis
Michail, Othon
Nikolaou, Stavros
Pavlogiannis, Andreas
Spirakis, Paul
mfcs10 - proceedings - CMNPS.pdf (main file)
mfcs10 - TechReport - CMNPS.pdf
Publication ID733