MAKING DISTRIBUTED SPANNING TREE ALGORITHMS FAULT-RESILIENT
				     (Extended Abstract)
	     Reuven Bar-Yehuda, Shay Kutten, Yaron Wolfstahl and Shmuel Zaks

ABSTRACT:
We study distributed algorithms for networks with undetectable fail-stop failures, assuming that all of
them had occurred before the execution started. (It was proved that distributed agreement cannot be reached when
a node may fail during execution.) Failures of this type are encountered, for example, during a recovery from a
crash in the network. We study the problems of leader election and spanning tree construction, that have been
characterized as fundamental for this environment. We point out that in presence of faults just duplicating messages
in an existing algorithm does not suffice to make it resilient; actually, this redundancy gives rise to synchronization
problems and also might increase the message complexity. In this paper we investigate the problem
of making existing spanning tree algorithms fault-resilient, and still overcome these difficulties. Several lower
bounds and optimal fault-resilient algorithms are presented for the first time. However, we believe that the main
contribution of the paper is twofold: First, in designing the algorithms we use tools that thus argued to be rather
general (for example, we extend the notion of token algorithms to multiple-token algorithms). In fact we are able
to use them on several different algorithms, for several different families of networks. Second, following the
amortized computational complexity, we introduce amortized message complexity as a tool for analyzing the message
complexity.