Technical Report CS0591

Title: Optimal Distributed t-Resilient Election in Complete Networks
Authors: A. Itai, S. Kutten, Y. Wolfstahl, and S. Zaks
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 of which might be faulty, we present an algorithm that uses at most O(n logk +n+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.

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 1989
To the main CS technical reports page

Computer science department, Technion