Passively mobile communicating machines that use restricted space
From MaRDI portal
Publication:650876
DOI10.1016/J.TCS.2011.07.001zbMATH Open1228.68028arXiv1012.2440OpenAlexW2951788333WikidataQ57608057 ScholiaQ57608057MaRDI QIDQ650876FDOQ650876
Authors: Ioannis Chatzigiannakis, Othon Michail, Stavros Nikolaou, Andreas Pavlogiannis, P. G. Spirakis 
Publication date: 7 December 2011
Published in: Theoretical Computer Science (Search for Journal in Brave)
Abstract: 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 is that 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 communication 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 on each agent. We provide a protocol that generates unique ids from scratch only by using O(log n) memory, and use it to provide an exact characterization for the classes PMSPACE(f(n)) when f(n)={Omega}(log n): they are precisely the classes of all symmetric predicates in NSPACE(nf(n)). In this way, we provide a space hierarchy for the PM model when the memory bounds are {Omega}(log n). Finally, we explore the computability of the PM model when the protocols use o(loglog n) space per machine and prove that SEMILINEAR=PMSPACE(f(n)) when f(n)=o(loglog n), where SEMILINEAR denotes the class of the semilinear predicates. In fact, we prove that this bound acts as a threshold, so that SEMILINEAR is a proper subset of PMSPACE(f(n)) when f(n)=O(loglog n).
Full work available at URL: https://arxiv.org/abs/1012.2440
Recommendations
Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Distributed systems (68M14) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)
Cites Work
- Theoretical aspects of distributed computing in sensor networks.
- Computation in networks of passively mobile finite-state sensors
- Semigroups, Presburger formulas, and languages
- Title not available (Why is that?)
- Fast computation by population protocols with a leader
- Title not available (Why is that?)
- Nondeterministic Space is Closed under Complementation
- Stably computable predicates are semilinear
- Mediated population protocols
- A simple population protocol for fast robust approximate majority
- Turing machines with sublogarithmic space
- Title not available (Why is that?)
- On the convergence of population protocols when population goes to infinity
- Recent Advances in Population Protocols
- The Dynamics of Probabilistic Population Protocols
- All symmetric predicates in NSPACE\((n^{2})\) are stably computable by the mediated population protocol model
- Mediated Population Protocols
- Computational models for networks of tiny artifacts: a survey
- Names Trump Malice: Tiny Mobile Agents Can Tolerate Byzantine Failures
- Passively mobile communicating machines that use restricted space
- Counter machines and counter languages
- Self-stabilizing counting in mobile sensor networks
- Space hierarchy theorem revised.
Cited In (22)
- The computational power of simple protocols for self-awareness on graphs
- A survey of size counting in population protocols
- Computational models for networks of tiny artifacts: a survey
- Passively mobile communicating machines that use restricted space
- Fault-tolerant simulation of population protocols
- A Survey on Analog Models of Computation
- A Glimpse at Paul G. Spirakis
- Mediated population protocols
- Population protocols with faulty interactions: the impact of a leader
- Simple and efficient local codes for distributed stable network construction
- Homonym population protocols
- Causality, influence, and computation in possibly disconnected synchronous dynamic networks
- Simple and fast approximate counting and leader election in populations
- Population protocols with unreliable communication
- Clocked population protocols
- Terminating distributed construction of shapes and patterns in a fair solution of automata
- Message complexity of population protocols
- The complexity of verifying population protocols
- How many cooks spoil the soup?
- Connectivity Preserving Network Transformers
- How Many Cooks Spoil the Soup?
- Connectivity preserving network transformers
This page was built for publication: Passively mobile communicating machines that use restricted space
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q650876)
