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

DOI10.1016/j.dam.2008.05.002zbMath1154.68091OpenAlexW2062581855MaRDI QIDQ1003766

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

shortest path algorithmself-stabilizing algorithmcenter-finding algorithmdistributed daemon model

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• A self-stabilizing algorithm for the shortest path problem assuming the distributed demon
• A self-stabilizing algorithm for constructing breadth-first trees
• Self-stabilization of dynamic systems assuming only read/write atomicity
• A self-stabilizing algorithm for the shortest path problem in a distributed system
• A self-stabilizing algorithm for the center-finding problem assuming read/write separate atomicity
• An efficient fault-containing self-stabilizing algorithm for the shortest path problem
• The alternator
• Fault-containing self-stabilizing distributed protocols
• A self-stabilizing algorithm for the shortest path problem assuming read/write atomicity
• Self-stabilizing systems in spite of distributed control
• A SELF-STABILIZING DISTRIBUTED ALGORITHM FOR ALL-PAIRS SHORTEST PATH PROBLEM
• Self-Stabilizing Algorithms for Finding Centers and Medians of Trees
• Token systems that self-stabilize