Fault-Tolerant Distributed Algorithms for Agreement and Election

This thesis consists of three parts. In the first part, we characterize 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.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Electrical Engineering

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2014

Author dc:creator

• Abu-Amara, Hosame Hassan

Contributors dc:contributor

• Loui, Michael C.

• Engineering, Electronics and Electrical
• Computer Science

Identifier

(UMI)AAI8908604

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/69405