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.
************************************