Randomized Consensus in Expected O(n log² n) Operations Per Processor
Randomized Consensus in Expected O(n log² n) Operations Per Processor
复制标题
每个处理器预期 O(n log² n) 操作的随机共识
DOI：
10.1137/s0097539792240881
复制
发表时间：
1996
期刊：
影响因子：
--
通讯作者：
Orli Waarts
中科院分区：
文献类型：
--
作者：
J. Aspnes;Orli Waarts
本文提出了一种新的随机算法，以在通过阅读和写入共享寄存器进行通信的异步处理器之间达成共识。以前最快的已知算法要求处理器在最坏情况下执行预期的$ O（n^2 \ log n）$读取操作。在我们的算法中，每个处理器最多执行预期的$ o（n \ log^2 n）$读取操作，该操作接近$ \ omega（n）$的琐事下限。所有先前已知的多项式时间共识算法都是围绕共享的coin协议构建的[J.算法，11（1990），pp。441--446]，其中每个处理器反复将随机$ \ pm pm 1 $投票添加到公共池中。因此，在所有这些协议中，单个处理器完成的读取和写入操作的数量的最糟糕的预期键在渐近上不比所有处理器一起完成的读写和写入操作的总数更好。我们通过允许加工者投票的重量增加来打破这一传统。这可以使对手更大的控制权，因为在确定要投放下一次投票的重量时，他可以从多达$ n $不同的权重（每个处理器）中进行选择。我们证明，使用Martingale参数，我们的共享胶条协议是正确的。
This 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(n^2 \log n)$ read and write operations in the worst case. In our algorithm, each processor executes at most an expected $O(n \log^2 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 [J. Algorithms, 11 (1990), pp. 441--446] in which each processor repeatedly adds random $\pm 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. We 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 weight of the next vote to be cast. We prove that our shared-coin protocol is nevertheless correct using martingale arguments.