About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Conference paper
Tolerating linear number of faults in networks of bounded degree
Abstract
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.