Loosely-stabilizing leader election in a population protocol model

DOI10.1016/J.TCS.2012.01.007MaRDI QIDQ442276zbMATH OpenOpenAlexFDO

Authors Yuichi Sudo, Junya Nakamura, Yukiko Yamauchi, Fukuhito Ooshita, Hirotsugu Kakugawa, Toshimitsu Masuzawa

Publication date 10 August 2012

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2012.01.007

zbMATH Keywords

leader electionloose-stabilizationpopulation protocolself-stabilization

Mathematics Subject Classification ID

Distributed systems (68M14) Reliability, testing and fault tolerance of networks and computer systems (68M15) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Recommendations

• Loosely-stabilizing leader election in population protocol model
• Loosely-stabilizing leader election with polylogarithmic convergence time
• Loosely-stabilizing leader election on arbitrary graphs in population protocols without identifiers nor random numbers
• On space and time complexity of loosely-stabilizing leader election
• Time-Optimal Self-stabilizing Leader Election on Rings in Population Protocols

Cites work

• A simple population protocol for fast robust approximate majority
• Computation in networks of passively mobile finite-state sensors
• Fast Computation by Population Protocols with a Leader
• scientific article; zbMATH DE number 2036573 (Why is no real title available?)
• Probability and Computing
• Quasi-self-stabilization of a distributed system assuming read/write atomicity
• Self-stabilization
• Self-stabilizing systems in spite of distributed control
• Space complexity of self-stabilizing leader election in passively-mobile anonymous agents

Cited in

(21)

• Constructing self-stabilizing oscillators in population protocols
• Loosely-stabilizing maximal independent set algorithms with unreliable communications
• Loosely-stabilizing leader election with polylogarithmic convergence time
• scientific article; zbMATH DE number 1696668 (Why is no real title available?)
• Constant-space population protocols for uniform bipartition
• Loosely-stabilizing leader election in population protocol model
• On space and time complexity of loosely-stabilizing leader election
• Leader election requires logarithmic time in population protocols
• scientific article; zbMATH DE number 7561458 (Why is no real title available?)
• The Power of Global Knowledge on Self-stabilizing Population Protocols
• Logarithmic Expected-Time Leader Election in Population Protocol Model
• Loosely-stabilizing leader election on arbitrary graphs in population protocols without identifiers nor random numbers
• A Near Time-optimal Population Protocol for Self-stabilizing Leader Election on Rings with a Poly-logarithmic Number of States
• Loosely-Stabilizing Maximal Independent Set Algorithms with Unreliable Communications
• A loosely self-stabilizing protocol for randomized congestion control with logarithmic memory
• Logarithmic expected-time leader election in population protocol model
• Stabilizing leader election in partial synchronous systems with crash failures
• Dynamic size counting in the population protocol model
• Complete graph identification in population protocols
• Sublinear-time collision detection in population protocols with polynomially many states
• Space-efficient self-stabilizing counting population protocols on mobile sensor networks

This page was built for publication: Loosely-stabilizing leader election in a population protocol model

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