Wait-free consensus with infinite arrivals
Wait-free consensus with infinite arrivals
复制标题
共识无等待，无限到来
DOI：
--
复制
发表时间：
2002
期刊：
影响因子：
--
通讯作者：
Jatin Shah
中科院分区：
文献类型：
--
作者：
J. Aspnes;Gauri Shah;Jatin Shah
给出了一个随机化算法，解决了共享内存模型的无限多个进程的无等待一致性问题。该算法基于弱共享硬币算法，该算法使用加权投票来实现具有至少恒定概率的多数结果，即使允许强大的对手破坏无限多的选票，也无法伪装。进程i执行的操作数是i的多项式函数。另外的算法给出了更有效地解决模型的共识与未知的上限B的并发性或未知的上限n的活动进程的数量;在这些限制下，它也表明，即使有无限多个匿名进程的问题可以解决前缀的每个实例的共享硬币的命名算法，打破对称性与高概率。对于这些算法中的许多算法，证明了匹配下界，表明它们的每进程工作作为i，B或n的函数接近最优。n个活动进程的情况下，给出了一个算法的匿名，自适应的共识，只需要O（n log 2 n）的每进程的工作，这是一个常数因子内的最好的以前已知的非自适应算法的一个强大的对手。最后，它表明，基于共识的标准通用结构继续与无限多的过程，只有轻微的修改。这表明，在无限分布系统中，就像在有限系统中一样，在随机性的情况下，一切都是可能的。
A randomized algorithm is given that solves the wait-free consensus problem for a shared-memory model with infinitely many processes. The algorithm is based on a weak shared coin algorithm that uses weighted voting to achieve a majority outcome with at least constant probability that cannot be disguised even if a strong adversary is allowed to destroy infinitely many votes. The number of operations performed by process i is a polynomial function of i. Additional algorithms are given for solving consensus more efficiently in models with an unknown upper bound b on concurrency or an unknown upper bound n on the number of active processes; under either of these restrictions, it is also shown that the problem can be solved even with infinitely many anonymous processes by prefixing each instance of the shared coin with a naming algorithm that breaks symmetry with high probability. For many of these algorithms, matching lower bounds are proved that show that their per-process work is nearly optimal as a function of i, b, or n. The case of n active processes gives an algorithm for anonymous, adaptive consensus that requires only O(n log2 n) per-process work, which is within a constant factor of the best previously known non-adaptive algorithm for a strong adversary. Finally, it is shown that standard universal constructions based on consensus continue to work with infinitely many processes with only slight modifications. This shows that in infinite distributed systems, as in finite ones, with randomness all things are possible.