Self-stabilizing minimum spanning tree construction on message-passing networks.

摘要

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.