@Article{BarKut88, author = "R. Bar-Yehuda and S. Kutten", title = "Fault Tolerant Distributed Majority Commitment", journal = "Journal of Algorithms", pages = "568--582", volume = "9", number = "4", month = dec, year = "1988", 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(n^2)$ and each message is $O(\log(MaxId))$ bits (where $n$ is the number of nodes and {\em 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 {\em MaxId} $= n^{O(1)}$).", }