Optimal communication in networks with randomly distributed byzantine faults
- 1 December 1993
- Vol. 23 (8) , 691-701
- https://doi.org/10.1002/net.3230230807
Abstract
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.Keywords
This publication has 15 references indexed in Scilit:
- Almost Safe Gossiping in Bounded Degree NetworksSIAM Journal on Discrete Mathematics, 1992
- Reliable communication in networks with Byzantine link failuresNetworks, 1992
- Efficient diagnosis of multiprocessor systems under probabilistic modelsIEEE Transactions on Computers, 1992
- A guided tour of chernoff boundsInformation Processing Letters, 1990
- Optimal and near-optimal broadcast in random graphsDiscrete Applied Mathematics, 1989
- Optimum broadcasting and personalized communication in hypercubesIEEE Transactions on Computers, 1989
- A survey of gossiping and broadcasting in communication networksNetworks, 1988
- Broadcasting with random faultsDiscrete Applied Mathematics, 1988
- On Gossiping with Faulty Telephone LinesSIAM Journal on Algebraic Discrete Methods, 1987
- Reaching Agreement in the Presence of FaultsJournal of the ACM, 1980