The computational power of population protocols

DOI10.1007/s00446-007-0040-2zbMath1266.68043arXivcs/0608084OpenAlexW2123429492MaRDI QIDQ1954251

David Eisenstat, Eric Ruppert, James Aspnes, Dana Angluin

Publication date: 20 June 2013

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

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

Mathematics Subject Classification ID

Distributed systems (68M14) Theory of computing (68Q99)

Related Items

Distributed computation and reconfiguration in actively dynamic networks, Solving the parity problem in one-dimensional cellular automata, On Convergence and Threshold Properties of Discrete Lotka-Volterra Population Protocols, Polylogarithmic-Time Leader Election in Population Protocols, Simple and fast approximate counting and leader election in populations, Parameterized model checking of rendezvous systems, Fast computation by population protocols with a leader, Unnamed Item, Computing in social networks, Recent Advances in Population Protocols, Reasoning in large games with unboundedly many players, Population protocols with unreliable communication, On Space and Time Complexity of Loosely-Stabilizing Leader Election, 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, On convergence and threshold properties of discrete Lotka-Volterra population protocols, Constant-Space Population Protocols for Uniform Bipartition, 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, Fault tolerant network constructors, Structural Liveness of Immediate Observation Petri Nets, Democratic, existential, and consensus-based output conventions in stable computation by chemical reaction networks, Programming discrete distributions with chemical reaction networks, Lower bounds on the state complexity of population protocols, On geometric shape construction via growth operations, Causality, influence, and computation in possibly disconnected synchronous dynamic networks, On geometric shape construction via growth operations, Fast and succinct population protocols for Presburger arithmetic, Parameterized Analysis of Immediate Observation Petri Nets, Computing with chemical reaction networks: a tutorial, Unnamed Item, Parameterized analysis of reconfigurable broadcast networks, Brief Announcement: Population Protocols Decide Double-exponential Thresholds, Population protocols: beyond runtime analysis, Protocols with constant local storage and unreliable communication, Unnamed Item, Unnamed Item, Unnamed Item, Simple and Efficient Leader Election, Distributed Patrolling with Two-Speed Robots (and an Application to Transportation), Computational models for networks of tiny artifacts: a survey, Fault-tolerant simulation of population protocols, Model checking parameterized asynchronous shared-memory systems, Expressive Power of Broadcast Consensus Protocols, Verification of Immediate Observation Population Protocols, On the transformation capability of feasible mechanisms for programmable matter, Verification of population protocols, Connectivity preserving network transformers, How to prove impossibility under global fairness: on space complexity of self-stabilizing leader election on a population protocol model, Mediated population protocols, Amorphous computing: a research agenda for the near future, Constructing self-stabilizing oscillators in population protocols, A self-stabilizing transformer for population protocols with covering, Unnamed Item, Unnamed Item, Stable leader election in population protocols requires linear time, Time-space trade-offs in population protocols for the majority problem, The complexity of verifying population protocols, Homonym population protocols, Connectivity Preserving Network Transformers, Simple and efficient local codes for distributed stable network construction, Clocked population protocols, On efficient connectivity-preserving transformations in a grid, Threshold-based network structural dynamics, Space-efficient self-stabilizing counting population protocols on mobile sensor networks, Threshold-based network structural dynamics, Robust biomolecular finite automata, Towards efficient verification of population protocols, Flatness and Complexity of Immediate Observation Petri Nets, Minimal output unstable configurations in chemical reaction networks and deciders, Composable computation in discrete chemical reaction networks, Noisy rumor spreading and plurality consensus, How Many Cooks Spoil the Soup?, Programming Discrete Distributions with Chemical Reaction Networks, Robustness of Expressivity in Chemical Reaction Networks, 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, How many cooks spoil the soup?, New bounds for the flock-of-birds problem, Analysis of fully distributed splitting and naming probabilistic procedures and applications, Distributed computation with continual population growth, Analysis of Fully Distributed Splitting and Naming Probabilistic Procedures and Applications, A Survey on Analog Models of Computation

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Space efficient processor identity protocol
• The processor identity problem
• On the reachability problem for 5-dimensional vector addition systems
• Computing in totally anonymous asynchronous shared memory systems
• Catalytic P systems, semilinear sets, and vector addition systems
• On the importance of having an identity or, is consensus really universal?
• Anonymous and fault-tolerant shared-memory computing
• Computation in networks of passively mobile finite-state sensors
• Comparison of initial conditions for distributed algorithms on anonymous networks
• Computing anonymously with arbitrary knowledge
• Fast Computation by Population Protocols with a Leader
• Wait-free consensus with infinite arrivals
• The Las-Vegas Processor Identity Problem (How and When to Be Unique)
• Stably computable predicates are semilinear
• Computation in networks of passively mobile finite-state sensors
• On Context-Free Languages
• Ordering by Divisibility in Abstract Algebras