Tolerating linear number of faults in networks of bounded degree

In [7], Dwork et al. 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 substantial number of faults, it was shown in [7] 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 [7] 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 [7], 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.