Asynchronous failure location and agreement algorithms for fiber-optic and for traditional networks with Byzantine links
Marwan Hassan Abu-Amara · OakTrust (Texas A&M University Libraries) · 1995
In the first part of the dissertation, we consider the agreement problem 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 algorithm can solve the agreement problem on asynchronous networks if any process 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 algorithm. Because we assume an asynchronous network, the channel delays are arbitrary. Thus, the faulty channels may not be detectable unless the faulty channels cause garbage to be sent. We present the first known agreement and leader election algorithms for asynchronous networks in which the processors are reliable but some channels may be Byzantine faulty. The types of networks that we consider are complete networks, general networks with known sense of direction, and general networks with unknown sense of direction. When the processors terminate their corresponding algorithm, all the processors in the network will have the same correct vector, where the vector contains values that the processors wanted to broadcast. Our algorithms for the complete networks and the general networks with known sense of direction tolerate up to t Byzantine faulty channels provided that the connectivity is at least 2t + 1. The bound on the connectivity of the network is optimal. Moreover, we present two algorithms for asynchronous general networks with unknown sense of direction that require the connectivity to be at least 3t + 1. The first algorithm assumes that the processors know the total number n of processors in the network. The second algorithm assumes that n is unknown. In the second part of the dissertation, we present an algorithm that locates possible stuck-at faults in the switching subsystems of the nodes of general asynchronous fiber-optic networks and provides the nodes of such a network with reliable paths for delivering messages sent between any two nodes. The algorithm has an O($n\sp2E$) message complexity, where n and E are the total number of nodes and the total number of links in the network, respectively.