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:
TitlePassively Mobile Communicating Machines that Use Restricted Space
Bibtex cite IDRACTI-RU1-2011-16
Booktitle 7th ACM SIGACT/SIGMOBILE International Workshop on Foundations of Mobile Computing (FOMC)
Series FOMC '11
Year published 2011
Month June
Pages 6-15
Publisher ACM
Location San Jose, California, USA
DOI 10.1145/1998476.1998480
Keywords population protocols,communicating machines,diffuse computation,passively mobility,sensor network
We propose a new theoretical model for passively mobile Wireless Sensor Networks, called PM, standing for Passively mobile Machines. The main modification w.r.t. the Population Protocol model [Angluin et al. 2006] is that the agents now, instead of being automata, are Turing Machines. We provide general definitions for unbounded memories, but we are mainly interested in computations upper-bounded by plausible space limitations. However, we prove that our results hold for more general cases. We focus on complete interaction graphs and define the complexity classes PMSPACE(f(n)) parametrically, consisting of all predicates that are stably computable by some PM protocol that uses O(f(n)) memory in each agent. We provide a protocol that generates unique identifiers from scratch only by using O(log n) memory, and use it to provide an exact characterization of the classes PMSPACE(f(n)) when f(n)=Omega(log n): they are precisely the classes of all symmetric predicates in NSPACE(nf(n)). As a consequence, we obtain a space hierarchy of the PM model when the memory bounds are Omega(log n). Finally, we establish that the minimal space requirement for the computation of non-semilinear predicates is O(log log n).
Chatzigiannakis, Ioannis
Michail, Othon
Nikolaou, Stavros
Pavlogiannis, Andreas
Spirakis, Paul
fomc11.pdf (main file)
Publication ID865