Passively mobile communicating machines that use restricted space

DOI10.1016/J.TCS.2011.07.001MaRDI QIDQ650876zbMATH OpenOpenAlexWikidataFDO

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)

Full work available at URL https://arxiv.org/abs/1012.2440

zbMATH Keywords

distributed computingdiffuse computationpassive mobilitypervasive environments

Mathematics Subject Classification ID

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)

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

Recommendations

• Computation in networks of passively mobile finite-state sensors
• Computation in networks of passively mobile finite-state sensors
• Homonym population protocols
• Computational models for networks of tiny artifacts: a survey
• The computational power of population protocols

Cites work

• scientific article; zbMATH DE number 5605125 (Why is no real title available?)
• scientific article; zbMATH DE number 3917711 (Why is no real title available?)
• scientific article; zbMATH DE number 3363526 (Why is no real title available?)
• A simple population protocol for fast robust approximate majority
• All symmetric predicates in NSPACE\((n^{2})\) are stably computable by the mediated population protocol model
• Computation in networks of passively mobile finite-state sensors
• Computational models for networks of tiny artifacts: a survey
• Counter machines and counter languages
• Fast computation by population protocols with a leader
• Mediated Population Protocols
• Mediated population protocols
• Names Trump Malice: Tiny Mobile Agents Can Tolerate Byzantine Failures
• Nondeterministic Space is Closed under Complementation
• On the convergence of population protocols when population goes to infinity
• Passively mobile communicating machines that use restricted space
• Recent Advances in Population Protocols
• Self-stabilizing counting in mobile sensor networks
• Semigroups, Presburger formulas, and languages
• Space hierarchy theorem revised.
• Stably computable predicates are semilinear
• The Dynamics of Probabilistic Population Protocols
• Theoretical aspects of distributed computing in sensor networks.
• Turing machines with sublogarithmic space

Cited in

(22)

• The computational power of simple protocols for self-awareness on graphs
• A survey of size counting in population protocols
• Connectivity preserving network transformers
• 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
• Mediated population protocols
• 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
• Computation in networks of passively mobile finite-state sensors
• Terminating distributed construction of shapes and patterns in a fair solution of automata
• Clocked population protocols
• Computation in networks of passively mobile finite-state sensors
• Message complexity of population protocols
• The complexity of verifying population protocols
• How many cooks spoil the soup?
• A glimpse at Paul G. Spirakis
• Connectivity preserving network transformers
• How Many Cooks Spoil the Soup?

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)