Technical Report CS0432

Title: Optimal Fault-Tolerant Distributed Spanning Tree Weak Construction in General Networks
Authors: Shay Kutten
Abstract: We study the basic problem of constructing a spanning tree distributively in an asynchronous general network, in presence of faults that occurred prior to the execution of the construction algorithm. Failures of this type are encountered, for example, during a recovery from a crash in the network. This problem is fundamental in computer communication networks, e.g: for routing, and as a subroutine for other distributed algorithms. Since we do not assume a global knowledge about the network, no fault-resilient algorithm can guarantee termination. Thus we investigate the border area between the possiple and the impossible. We present for the first time an optimal (in terms of the message complexity) algorithm which eventually constructs a spanning tree (but does not detect the termination) in spite of faults in general networks. Although our algorithm is faults-resilient, the order of the number of messages it uses is the same as that required by a non-resilient algorithm. For a network with m commuimication 1ines and n processors, k of which start the algorithm, the algorithm we present uses at most 0 (n log k +m) messages. Another main contribution of this paper is the method by which we have modified of an existing algorithm for a fault-free network.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 1986
To the main CS technical reports page

Computer science department, Technion