The first self-stabilizing algorithm published by Dijkstra in 1973 assumed the existence of a central daemon, that activates one processor at time to change state as a function of its own state and the state of a neighbor. Subsequent research has reconsidered this algorithm without the assumption of a central daemon, and under different forms of communication, such as the model of link registers. In all of these investigations, one common feature is the atomicity of communication, whether by shared variables or read/write registers. This paper weakens the atomicity assumptions for the communication model, proposing versions of Dijkstra's algorithm that tolerate various weaker forms of atomicity, including cases of regular and safe registers. The paper also presents an implementation of Dijkstra's algorithm based on registers that have probabilistically correct behavior, which requires a notion of weak stabilization, where Markov chains are used to evaluate the probability to be in a safe configuration.
['Shlomi Dolev', 'Ted Herman']
Dijkstra's Self-Stabilizing Algorithm in Unsupportive Environments