Technical Report CS0409

Title: Fault Tolerant-Leader Election with Termination Detection, in General Undirected Networks (Extended Abstract)
Authors: R. Bar-Yehuda and S. Kutten
Abstract: The problem of leader election in an asynchronous network with possible faulty edges (and nodes) is studied, In our model, a faulty edge is an edge which does not transfer messages in both directions. The election is needed in such cases in order to reorganize the network after failures have occurred. The goal is a fault tolerant algotithm with detection of termination. The common methods for the heavily studied termination detection cannot be applied in unreliable networks. Actually, "When there is no additional knowledge", it is obvious that ho fault tolerant algorithm can guarantee termination detection. However in real networks it is reasonable to expect that some global information, such as "how many nodes nodes form a majority", is known. For this model we present an O(n^2+m) messages complexity algorithm and each message is O(log(MaxId)) bits (where n is number of nodes, m the number of edges and Maxld is the maximum identity). Before presenting the formal algorithm and proofs, we present an infermal description in which we construct our algorithm step by step. The algorithm guarantees termination in a component with a-majority of the nodes. This algorithm can be used in networks in which message transmission is not restricted to the FIFO discipline. Thus, the memory (or the time and messages) needed to simulate the FIFO discipline, is saved. The memory space needed in each node is only O(MaxNodesDegree + log(MaxId)) ,(which, within a constant is the best possible).
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