Please use this identifier to cite or link to this item: http://hdl.handle.net/1880/46463
Title: SELF-STABILIZING MINIMUM SPANNING TREE CONSTRUCTION ON MESSAGE-PASSING NETWORK
Authors: Liang, Zhiying
Keywords: Computer Science
Issue Date: 14-Nov-2001
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.
URI: http://hdl.handle.net/1880/46463
Appears in Collections:Technical Reports

Files in This Item:
File Description SizeFormat 
2001-688-11.pdf274.56 kBAdobe PDFView/Open
2001-688-11.ps341.53 kBPostscriptView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.