Randomized consensus in expected O(n log2 n) operations per processor
Abstract
The paper presents a new randomized algorithm for achieving consensus among asynchronous processors that communicate by reading and writing shared registers. The fastest previously known algorithm requires a processor to perform an expected O(n2 log n) read and write operations in the worst case. In the algorithm, each processor executes at most an expected O(n log2 n) read and write operations, which is close to the trivial lower bound of Omega (n). All previously known polynomial-time consensus algorithms were structured around a shared coin protocol in which each processor repeatedly adds random +or-1 votes to a common pool. Consequently, in all of these protocols, the worst case expected bound on the number of read and write operations done by a single processor is asymptotically no better than the bound on the total number of read and write operations done by all of the processors together. The authors succeed in breaking this tradition by allowing the processors to cast votes of increasing weights. This grants the adversary greater control since he can choose from up to n different weights (one for each processor) when determining the w i ht of the next vote to be cast. They prove that the shared coin protocol is correct nevertheless using martingale arguments.