Optimal Fault-Tolerant Distributed Construction of A Spanning Forest
					Shay Kutten

ABSTRACT
We study the basic problem of constructing a spanning tree distributively in asynchronous
general network, in the presence of fault 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. In the case the network has been partitioned we construct a spanning forest. This problem is fundamental in computer communication networks, for example for routing, and as a subroutine for other distributed algorithms. Since we do not assume that a node in the network has any global knowledge about the network, no fault-resilient algorithm can guarantee termination detection. We present for the first time an optimal (in the order of massege complexity) fault-resilient forest constructing algorithm for general networks. The algorithm eventually constructs a spanning tree in every component of the network that remained connected in which at least one node initiated the algorithm. Although our algorithm is fault-resilient, the order of the number of messages it uses is the same as that required by a nonresilient algorithm. For a network with m communication lines and n processors, k of which initiate the algorithm spontaneously, the algorithm we present uses at most O(nlogk+m) messages. Another major contribution of this paper is the approach we took in order to modify an existing tree construction for fault-tree networks, to make it fault-resilient.