A self-stabilizing algorithm for the shortest path problem assuming the distributed demon

✍ Scribed by Tetz C. Huang

• Publisher: Elsevier Science
• Year: 2005
• Tongue: English
• Weight: 1015 KB
• Volume: 50
• Category: Article
• ISSN: 0898-1221
• DOI: 10.1016/j.camwa.2005.05.002

✦ Synopsis

Shortest path finding has a variety of applications in transportation and communication. In this paper, we study a well-known self-stabilizing algorithm for the shortest path problem for the distributed systems. The prevlotm works on this topic had two assumptions that can be relaxed in this paper. First, in the previous works, the systems were assumed to be integral-weighted, whereas in this paper, the systems are real-weighted. Second, and more importantly, the previous works have shown that the algorithm is self-stabilizing under the more restricted central demon model, whereas in this paper, we give a rigorous proof showing that the algorithm is actually self-stabilizing under the more general distributed demon model. The work in this paper is of significance because in the existing literature on self-stabilizing systems, most of the papers regarding the distributed demon are for the ring networks only; there are very few papers that discuss the self-stabilizing algorithms for the general distributed systems assuming the distributed demon model.