Technical Report CS0430

Title: Optimal Distributed t-Resilient Election in Complete Networks
Authors: S. Kutten, Y. Wolfstahl and S. Zaks
Abstract: We study the problem of electing a leader distributively 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 t crash in the network. For a network with n processors, k of which start the algorithm and at most t processors might be faulty, we present an algorithm that uses at most O(nlogk+kt) messages. We prove that this algorithmis optimal. We also present optimal results for the cases where neighbor's identities are known, and where edges may fail. It is interesting to see that the order of the message complexity of a t-resilient algorithm is not always higner than the complexity of a non-resilient algorithm. The t-resilent algorithm is a systematic modification of an existing algorithm for a fault-free network. In the complexity analysis we use a new technique that we believe will prove helpful in analyzing fault-tolerant algorithms.
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 1986
To the main CS technical reports page

Computer science department, Technion