Self-Stabilization by Local Checking and Global Reset
We describe a method for transforming asynchronous network
protocols into protocols that can sustain any transient fault, i.e.,
become self-stabilizing.
We combine the known notion of local checking with a new notion
of {\em internal reset}, and prove that
given any self-stabilizing internal reset protocol, any locally-checkable
protocol can be made self-stabilizing.
Our proof is constructive in
the sense that we provide explicit code. The method applies to many
practical network problems, including spanning tree construction,
topology update, and virtual circuit setup.
Click here
for proceedings version.