TOLERATING A LINEAR NUMBER OF FAULTS IN NETWORKS OF BOUNDED DEGREE

While all other fault tolerance paradigms require networks of high con nectivity to tolerate a substantial number of faults, it was shown in Dwork et al. that the new paradigm can be achieved even on bounded deg ree 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 op en in Dwork et al. is whether almost everywhere agreement can be achie ved on bounded degree networks in the presence of up to O(n) faulty no des (processors). In this work, we answer this question in the affirma tive. 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. (C) 1994 Academic Press, I nc.