How to prove impossibility under global fairness: on space complexity of self-stabilizing leader election on a population protocol model
From MaRDI portal
Publication:692907
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
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