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 ).