Computation in networks of passively mobile finite-state sensors

DOI10.1007/s00446-005-0138-3zbMath1266.68042OpenAlexW2706788079WikidataQ62472222 ScholiaQ62472222MaRDI QIDQ2375293

Michael J. Fischer, Dana Angluin, Zoë Diamadi, James Aspnes

Publication date: 13 June 2013

Published in: Distributed Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00446-005-0138-3

zbMATH Keywords

mobile agentdiffuse computationfinite-state agentintermittent communicationstable computationsensor net

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Distributed systems (68M14)

Related Items

Distributed computation and reconfiguration in actively dynamic networks, Deterministic function computation with chemical reaction networks, Optimal dispersion on an anonymous ring in the presence of weak Byzantine robots, Traveling salesman problems in temporal graphs, Population protocols with faulty interactions: the impact of a leader, On Convergence and Threshold Properties of Discrete Lotka-Volterra Population Protocols, Polylogarithmic-Time Leader Election in Population Protocols, Search by a metamorphic robotic system in a finite 2D square grid, Simple and fast approximate counting and leader election in populations, Fast computation by population protocols with a leader, ppsim: a software package for efficiently simulating and visualizing population protocols, Computing in social networks, Effective storage capacity of labeled graphs, Recent Advances in Population Protocols, Population protocols with unreliable communication, Information Spreading by Mobile Particles on a Line, On Space and Time Complexity of Loosely-Stabilizing Leader Election, A Glimpse at Paul G. Spirakis, An Introduction to Temporal Graphs: An Algorithmic Perspective, Terminating distributed construction of shapes and patterns in a fair solution of automata, A simple population protocol for fast robust approximate majority, Advances in parameterized verification of population protocols, Anonymous asynchronous systems: the case of failure detectors, On convergence and threshold properties of discrete Lotka-Volterra population protocols, Constant-Space Population Protocols for Uniform Bipartition, The complexity of optimal design of temporally connected graphs, Simulating and model checking membrane systems using strategies in Maude, Pushing lines helps: efficient universal centralised transformations for programmable matter, A combinatorial characterization of self-stabilizing population protocols, Tight complexity analysis of population protocols with cover times -- the ZebraNet example, The computational power of simple protocols for self-awareness on graphs, Shortest, Fastest, and Foremost Broadcast in Dynamic Networks, Synthesizing and Tuning Chemical Reaction Networks with Specified Behaviours, Leader Election and Shape Formation with Self-organizing Programmable Matter, Breathe before speaking: efficient information dissemination despite noisy, limited and anonymous communication, Speed faults in computation by chemical reaction networks, How many ants does it take to find the food?, On space complexity of self-stabilizing leader election in mediated population protocol, Causality, influence, and computation in possibly disconnected synchronous dynamic networks, A stochastic approach to shortcut bridging in programmable matter, Controlling a random population, Population protocols: beyond runtime analysis, Network Constructors: A Model for Programmable Matter, Loosely-stabilizing leader election in a population protocol model, Protocols with constant local storage and unreliable communication, Anonymous and fault-tolerant shared-memory computing, The computational power of population protocols, Unnamed Item, Distributed Patrolling with Two-Speed Robots (and an Application to Transportation), Passively mobile communicating machines that use restricted space, Computational models for networks of tiny artifacts: a survey, Fault-tolerant simulation of population protocols, Mediated Population Protocols: Leader Election and Applications, Multi-scale verification of distributed synchronisation, On the power of synchronization between two adjacent processes, Finding cut-offs in leaderless rendez-vous protocols is easy, Running time analysis of broadcast consensus protocols, Temporal network optimization subject to connectivity constraints, Uniform bipartition in the population protocol model with arbitrary graphs, Position discovery for a system of bouncing robots, Localization for a system of colliding robots, On the transformation capability of feasible mechanisms for programmable matter, Theory of reaction automata: a survey, A survey of size counting in population protocols, Consensus in anonymous asynchronous systems with crash-recovery and omission failures, Determining majority in networks with local interactions and very small local memory, Verification of population protocols, Connectivity preserving network transformers, Universal coating for programmable matter, How to prove impossibility under global fairness: on space complexity of self-stabilizing leader election on a population protocol model, Minimizing message size in stochastic communication patterns: fast self-stabilizing protocols with 3 bits, Mediated population protocols, Leaderless deterministic chemical reaction networks, Strand algebras for DNA computing, Constructing self-stabilizing oscillators in population protocols, A self-stabilizing transformer for population protocols with covering, A calculus for collective-adaptive systems and its behavioural theory, Time-space trade-offs in population protocols for the majority problem, The complexity of verifying population protocols, Data collection in population protocols with non-uniformly random scheduler, Loosely-stabilizing leader election with polylogarithmic convergence time, Clocked population protocols, Dynamic networks of finite state machines, Space-efficient self-stabilizing counting population protocols on mobile sensor networks, Reachability Problems for Continuous Chemical Reaction Networks, Survivability of bouncing robots, Towards efficient verification of population protocols, Minimal output unstable configurations in chemical reaction networks and deciders, Composable computation in discrete chemical reaction networks, How Many Cooks Spoil the Soup?, Robustness of Expressivity in Chemical Reaction Networks, On the Runtime of Universal Coating for Programmable Matter, On Gossip and Populations, Space Complexity of Self-stabilizing Leader Election in Passively-Mobile Anonymous Agents, Characterizing Topological Assumptions of Distributed Algorithms in Dynamic Networks, Loosely-Stabilizing Leader Election in Population Protocol Model, How many cooks spoil the soup?, On parallel time in population protocols, New bounds for the flock-of-birds problem, Convergecast and broadcast by power-aware mobile agents, Data Collection in Population Protocols with Non-uniformly Random Scheduler, Improved Leader Election for Self-organizing Programmable Matter, Leader Election Requires Logarithmic Time in Population Protocols, On Verifying and Maintaining Connectivity of Interval Temporal Networks, The Power of Global Knowledge on Self-stabilizing Population Protocols, Fault tolerant network constructors, Structural Liveness of Immediate Observation Petri Nets, Computing with biological switches and clocks, Finding Cut-Offs in Leaderless Rendez-Vous Protocols is Easy, Democratic, existential, and consensus-based output conventions in stable computation by chemical reaction networks, Lower bounds on the state complexity of population protocols, The canonical amoebot model: algorithms and concurrency control, On geometric shape construction via growth operations, Centralised connectivity-preserving transformations by rotation: 3 musketeers for all orthogonal convex shapes, On geometric shape construction via growth operations, Fast and succinct population protocols for Presburger arithmetic, Computing with chemical reaction networks: a tutorial, Approximate majority analyses using tri-molecular chemical reaction networks, Uniform atomic broadcast and consensus in fully anonymous synchronous systems with crash failures, Unnamed Item, Parameterized analysis of reconfigurable broadcast networks, A Near Time-optimal Population Protocol for Self-stabilizing Leader Election on Rings with a Poly-logarithmic Number of States, Brief Announcement: Population Protocols Decide Double-exponential Thresholds, Computational Complexity of Atomic Chemical Reaction Networks, Simple and Efficient Leader Election, Expressive Power of Broadcast Consensus Protocols, Verification of Immediate Observation Population Protocols, Automatic Analysis of Expected Termination Time for Population Protocols, Leaderless Deterministic Chemical Reaction Networks, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Stable leader election in population protocols requires linear time, Unnamed Item, Connectivity Preserving Network Transformers, Simple and efficient local codes for distributed stable network construction, On efficient connectivity-preserving transformations in a grid, Wait-free solvability of colorless tasks in anonymous shared-memory model, Centralised connectivity-preserving transformations for programmable matter: a minimal seed approach, Centralised connectivity-preserving transformations for programmable matter: a minimal seed approach, Distributed transformations of Hamiltonian shapes based on line moves, Distributed transformations of Hamiltonian shapes based on line moves, Threshold-based network structural dynamics, Threshold-based network structural dynamics, The Synergy of Finite State Machines, A Population Protocol for Exact Majority with O(log5/3 n) Stabilization Time and Theta(log n) States, Stochastic analysis of average-based distributed algorithms, An Introduction to Temporal Graphs: An Algorithmic Perspective^*

Uses Software

• TAG

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The chemical abstract machine
• Catalytic P systems, semilinear sets, and vector addition systems
• Semigroups, Presburger formulas, and languages
• On Communicating Finite-State Machines
• Nondeterministic Space is Closed under Complementation
• On Context-Free Languages