Dijkstra's Self-Stabilizing Algorithm in Unsupportive Environments.
S Dolev, T Herman:
Postscript Document and
DVI file.
Abstract
The first self-stabilizing algorithm [Dij73]
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 [Dij73]
that tolerate various weaker forms of atomicity.
First, a solution for the case of regular registers
is presented. Then the case of safe registers is considered,
with both negative and positive results presented.
The paper also presents an implementation of [Dij73]
based on registers that have probabilistically correct
behavior, which requires a notion of weak stabilization.