Polylogarithmic-Time Leader Election in Population Protocols

DOI10.1007/978-3-662-47666-6_38zbMath1434.68042arXiv1502.05745OpenAlexW2399651233MaRDI QIDQ3449497

Dan Alistarh, Rati Gelashvili

Publication date: 4 November 2015

Published in: Automata, Languages, and Programming (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Distributed systems (68M14) Network protocols (68M12)

Related Items (21)

Population protocols with faulty interactions: the impact of a leader ⋮ Simple and fast approximate counting and leader election in populations ⋮ ppsim: a software package for efficiently simulating and visualizing population protocols ⋮ On Space and Time Complexity of Loosely-Stabilizing Leader Election ⋮ Leader Election Requires Logarithmic Time in Population Protocols ⋮ Constant-Space Population Protocols for Uniform Bipartition ⋮ The Power of Global Knowledge on Self-stabilizing Population Protocols ⋮ Democratic, existential, and consensus-based output conventions in stable computation by chemical reaction networks ⋮ Unnamed Item ⋮ Simple and Efficient Leader Election ⋮ Fault-tolerant simulation of population protocols ⋮ Uniform bipartition in the population protocol model with arbitrary graphs ⋮ A survey of size counting in population protocols ⋮ Minimizing message size in stochastic communication patterns: fast self-stabilizing protocols with 3 bits ⋮ Unnamed Item ⋮ Stable leader election in population protocols requires linear time ⋮ Data collection in population protocols with non-uniformly random scheduler ⋮ Loosely-stabilizing leader election with polylogarithmic convergence time ⋮ How Many Cooks Spoil the Soup? ⋮ Robustness of Expressivity in Chemical Reaction Networks ⋮ How many cooks spoil the soup?

Cites Work

• Deterministic function computation with chemical reaction networks
• A simple population protocol for fast robust approximate majority
• The computational power of population protocols
• Computation in networks of passively mobile finite-state sensors
• Fast computation by population protocols with a leader
• Convergence Speed of Binary Interval Consensus
• Loosely-Stabilizing Leader Election in Population Protocol Model
• Leaderless Deterministic Chemical Reaction Networks
• Stably computable predicates are semilinear
• Stable leader election in population protocols requires linear time

This page was built for publication: Polylogarithmic-Time Leader Election in Population Protocols