Tight bounds for asynchronous randomized consensus
Authors:
Open Access
- 1 October 2008
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 55 (5) , 1-26
Abstract
A distributed consensus algorithm allows n processes to reach a common decision value starting from individual inputs. Wait-free consensus, in which a process always terminates within a finite number of its own steps, is impossible in an asynchronous shared-memory system. However, consensus becomes solvable using randomization when a process only has to terminate with probability 1. Randomized consensus algorithms are typically evaluated by their total step complexity , which is the expected total number of steps taken by all processes. This article proves that the total step complexity of randomized consensus is Θ( n 2 ) in an asynchronous shared memory system using multi-writer multi-reader registers. This result is achieved by improving both the lower and the upper bounds for this problem. In addition to improving upon the best previously known result by a factor of log 2 n , the lower bound features a greatly streamlined proof. Both goals are achieved through restricting attention to a set of layered executions and using an isoperimetric inequality for analyzing their behavior. The matching algorithm decreases the expected total step complexity by a log n factor, by leveraging the multi-writing capability of the shared registers. Its correctness proof is facilitated by viewing each execution of the algorithm as a stochastic process and applying Kolmogorov's inequality.Keywords
Funding Information
- Israel Science Foundation (953/06)
This publication has 28 references indexed in Scilit:
- Efficient low-contention asynchronous consensus with the value-oblivious adversary schedulerDistributed Computing, 2005
- Randomized protocols for asynchronous consensusDistributed Computing, 2003
- The part-time parliamentACM Transactions on Computer Systems, 1998
- Lower bounds for distributed coin-flipping and randomized consensusJournal of the ACM, 1998
- Wait-free synchronizationACM Transactions on Programming Languages and Systems, 1991
- Implementing fault-tolerant services using the state machine approach: a tutorialACM Computing Surveys, 1990
- Fast randomized consensus using shared memoryJournal of Algorithms, 1990
- Impossibility of distributed consensus with one faulty processJournal of the ACM, 1985
- A lower bound for the time to assure interactive consistencyInformation Processing Letters, 1982
- An Introduction to Probability Theory and Its Applications. Vol. 1, Second Edition.Journal of the American Statistical Association, 1958