Liang, Zhiying2008-05-202008-05-202001-11-14http://hdl.handle.net/1880/46463Self-stabilization is an abstraction of fault tolerance for transient faults. It guarantees that the system will eventually reach a legitimate configuration when started from an arbitrary initial configuration. This thesis presents two minimum spanning tree algorithms designed directly for deterministic, message-passing networks. The first converts an arbitrary spanning tree to a minimum one; the second is a fully self-stabilizing construction. The algorithms assume distinct identifiers and reliable fifo message passing, but do not rely on a root or synchrony. Also, processors have a safe time-out mechanism (the minimum assumption necessary for a solution to exist). Both algorithms apply to networks that can change dynamically.EngComputer Scienceunknown2001-688-1110.11575/PRISM/31360