Abstract Fault Tolerant Distributed Majority Commitment 1

The problem of leader election in an asynchronous communication network with some faulty edges (and nodes) is studied. The election is needed in such cases in order to reorganize the network after failures have occurred. We present a fault-tolerant algorithm which guarantees commitment. The total number of messages is O(n 2)and each message is O(log(MaxId)) bits (where n is the number of nodes and MaxId is the maximum identity). This improves aprevious fault-tolerant algorithm. The 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(NodeDegree + log(MaxId)) (which is optimal when MaxId = n O(1)). 1 Apreliminary version of this paper was presented at the STACS-87 conference. 1