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
Optimal time randomized consensus - Making resilient algorithms fast in practice
Abstract
In practice, the design of distributed systems is often geared towards optimizing the time complexity of algorithms in "normal" executions, i.e. ones in which at most a small number of failures occur, while at the same time building in safety provisions to protect against many failures. In this paper we present an optimally fast and highly resilient shared-memory randomized consensus algorithm that runs in only O(log n) expected time if √n or less failures occur, and takes at most O(n3/n-f) expected time for any f. Every previously known resilient algorithm required polynomial expected time even if no faults occurred. Using the novel consensus algorithm, we show a method for speedingup resilient algorithms: for any decision problem on n processors, given a highly resilient algorithm as a black box, it modularly generates an algorithm with the same strong properties, that runs in only O(log n) expected time in executions where no failures occur.