TR#: | CS0591 |

Class: | CS |

Title: | Optimal Distributed t-Resilient Election in Complete Networks |

Authors: | A. Itai, S. Kutten, Y. Wolfstahl, and S. Zaks |

CS0591.pdf | |

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

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/1989/CS/CS0591), 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