SELF-STABILIZING MINIMUM SPANNING TREE CONSTRUCTION ON MESSAGE-PASSING NETWORK
Date
2001-11-14
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
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.
Description
Keywords
Computer Science