Tolerating a linear number of faults in networks of bounded degree

Dwork et al. [SIAM J. Comput.17 (1988), 975-988] proposed a new paradigm for fault tolerant distributed computing termed almost everywhere agreement. While all other fault tolerance paradigms require networks of high connectivity to tolerate a substantial number of faults, it was shown in Dwork et al. that the new paradigm can be achieved even on bounded degree networks, as long as the number of faults is bounded by O(n/log n), where n is the size of the network. A major problem that was left open in Dwork et al. is whether almost everywhere agreement can be achieved on bounded degree networks in the presence of up to O(n) faulty nodes (processors). In this work, we answer this question in the affirmative. As in Dwork et al., our solution is based on a general technique for simulating on a bounded degree network an algorithm designed for the complete network. Each communication round of the complete network protocol is simulated by a logarithmic number of communication rounds, and with a polynomial number of messages. © 1994 Academic Press, Inc.