Fast computation by population protocols with a leader
From MaRDI portal
Publication:2377254
DOI10.1007/s00446-008-0067-zzbMath1267.68306OpenAlexW2006072889MaRDI QIDQ2377254
Dana Angluin, David Eisenstat, James Aspnes
Publication date: 28 June 2013
Published in: Distributed Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00446-008-0067-z
Related Items
Deterministic function computation with chemical reaction networks, Population protocols with faulty interactions: the impact of a leader, Polylogarithmic-Time Leader Election in Population Protocols, Simple and fast approximate counting and leader election in populations, Unnamed Item, Analysis of Distributed Token Circulation Algorithm with Faulty Random Number Generator, Recent Advances in Population Protocols, On Space and Time Complexity of Loosely-Stabilizing Leader Election, Terminating distributed construction of shapes and patterns in a fair solution of automata, Advances in parameterized verification of population protocols, Leader Election Requires Logarithmic Time in Population Protocols, Constant-Space Population Protocols for Uniform Bipartition, Tight complexity analysis of population protocols with cover times -- the ZebraNet example, The computational power of simple protocols for self-awareness on graphs, The Power of Global Knowledge on Self-stabilizing Population Protocols, Democratic, existential, and consensus-based output conventions in stable computation by chemical reaction networks, Speed faults in computation by chemical reaction networks, Lower bounds on the state complexity of population protocols, On space complexity of self-stabilizing leader election in mediated population protocol, Fast and succinct population protocols for Presburger arithmetic, Computing with chemical reaction networks: a tutorial, Unnamed Item, A Near Time-optimal Population Protocol for Self-stabilizing Leader Election on Rings with a Poly-logarithmic Number of States, Population protocols: beyond runtime analysis, Unnamed Item, Passively mobile communicating machines that use restricted space, Computational models for networks of tiny artifacts: a survey, Fault-tolerant simulation of population protocols, Probabilistic Analysis of Rumor-Spreading Time, Running time analysis of broadcast consensus protocols, A survey of size counting in population protocols, Determining majority in networks with local interactions and very small local memory, Verification of population protocols, Mediated population protocols, Leaderless deterministic chemical reaction networks, Constructing self-stabilizing oscillators in population protocols, A self-stabilizing transformer for population protocols with covering, Unnamed Item, Stable leader election in population protocols requires linear time, Time-space trade-offs in population protocols for the majority problem, Loosely-stabilizing leader election with polylogarithmic convergence time, Clocked population protocols, Constructing Self-stabilizing Oscillators in Population Protocols, A Population Protocol for Exact Majority with O(log5/3 n) Stabilization Time and Theta(log n) States, Composable computation in discrete chemical reaction networks, Robustness of Expressivity in Chemical Reaction Networks, Computation with finite stochastic chemical reaction networks, On Gossip and Populations, How many cooks spoil the soup?, New bounds for the flock-of-birds problem, Distributed computation with continual population growth
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A simple population protocol for fast robust approximate majority
- The computational power of population protocols
- Computation in networks of passively mobile finite-state sensors
- Self-stabilizing clock synchronization in the presence of Byzantine faults
- A Simple Population Protocol for Fast Robust Approximate Majority
- Fast Computation by Population Protocols with a Leader
- Tail bounds for occupancy and the satisfiability threshold conjecture
- Stably computable predicates are semilinear
- Computation in networks of passively mobile finite-state sensors
