Premium
Optimal communication in networks with randomly distributed byzantine faults
Author(s) -
Blough Douglas M.,
Pelc Andrzej
Publication year - 1993
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.3230230807
Subject(s) - asymptotically optimal algorithm , node (physics) , computer science , computer network , distributed computing , telecommunications network , byzantine fault tolerance , fault tolerance , algorithm , engineering , structural engineering
We consider the problem of efficient information exchange in a communication network whose nodes and/or links are subject to Byzantine faults that are randomly and independently distributed through the network. The goal is almost safe communication, i.e., getting to every fault‐free node information about every other fault‐free node, with probability converging to one as the number of nodes grows. We present nonadaptive almost‐safe communication schemes working for various networks in asymptotically optimal time and using an asymptotically optimal number of message bits.