Fast computation by population protocols with a leader

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

Mathematics Subject Classification ID

Distributed algorithms (68W15)

Related Items (51)

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

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Fast computation by population protocols with a leader