Please use this identifier to cite or link to this item:
|Title:||SELF-STABILIZING MINIMUM SPANNING TREE CONSTRUCTION ON MESSAGE-PASSING NETWORK|
|Abstract:||Self-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.|
|Appears in Collections:||Technical Reports|
Files in This Item:
|2001-688-11.pdf||274.56 kB||Adobe PDF||View/Open|
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.