A self-stabilizing algorithm for the shortest path problem assuming read/write atomicity

摘要

Shortest path finding has a variety of applications in the areas of transportation and communication in distributed systems. In this paper, we design and prove the correctness of a self-stabilizing algorithm that solves the single-source shortest path problem for a distributed system. Unlike all previous works on this topic, the model of computation employed by the system in this paper assumes the separate read/write atomicity introduced by Dolev et al. instead of the commonly used composite read/write atomicity introduced by Dijkstra.