The computational power of population protocols
From MaRDI portal
Publication:1954251
DOI10.1007/s00446-007-0040-2zbMath1266.68043arXivcs/0608084MaRDI 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
Related Items
Connectivity Preserving Network Transformers, Unnamed Item, Unnamed Item, A Survey on Analog Models of Computation, Verification of Immediate Observation Population Protocols, Flatness and Complexity of Immediate Observation Petri Nets, Simple and Efficient Leader Election, Unnamed Item, Model checking parameterized asynchronous shared-memory systems, 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, Threshold-based network structural dynamics, Threshold-based network structural dynamics, Expressive Power of Broadcast Consensus Protocols, Unnamed Item, Unnamed Item, 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, 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, Parameterized analysis of reconfigurable broadcast networks, Brief Announcement: Population Protocols Decide Double-exponential Thresholds, Solving the parity problem in one-dimensional cellular automata, A simple population protocol for fast robust approximate majority, Tight complexity analysis of population protocols with cover times -- the ZebraNet example, The computational power of simple protocols for self-awareness on graphs, Computational models for networks of tiny artifacts: a survey, Verification of population protocols, Connectivity preserving network transformers, Mediated population protocols, A self-stabilizing transformer for population protocols with covering, How to prove impossibility under global fairness: on space complexity of self-stabilizing leader election on a population protocol model, Homonym population protocols, Space-efficient self-stabilizing counting population protocols on mobile sensor networks, Causality, influence, and computation in possibly disconnected synchronous dynamic networks, Parameterized model checking of rendezvous systems, Terminating distributed construction of shapes and patterns in a fair solution of automata, On the transformation capability of feasible mechanisms for programmable matter, Amorphous computing: a research agenda for the near future, 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?, New bounds for the flock-of-birds problem, Distributed computation with continual population growth, Distributed computation and reconfiguration in actively dynamic networks, Simple and fast approximate counting and leader election in populations, Reasoning in large games with unboundedly many players, 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, Fault-tolerant simulation of population protocols, Robust biomolecular finite automata, Minimal output unstable configurations in chemical reaction networks and deciders, Noisy rumor spreading and plurality consensus, Analysis of fully distributed splitting and naming probabilistic procedures and applications, Fast computation by population protocols with a leader, Advances in parameterized verification of population protocols, Computing in social networks, A combinatorial characterization of self-stabilizing population protocols, Population protocols: beyond runtime analysis, Protocols with constant local storage and unreliable communication, How Many Cooks Spoil the Soup?, Programming Discrete Distributions with Chemical Reaction Networks, Robustness of Expressivity in Chemical Reaction Networks, Analysis of Fully Distributed Splitting and Naming Probabilistic Procedures and Applications, Shortest, Fastest, and Foremost Broadcast in Dynamic Networks, Distributed Patrolling with Two-Speed Robots (and an Application to Transportation), Unnamed Item, 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, On Convergence and Threshold Properties of Discrete Lotka-Volterra Population Protocols, Polylogarithmic-Time Leader Election in Population Protocols, On Space and Time Complexity of Loosely-Stabilizing Leader Election, Constant-Space Population Protocols for Uniform Bipartition
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
