A Stabilizing Rendition of MST Construction.
T Herman:
Postscript Document and
DVI file.
Abstract
A self-stabilizing construction of the minimum-spanning forest of
distributed network is described. The algorithm demonstrates that
techniques of graph reduction and iteration can be
employed in the context of stabilizing distributed programs.
The program development follows the principle of layering in
the construction of self-stabilizing algorithms,
where each layer corresponds to one level of iteration.
The result is a relatively terminating program that can
either be executed asynchronously or by using a stabilizing synchronizer.