Premium
Reliable communication in networks with Byzantine link failures
Author(s) -
Pelc Andrzej
Publication year - 1992
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230220503
Subject(s) - link (geometry) , computer science , hypercube , computer network , protocol (science) , telecommunications network , construct (python library) , class (philosophy) , distributed computing , theoretical computer science , medicine , alternative medicine , pathology , artificial intelligence , parallel computing
We consider the problem of communication between nodes of a network whose links are subject to arbitrary failures: A failed link may not only stop transmitting messages but may corrupt them in any possible way. We characterize networks allowing communication in spite of at most t failures. Also, for every fixed link failure probability p ≤ .29, we construct a class of networks for which the probability of successful communication converges to 1 as the number of nodes grows. It is shown that the number of links in these networks is asymptotically smallest possible to assure reliable communication. Moreover, in these networks, communication can be completed in just two information exchange rounds. Finally, we give a protocol assuring reliable communication in the hypercube if link failure probability is p ≤ .02 and show that no such protocol exists if p ≥ .15.