Randomized self-stabilizing and space optimal leader election under arbitrary scheduler on rings

DOI10.1007/S00446-007-0034-0MaRDI QIDQ1954232zbMATH OpenOpenAlexFDO

Authors J. Beauquier, Maria Gradinariu, Colette Johnen

Publication date 20 June 2013

Published in Distributed Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00446-007-0034-0

zbMATH Keywords

leader electionself-stabilizationschedulerprotocol compositionrandomized protocol

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Reliability, testing and fault tolerance of networks and computer systems (68M15) Distributed systems (68M14)

Recommendations

• Self-stabilizing leader election in optimal space under an arbitrary scheduler
• scientific article; zbMATH DE number 2006655
• Deterministic, constant space, self-stabilizing leader election on uniform rings
• Time-Optimal Self-stabilizing Leader Election on Rings in Population Protocols
• Compact deterministic self-stabilizing leader election on a ring: the exponential advantage of being talkative
• An O(n)-time self-stabilizing leader election algorithm
• On space and time complexity of loosely-stabilizing leader election
• scientific article; zbMATH DE number 177572
• Improved bounds for electing a leader in a synchronous ring

Cites work

• scientific article; zbMATH DE number 4060392 (Why is no real title available?)
• scientific article; zbMATH DE number 2036567 (Why is no real title available?)
• scientific article; zbMATH DE number 1863300 (Why is no real title available?)
• scientific article; zbMATH DE number 794262 (Why is no real title available?)
• Coupling and self-stabilization
• Fault-Tolerant and Self-stabilizing Mobile Robots Gathering
• Formal verification of timed properties of randomized distributed algorithms
• Memory requirements for silent stabilization
• Memory space requirements for self-stabilizing leader election protocols
• Memory-efficient and self-stabilizing network RESET (extended abstract)
• Optimal Randomized Self-stabilizing Mutual Exclusion on Synchronous Rings
• Randomized self-stabilizing and space optimal leader election under arbitrary scheduler on rings
• Reactive, generative, and stratified models of probabilistic processes
• Self-Stabilizing Symmetry Breaking in Constant Space
• Self-stabilization of dynamic systems assuming only read/write atomicity
• Self-stabilizing token circulation on asynchronous uniform unidirectional rings
• Stabilization-preserving atomicity refinement
• Token-based self-stabilizing uniform algorithms
• Verification of multiprocess probabilistic protocols
• When graph theory helps self-stabilization

Cited in

(12)

• Randomized self-stabilizing and space optimal leader election under arbitrary scheduler on rings
• Deterministic, constant space, self-stabilizing leader election on uniform rings
• On probabilistic snap-stabilization
• Constant-Space Localized Byzantine Consensus
• Randomized dining philosophers without fairness assumption
• Randomized self-stabilizing leader election in preference-based anonymous trees
• Compact deterministic self-stabilizing leader election on a ring: the exponential advantage of being talkative
• scientific article; zbMATH DE number 2006655 (Why is no real title available?)
• Weak vs. self vs. probabilistic stabilization
• The expressive power of snap-stabilization
• The Bit Complexity of Randomized Leader Election on a Ring
• Optimal Randomized Self-stabilizing Mutual Exclusion on Synchronous Rings

This page was built for publication: Randomized self-stabilizing and space optimal leader election under arbitrary scheduler on rings

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