Optimal time randomized consensus - Making resilient algorithms fast in practice

Michael Saks, Nir Shavit, Heather Woll

Research output: Chapter in Book/Report/Conference proceedingConference contribution

59 Scopus citations

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.

Original languageEnglish (US)
Title of host publicationProceedings of the 2nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1991
PublisherAssociation for Computing Machinery
Pages351-362
Number of pages12
ISBN (Print)0897913760
StatePublished - Mar 1 1991
Externally publishedYes
Event2nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1991 - San Francisco, United States
Duration: Jan 28 1991Jan 30 1991

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

Other

Other2nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1991
Country/TerritoryUnited States
CitySan Francisco
Period1/28/911/30/91

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)

Fingerprint

Dive into the research topics of 'Optimal time randomized consensus - Making resilient algorithms fast in practice'. Together they form a unique fingerprint.

Cite this