Polylogarithmic-Time Leader Election in Population Protocols

DOI10.1007/978-3-662-47666-6_38zbMath1434.68042arXiv1502.05745MaRDI 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

68W40: Analysis of algorithms

68M14: Distributed systems

68M12: Network protocols

Related Items

Unnamed Item, Leader Election Requires Logarithmic Time in Population Protocols, The Power of Global Knowledge on Self-stabilizing Population Protocols, Simple and Efficient Leader Election, Unnamed Item, Stable leader election in population protocols requires linear time, Democratic, existential, and consensus-based output conventions in stable computation by chemical reaction networks, Population protocols with faulty interactions: the impact of a leader, Minimizing message size in stochastic communication patterns: fast self-stabilizing protocols with 3 bits, How many cooks spoil the soup?, Simple and fast approximate counting and leader election in populations, ppsim: a software package for efficiently simulating and visualizing population protocols, Fault-tolerant simulation of population protocols, Uniform bipartition in the population protocol model with arbitrary graphs, A survey of size counting in population protocols, 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, On Space and Time Complexity of Loosely-Stabilizing Leader Election, Constant-Space Population Protocols for Uniform Bipartition

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