Fault-Tolerant Distributed Algorithms for Agreement and Election

摘要

This thesis consists of three parts. The first part characterizes completely the shared-memory requirements for achieving agreement in an asynchronous system of fail-stop processes that die undetectably. There is no agreement protocol that uses only read and write operations, even if at most one process dies. This result implies the impossibility of Byzantine agreement in asynchronous message-passing systems. Furthermore, there is no agreement protocol that uses test-and-set operations if memory cells have only two values and two or more processes may die. In contrast, there is an agreement protocol with test-and-set operations if either memory cells have at least three values or at most one process dies. Part 2 considers the election problem on asynchronous complete networks when the processors are reliable but some of the channels may be intermittently faulty. To be consistent with the standard model of distributed algorithms in which channel delays can be arbitrary but finite, it is assumed that channel failures are undetectable. Given is an algorithm that correctly solves the problem when the channels fail before or during the execution of the algorithm. The third part presents the most efficient algorithm known of for election in synchronous square meshes. The algorithm uses 229/18n messages, runs in time units, and requires O(log(t)) bits per message. Also, we prove that any comparison algorithm on meshes requires at least 57/32n messages.