OPTIMAL DISTRIBUTED t-RESILIENT ELECTION  IN COMPLETE NETWORKS1


Alon Itai, Shay Kutten2, Yaron Wolfstahl and Shmuel Zaks2

Department of Computer ScienceTechnion, Haifa, Israel



	ABSTRACT 


We study the problem of distributed leader election in an asynchronous complete network, in presence of faults that 
occurred prior to the execution of the election algorithm. Failures of this type are encountered, for example, during 
a recovery from a crash in the network. For a network with n processors, k of which start the algorithm and at most 
t processors may be faulty, we present an algorithm that uses at most O(n log k + k t) messages. We prove that this 
algorithm is optimal. We also present an optimal algorithm for the case where the identities of the neighbors are 
known. It is interesting to note that the order of the message complexity of a t-resilient algorithm is not always 
higher than that of a non-resilient one. The t-resilient algorithm is a systematic modification of an existing 
algorithm for a fault-free network.

Index Terms: complete networks, distributed algorithms, election, fault-tolerance, message complexity.

************************************