TY - GEN

T1 - Optimal time randomized consensus - Making resilient algorithms fast in practice

AU - Saks, Michael

AU - Shavit, Nir

AU - Woll, Heather

N1 - Publisher Copyright:
© 1991 Association for Computing Machinery. All rights reserved.

PY - 1991/3/1

Y1 - 1991/3/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=35448990126&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=35448990126&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:35448990126

SN - 0897913760

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 351

EP - 362

BT - Proceedings of the 2nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1991

PB - Association for Computing Machinery

T2 - 2nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1991

Y2 - 28 January 1991 through 30 January 1991

ER -