%0 Report %1 journals/corr/abs-1004-3395 %A Chatzigiannakis, Ioannis %A Michail, Othon %A Nikolaou, Stavros %A Pavlogiannis, Andreas %A Spirakis, Paul G. %D 2010 %K logspace populationprotocols %T Passively mobile communicating logarithmic space machines %U https://arxiv.org/abs/1004.3395 %X We propose a new theoretical model for passively mobile Wireless Sensor Networks. We call it the PALOMA model, standing for PAssively mobile LOgarithmic space MAchines. The main modification w.r.t. the Population Protocol model 2 is that agents now, instead of being automata, are Turing Machines whose memory is logarithmic in the population size n. Note that the new model is still easily implementable with current technology. We focus on complete communication graphs. We define the complexity class P LM , consisting of all symmetric predicates on input assignments that are stably computable by the PALOMA model. We assume that the agents are initially identical. Surprisingly, it turns out that the PALOMA model can assign unique consecutive ids to the agents and inform them of the population size! This allows us to give a direct simulation of a Deterministic Turing Machine of O(n log n) space, thus, establishing that any symmetric predicate in SP ACE(n log n) also belongs to P LM . We next prove that the PALOMA model can simulate the Community Protocol model 15, thus, improving the previous lower bound to all symmetric predicates in N SP ACE(n log n). Going one step further, we generalize the simulation of the deterministic TM to prove that the PALOMA model can simulate a Nondeterministic TM of O(n log n) space. Although providing the same lower bound, the important remark here is that the bound is now obtained in a direct manner, in the sense that it does not depend on the simulation of a TM by a Pointer Machine. Finally, by showing that a Nondeterministic TM of O(n log n) space decides any language stably computable by the PALOMA model, we end up with an exact characterization for P LM : it is precisely the class of all symmetric predicates in N SP ACE(n log n).

@techreport{journals/corr/abs-1004-3395, abstract = {We propose a new theoretical model for passively mobile Wireless Sensor Networks. We call it the PALOMA model, standing for PAssively mobile LOgarithmic space MAchines. The main modification w.r.t. the Population Protocol model [2] is that agents now, instead of being automata, are Turing Machines whose memory is logarithmic in the population size n. Note that the new model is still easily implementable with current technology. We focus on complete communication graphs. We define the complexity class P LM , consisting of all symmetric predicates on input assignments that are stably computable by the PALOMA model. We assume that the agents are initially identical. Surprisingly, it turns out that the PALOMA model can assign unique consecutive ids to the agents and inform them of the population size! This allows us to give a direct simulation of a Deterministic Turing Machine of O(n log n) space, thus, establishing that any symmetric predicate in SP ACE(n log n) also belongs to P LM . We next prove that the PALOMA model can simulate the Community Protocol model [15], thus, improving the previous lower bound to all symmetric predicates in N SP ACE(n log n). Going one step further, we generalize the simulation of the deterministic TM to prove that the PALOMA model can simulate a Nondeterministic TM of O(n log n) space. Although providing the same lower bound, the important remark here is that the bound is now obtained in a direct manner, in the sense that it does not depend on the simulation of a TM by a Pointer Machine. Finally, by showing that a Nondeterministic TM of O(n log n) space decides any language stably computable by the PALOMA model, we end up with an exact characterization for P LM : it is precisely the class of all symmetric predicates in N SP ACE(n log n).}, added-at = {2019-02-01T16:23:11.000+0100}, author = {Chatzigiannakis, Ioannis and Michail, Othon and Nikolaou, Stavros and Pavlogiannis, Andreas and Spirakis, Paul G.}, biburl = {https://www.bibsonomy.org/bibtex/2e2a09a0bfb1421ebed29a24597b57342/paves_intern}, description = {An agent model with general-logspace local storage, contrast to Community protocols with restricted-purpose constant-identifier-capacity storage.}, interhash = {0c66a18d2c3952974a952d26f8940907}, intrahash = {e2a09a0bfb1421ebed29a24597b57342}, keywords = {logspace populationprotocols}, timestamp = {2019-02-12T16:10:37.000+0100}, title = {Passively mobile communicating logarithmic space machines}, url = {https://arxiv.org/abs/1004.3395}, year = 2010 }