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-ZMaRDI QIDQ692907zbMATH OpenOpenAlexFDO

Authors Shukai Cai, Taisuke Izumi, Koichi Wada

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 algorithmleader electionself-stabilizationpopulation protocolglobal fairness

Mathematics Subject Classification ID

Distributed systems (68M14)

Recommendations

• Space complexity of self-stabilizing leader election in passively-mobile anonymous agents
• Time-Optimal Self-stabilizing Leader Election on Rings in Population Protocols
• Loosely-stabilizing leader election in population protocol model

Cites work

• scientific article; zbMATH DE number 5605125 (Why is no real title available?)
• A Simple Population Protocol for Fast Robust Approximate Majority
• Computation in networks of passively mobile finite-state sensors
• Self-stabilizing Counting in Mobile Sensor Networks with a Base Station
• Stably computable predicates are semilinear
• The computational power of population protocols

Cited in

(23)

• Constructing self-stabilizing oscillators in population protocols
• Fault-tolerant simulation of population protocols
• The Power of Global Knowledge on Self-stabilizing Population Protocols
• Constant-space population protocols for uniform bipartition
• Brief announcement: Space-optimal naming in population protocols
• On the power of oracle \(\varOmega ?\) for self-stabilizing leader election in population protocols
• A combinatorial characterization of self-stabilizing population protocols
• Loosely-stabilizing leader election with polylogarithmic convergence time
• Efficient assignment of identities in anonymous populations
• Mediated population protocols: leader election and applications
• scientific article; zbMATH DE number 7204593 (Why is no real title available?)
• Space-efficient self-stabilizing counting population protocols on mobile sensor networks
• 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
• Space complexity of self-stabilizing leader election in passively-mobile anonymous agents
• Deterministic self-stabilising leader election for programmable matter with constant memory
• On space complexity of self-stabilizing leader election in mediated population protocol
• Constructing Self-stabilizing Oscillators in Population Protocols
• On space and time complexity of loosely-stabilizing leader election
• Sublinear-time collision detection in population protocols with polynomially many states
• scientific article; zbMATH DE number 7561458 (Why is no real title available?)
• A Combinatorial Characterization of Self-stabilizing Population Protocols
• Self-stabilizing systems in spite of high dynamics

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q692907)