Fault Tolerance in Networks of Bounded Degree
In 1983 Dolev [D] published the following damning result for distributed computing: "Byzantine agreement is achievable only if the number of faulty processors in the system is less than one-half of the connectivity of the system's network." Even in the absence of malicious failures connectivity t + 1 required to achieve agreement [H].
© 1986 Association for Computing Machinery
Dwork, C., Peleg, D., Pippenger, N., and Upfal, E. "Fault Tolerance in Networks of Bounded Degree", ACM Symp. on Theory of Computing, 18 (1986), 370-379. doi: 10.1145/12130.12169