How to prove impossibility under global fairness: on space complexity of self-stabilizing leader election on a population protocol model

DOI10.1007/s00224-011-9313-zzbMath1281.68049OpenAlexW2092232879MaRDI QIDQ692907

Shukai Cai, Koichi Wada, Taisuke Izumi

Publication date: 6 December 2012

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-011-9313-z

zbMATH Keywords

distributed algorithmself-stabilizationleader electionpopulation protocolglobal fairness

Mathematics Subject Classification ID

Distributed systems (68M14)

Related Items (16)

Population protocols with faulty interactions: the impact of a leader ⋮ On Space and Time Complexity of Loosely-Stabilizing Leader Election ⋮ Constant-Space Population Protocols for Uniform Bipartition ⋮ A combinatorial characterization of self-stabilizing population protocols ⋮ The Power of Global Knowledge on Self-stabilizing Population Protocols ⋮ Self-stabilizing systems in spite of high dynamics ⋮ On space complexity of self-stabilizing leader election in mediated population protocol ⋮ A Near Time-optimal Population Protocol for Self-stabilizing Leader Election on Rings with a Poly-logarithmic Number of States ⋮ Brief Announcement: Population Protocols Decide Double-exponential Thresholds ⋮ Fault-tolerant simulation of population protocols ⋮ Mediated Population Protocols: Leader Election and Applications ⋮ Constructing self-stabilizing oscillators in population protocols ⋮ Unnamed Item ⋮ Loosely-stabilizing leader election with polylogarithmic convergence time ⋮ Constructing Self-stabilizing Oscillators in Population Protocols ⋮ Space-efficient self-stabilizing counting population protocols on mobile sensor networks

Cites Work

• The computational power of population protocols
• Computation in networks of passively mobile finite-state sensors
• A Simple Population Protocol for Fast Robust Approximate Majority
• Self-stabilizing Counting in Mobile Sensor Networks with a Base Station
• Stably computable predicates are semilinear
• Unnamed Item

This page was built for publication: How to prove impossibility under global fairness: on space complexity of self-stabilizing leader election on a population protocol model