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