OPTIMAL ASYNCHRONOUS AGREEMENT AND LEADER ELECTION ALGORITHM FOR COMPLETE NETWORKS WITH BYZANTINE FAULTY LINKS

We consider agreement and leader election on asynchronous complete net works when the processors are reliable, but some of the channels are s ubject to failure. Fischer, Lynch, and Paterson have already shown tha t no deterministic algorithm can solve the agreement problem on asynch ronous networks if any processor fails during the execution of the alg orithm. Therefore, we consider only channel failures. The type of chan nel failure we consider in this paper is Byzantine failure, that is, c hannels fail by altering messages, sending false information, forging messages, losing messages at will, and so on. There are no restriction s on the behavior of a faulty channel. Therefore, a faulty channel may act as an adversary who forges messages on purpose to prevent the suc cessful completion of the algorithm. 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 g arbage to be sent. We present the first known agreement and leader ele ction algorithm for asynchronous complete networks in which the proces sors are reliable but some channels may be Byzantine faulty. The algor ithm can tolerate up to [n-2/2] faulty channels, where n is the number of processors in the network. We show that the bound on the number of faulty channels is optimal. When the processors terminate their corre sponding algorithms, all the processors in the network will have the s ame correct vector, where the vector contains the private values of al l the processors.