On Space and Time Complexity of Loosely-Stabilizing Leader Election

DOI10.1007/978-3-319-25258-2_21zbMath1471.68032OpenAlexW2293236883MaRDI QIDQ3460723

Taisuke Izumi

Publication date: 8 January 2016

Published in: Structural Information and Communication Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-25258-2_21

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Distributed systems (68M14)

Related Items (8)

Constant-Space Population Protocols for Uniform Bipartition ⋮ The Power of Global Knowledge on Self-stabilizing Population Protocols ⋮ A Near Time-optimal Population Protocol for Self-stabilizing Leader Election on Rings with a Poly-logarithmic Number of States ⋮ Constructing self-stabilizing oscillators in population protocols ⋮ Unnamed Item ⋮ Data collection in population protocols with non-uniformly random scheduler ⋮ Loosely-stabilizing leader election with polylogarithmic convergence time ⋮ Loosely-stabilizing maximal independent set algorithms with unreliable communications

Cites Work

• Loosely-stabilizing leader election in a population protocol model
• How to prove impossibility under global fairness: on space complexity of self-stabilizing leader election on a population protocol model
• Space-efficient self-stabilizing counting population protocols on mobile sensor networks
• Approximate counting: a detailed analysis
• The computational power of population protocols
• Computation in networks of passively mobile finite-state sensors
• Fast computation by population protocols with a leader
• A Randomized Algorithm for Finding Frequent Elements in Streams Using O(loglogN) Space
• Polylogarithmic-Time Leader Election in Population Protocols
• Self-stabilizing Counting in Mobile Sensor Networks with a Base Station
• On utilizing speed in networks of mobile agents

This page was built for publication: On Space and Time Complexity of Loosely-Stabilizing Leader Election