| TR#: | CS0430 |
| Class: | CS |
| Title: | Optimal Distributed t-Resilient Election in Complete Networks |
| Authors: | S. Kutten, Y. Wolfstahl and S. Zaks |
| CS0430.pdf | |
| 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. |
| Copyright | The 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 (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/1986/CS/CS0430), 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