Short correctness proofs for two self-stabilizing algorithms under the distributed daemon model

DOI10.1016/J.DAM.2008.05.002MaRDI QIDQ1003766zbMATH OpenOpenAlexFDO

Authors Ji-Cherng Lin, Ming-Yi Chiu

Publication date 4 March 2009

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2008.05.002

zbMATH Keywords

center-finding algorithmdistributed daemon modelself-stabilizing algorithmshortest path algorithm

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85) Nonnumerical algorithms (68W05)

Recommendations

• A self-stabilizing algorithm for the shortest path problem in a distributed system
• Daemon Conversions in Distributed Self-stabilizing Algorithms
• A self-stabilizing algorithm for the shortest path problem assuming the distributed demon
• scientific article; zbMATH DE number 2036570
• A \(4n\)-move self-stabilizing algorithm for the minimal dominating set problem using an unfair distributed daemon

Cites work

• A self-stabilizing algorithm for constructing breadth-first trees
• A self-stabilizing algorithm for the center-finding problem assuming read/write separate atomicity
• A self-stabilizing algorithm for the shortest path problem assuming read/write atomicity
• A self-stabilizing algorithm for the shortest path problem assuming the distributed demon
• A self-stabilizing algorithm for the shortest path problem in a distributed system
• A SELF-STABILIZING DISTRIBUTED ALGORITHM FOR ALL-PAIRS SHORTEST PATH PROBLEM
• An efficient fault-containing self-stabilizing algorithm for the shortest path problem
• Fault-containing self-stabilizing distributed protocols
• scientific article; zbMATH DE number 1919504 (Why is no real title available?)
• scientific article; zbMATH DE number 194437 (Why is no real title available?)
• Self-stabilization of dynamic systems assuming only read/write atomicity
• Self-Stabilizing Algorithms for Finding Centers and Medians of Trees
• Self-stabilizing systems in spite of distributed control
• The alternator
• Token systems that self-stabilize

Cited in

(3)

• A self-stabilizing algorithm for the shortest path problem in a distributed system
• Daemon Conversions in Distributed Self-stabilizing Algorithms
• A self-stabilizing algorithm for the shortest path problem assuming the distributed demon

This page was built for publication: Short correctness proofs for two self-stabilizing algorithms under the distributed daemon model

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