The Power of Global Knowledge on Self-stabilizing Population Protocols

DOI10.1007/978-3-030-54921-3_14MaRDI QIDQ5100963zbMATH OpenOpenAlexFDO

Authors Yuichi Sudo, Masahiro Shibata, Junya Nakamura, Yong-Hwan Kim, Toshimitsu Masuzawa

Publication date 1 September 2022

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

Full work available at URL https://arxiv.org/abs/2003.07491

Mathematics Subject Classification ID

Computer system organization (68Mxx) Communication complexity, information complexity (68Q11) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• How to prove impossibility under global fairness: on space complexity of self-stabilizing leader election on a population protocol model
• On the power of oracle \(\varOmega ?\) for self-stabilizing leader election in population protocols
• Space complexity of self-stabilizing leader election in passively-mobile anonymous agents
• A combinatorial characterization of self-stabilizing population protocols
• A Combinatorial Characterization of Self-stabilizing Population Protocols

Cites work

• Computation in networks of passively mobile finite-state sensors
• Determining majority in networks with local interactions and very small local memory
• Fast computation by population protocols with a leader
• How to prove impossibility under global fairness: on space complexity of self-stabilizing leader election on a population protocol model
• Logarithmic Expected-Time Leader Election in Population Protocol Model
• Loosely-stabilizing leader election in a population protocol model
• Loosely-stabilizing leader election on arbitrary graphs in population protocols without identifiers nor random numbers
• Loosely-stabilizing leader election with polylogarithmic convergence time
• On space and time complexity of loosely-stabilizing leader election
• Polylogarithmic-time leader election in population protocols
• Self-Stabilizing Leader Election
• Self-stabilizing systems in spite of distributed control
• Space-optimal proportion consensus with population protocols

Cited in

(1)

• Constructing Self-stabilizing Oscillators in Population Protocols

This page was built for publication: The Power of Global Knowledge on Self-stabilizing Population Protocols

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