Passively mobile communicating machines that use restricted space

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 PM-SPACE(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) = Ω(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 Ω(log n). Finally, we establish that the minimal space requirement for the computation of non-semilinear predicates is O(log log n). © 2011 ACM.