Files in this item
Files  Description  Format 

application/pdf 8908604.pdf (4MB)  (no description provided) 
Description
Title:  FaultTolerant Distributed Algorithms for Agreement and Election 
Author(s):  AbuAmara, Hosame Hassan 
Doctoral Committee Chair(s):  Loui, Michael C. 
Department / Program:  Electrical Engineering 
Discipline:  Electrical Engineering 
Degree Granting Institution:  University of Illinois at UrbanaChampaign 
Degree:  Ph.D. 
Genre:  Dissertation 
Subject(s):  Engineering, Electronics and Electrical
Computer Science 
Abstract:  This thesis consists of three parts. In the first part, we characterize completely the sharedmemory requirements for achieving agreement in an asynchronous system of failstop 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 messagepassing systems. Furthermore, there is no agreement protocol that uses testandset operations if memory cells have only two values and two or more processes may die. In contrast, there is an agreement protocol with testandset 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 (r1)}$log$({n\over (r1)f}))$ messages in the worst case, runs in time $O({n\over (r1)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. 
Issue Date:  1988 
Type:  Text 
Description:  97 p. Thesis (Ph.D.)University of Illinois at UrbanaChampaign, 1988. 
URI:  http://hdl.handle.net/2142/69405 
Other Identifier(s):  (UMI)AAI8908604 
Date Available in IDEALS:  20141215 
Date Deposited:  1988 
This item appears in the following Collection(s)

Dissertations and Theses  Electrical and Computer Engineering
Dissertations and Theses in Electrical and Computer Engineering 
Graduate Dissertations and Theses at Illinois
Graduate Theses and Dissertations at Illinois