Computation in networks of passively mobile finite-state sensors
From MaRDI portal
Publication:2375293
DOI10.1007/s00446-005-0138-3zbMath1266.68042WikidataQ62472222 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
mobile agent; diffuse computation; finite-state agent; intermittent communication; stable computation; sensor net
Related Items
Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, 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, Verification of Immediate Observation Population Protocols, Automatic Analysis of Expected Termination Time for Population Protocols, Leaderless Deterministic Chemical Reaction Networks, The Synergy of Finite State Machines, A Population Protocol for Exact Majority with O(log5/3 n) Stabilization Time and Theta(log n) States, Simple and Efficient Leader Election, Unnamed Item, Stable leader election in population protocols requires linear time, 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, An Introduction to Temporal Graphs: An Algorithmic Perspective*, Expressive Power of Broadcast Consensus Protocols, Fault tolerant network constructors, Structural Liveness of Immediate Observation Petri Nets, Finding Cut-Offs in Leaderless Rendez-Vous Protocols is Easy, 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, Uniform atomic broadcast and consensus in fully anonymous synchronous systems with crash failures, Connectivity Preserving Network Transformers, Stochastic analysis of average-based distributed algorithms, Convergecast and broadcast by power-aware mobile agents, Deterministic function computation with chemical reaction networks, Traveling salesman problems in temporal graphs, A simple population protocol for fast robust approximate majority, Anonymous asynchronous systems: the case of failure detectors, Tight complexity analysis of population protocols with cover times -- the ZebraNet example, The computational power of simple protocols for self-awareness on graphs, Loosely-stabilizing leader election in a population protocol model, Computational models for networks of tiny artifacts: a survey, Position discovery for a system of bouncing robots, Localization for a system of colliding robots, 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, Mediated population protocols, Strand algebras for DNA computing, A self-stabilizing transformer for population protocols with covering, Passively mobile communicating machines that use restricted space, On the power of synchronization between two adjacent processes, How to prove impossibility under global fairness: on space complexity of self-stabilizing leader election on a population protocol model, Space-efficient self-stabilizing counting population protocols on mobile sensor networks, Optimal dispersion on an anonymous ring in the presence of weak Byzantine robots, How many ants does it take to find the food?, Causality, influence, and computation in possibly disconnected synchronous dynamic networks, Population protocols with faulty interactions: the impact of a leader, Terminating distributed construction of shapes and patterns in a fair solution of automata, Breathe before speaking: efficient information dissemination despite noisy, limited and anonymous communication, Speed faults in computation by chemical reaction networks, Temporal network optimization subject to connectivity constraints, On the transformation capability of feasible mechanisms for programmable matter, On space complexity of self-stabilizing leader election in mediated population protocol, Anonymous and fault-tolerant shared-memory computing, The computational power of population protocols, Theory of reaction automata: a survey, Minimizing message size in stochastic communication patterns: fast self-stabilizing protocols with 3 bits, Leaderless deterministic chemical reaction networks, Constructing self-stabilizing oscillators in population protocols, Time-space trade-offs in population protocols for the majority problem, The complexity of verifying population protocols, Clocked population protocols, Towards efficient verification of population protocols, Composable computation in discrete chemical reaction networks, How many cooks spoil the soup?, On parallel time in population protocols, New bounds for the flock-of-birds problem, Distributed computation and reconfiguration in actively dynamic networks, Search by a metamorphic robotic system in a finite 2D square grid, Simple and fast approximate counting and leader election in populations, ppsim: a software package for efficiently simulating and visualizing population protocols, Population protocols with unreliable communication, On convergence and threshold properties of discrete Lotka-Volterra population protocols, Pushing lines helps: efficient universal centralised transformations for programmable matter, Controlling a random population, Fault-tolerant simulation of population protocols, Multi-scale verification of distributed synchronisation, Finding cut-offs in leaderless rendez-vous protocols is easy, Running time analysis of broadcast consensus protocols, Uniform bipartition in the population protocol model with arbitrary graphs, A survey of size counting in population protocols, Consensus in anonymous asynchronous systems with crash-recovery and omission failures, A calculus for collective-adaptive systems and its behavioural theory, Data collection in population protocols with non-uniformly random scheduler, Loosely-stabilizing leader election with polylogarithmic convergence time, Dynamic networks of finite state machines, Minimal output unstable configurations in chemical reaction networks and deciders, Fast computation by population protocols with a leader, Advances in parameterized verification of population protocols, The complexity of optimal design of temporally connected graphs, Computing in social networks, Effective storage capacity of labeled graphs, Simulating and model checking membrane systems using strategies in Maude, A combinatorial characterization of self-stabilizing population protocols, Population protocols: beyond runtime analysis, Protocols with constant local storage and unreliable communication, Survivability of bouncing robots, How Many Cooks Spoil the Soup?, Robustness of Expressivity in Chemical Reaction Networks, On the Runtime of Universal Coating for Programmable Matter, 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, Network Constructors: A Model for Programmable Matter, Distributed Patrolling with Two-Speed Robots (and an Application to Transportation), Mediated Population Protocols: Leader Election and Applications, Recent Advances in Population Protocols, Unnamed Item, 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, On Convergence and Threshold Properties of Discrete Lotka-Volterra Population Protocols, Polylogarithmic-Time Leader Election in Population Protocols, 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, Constant-Space Population Protocols for Uniform Bipartition
Uses Software
Cites Work
- 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
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
