Fault Tolerant Distributed Majority Commitment1
Reuven Bar-Yehuda and Shay Kutten
Computer Science Department
Technion - IIT Haifa 32000, Israel
Abstract
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(n2) and each message is O(log(MaxId)) bits (where n is the
number of nodes and MaxId is the maximum identity). This improves a previous 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 = nO(1)).