SELF-STABILIZING MINIMUM SPANNING TREE CONSTRUCTION ON MESSAGE-PASSING 
NETWORK

Liang, Zhiying

SELF-STABILIZING MINIMUM SPANNING TREE CONSTRUCTION ON MESSAGE-PASSING NETWORK

dc.contributor.author	Liang, Zhiying	eng
dc.date.accessioned	2008-05-20T23:24:28Z
dc.date.available	2008-05-20T23:24:28Z
dc.date.computerscience	2001-11-14	eng
dc.date.issued	2001-11-14	eng
dc.description.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.	eng
dc.description.notes	We are currently acquiring citations for the work deposited into this collection. We recognize the distribution rights of this item may have been assigned to another entity, other than the author(s) of the work.If you can provide the citation for this work or you think you own the distribution rights to this work please contact the Institutional Repository Administrator at digitize@ucalgary.ca	eng
dc.identifier.department	2001-688-11	eng
dc.identifier.doi	http://dx.doi.org/10.11575/PRISM/31360
dc.identifier.uri	http://hdl.handle.net/1880/46463
dc.language.iso	Eng	eng
dc.publisher.corporate	University of Calgary	eng
dc.publisher.faculty	Science	eng
dc.subject	Computer Science	eng
dc.title	SELF-STABILIZING MINIMUM SPANNING TREE CONSTRUCTION ON MESSAGE-PASSING NETWORK	eng
dc.type	unknown
thesis.degree.discipline	Computer Science	eng