Fault-Tolerant Distributed Algorithms for Agreement and Election
Abu-Amara, Hosame Hassan
This item is only available for download by members of the University of Illinois community. Students, faculty, and staff at the U of I may log in with your NetID and password to view the item. If you are trying to access an Illinois-restricted dissertation or thesis, you can request a copy through your library's Inter-Library Loan office or purchase a copy directly from ProQuest.
Permalink
https://hdl.handle.net/2142/69405
Description
Title
Fault-Tolerant Distributed Algorithms for Agreement and Election
Author(s)
Abu-Amara, Hosame Hassan
Issue Date
1988
Doctoral Committee Chair(s)
Loui, Michael C.
Department of Study
Electrical Engineering
Discipline
Electrical Engineering
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
Ph.D.
Degree Level
Dissertation
Keyword(s)
Engineering, Electronics and Electrical
Computer Science
Abstract
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.
In the second part, we consider 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, we assume that channel failures are undetectable. We give an algorithm that correctly solves the problem when the channels fail before or during the execution of the algorithm. Let n be the number of processors in the network, f be the maximum number of faulty channels, and r be a design parameter. The algorithm uses no more than $O(nrf+{nr\over (r-1)}$log$({n\over (r-1)f}))$ messages in the worst case, runs in time $O({n\over (r-1)f})$, and uses at most $O$(log$\vert T\vert$) bits per message, where $\vert T\vert$ is the cardinality of the set of processor identifiers. If $r$ is chosen to minimize the number of messages, our algorithm uses no more than $O(nf+n$log $n)$ messages.
In the third part, we present the most efficient algorithm that we know of for election in synchronous square meshes. The algorithm uses ${229\over 18}n$ messages, runs in time $\Theta$($\sqrt{n}$) time units, and requires $O$(log$\vert T\vert$) bits per message. Also, we prove that any comparison algorithm on meshes requires at least ${57\over 32}n$ messages.
Use this login method if you
don't
have an
@illinois.edu
email address.
(Oops, I do have one)
IDEALS migrated to a new platform on June 23, 2022. If you created
your account prior to this date, you will have to reset your password
using the forgot-password link below.
