Agreement, leader election and secure message transmission in networks with Byzantine faulty links and processors /
We consider agreement and leader election on asynchronous networks when the . processors are reliable, but some of the channels are subject to failure. Fischer, Lynch, and Paterson have already shown that no deterministic algorithm can solve the agreement problem on asynchronous networks if any pro...
| Main Author: | |
|---|---|
| Format: | Thesis Book |
| Language: | English |
| Published: |
[Place of publication not identified] :
[publisher not identified] ;
1995.
|
| Subjects: | |
| Online Access: | http://proxy.library.tamu.edu/login?url=http://proquest.umi.com/pqdweb?did=742145391&sid=1&Fmt=2&clientId=2945&RQT=309&VName=PQD |
| Summary: | We consider agreement and leader election on asynchronous networks when the . processors are reliable, but some of the channels are subject to failure. Fischer, Lynch, and Paterson have already shown that no deterministic algorithm can solve the agreement problem on asynchronous networks if any processor fails during the execution of the algorithm. Therefore, we consider only channel failures. The type of channel failure we consider in this dissertation is Byzantine failure, that is, channels fail by altering messages, sending false information, forging messages, losing messages at will, and so on. There are no restrictions on the behavior of a faulty channel. Therefore, a faulty channel may act as an adversary who forges messages on purpose to prevent the successful completion of the algorithms. Because we assume an asynchronous network, the channel delays are arbitrary. Thus, the faulty channels may not be detectable unless, for example, the faulty channels cause garbage to be sent. We present algorithms for three different type of networks namely, asynchronous complete networks, asynchronous general network with known sense of direction and asynchronous general network with unknown sense of direction. We also study the problem of perfectly secure communication in synchronous and asynchronous general networks where processors and communication lines may be Byzantine faulty. One of our algorithms is a significant improvement on previous algorithms in the number of messages and the amount of local computation. Hence, our algorithm is better suited for traditional and fiber-optic networks than previous algorithms while requiring the same amount of connectivity. All the other algorithms we present are completely new and simultaneously achieve the three goals of perfect secrecy, perfect resiliency, and worst case time that is linear in the diameter of the network. |
|---|---|
| Item Description: | Vita. "Major Subject: Electrical Engineering". |
| Physical Description: | ix, 110 leaves : illustrations ; 28 cm. Issued also on microfiche from University Microfilms Inc. |
| Bibliography: | Includes bibliographical references. |