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.