Stabilizing consensus with the power of two choices
Stabilizing consensus with the power of two choices
复制标题
以两种选择的力量稳定共识
DOI：
10.1145/1989493.1989516
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
Doerr B
中科院分区：
文献类型：
--
作者：
Doerr B
在标准的一致性问题中，存在可能具有不同输入值的进程，目标是最终达到所有进程都致力于这些值中的一个的点。我们正在研究共识问题的一个微小变体，称为稳定共识问题[2]。在这个问题中，我们不要求每个进程在某个点上提交一个最终值，但最终它们会在不一定意识到这一点的情况下获得一个共同的、稳定的值。无论进程处于何种启动状态，这都应该起作用。我们的主要结果是一个简单的随机算法，称为中值规则，该算法高概率只需要O(logmlogn+logn)时间和每个进程的工作，就可以对任何一组非法值达成几乎稳定的共识，只要对手在任何时间都可以破坏至多√n个进程的状态。在没有对手参与的情况下，需要JUSTO(LOGN)时间和工作来达成稳定的共识，可能性很大。作为一个副产品，我们得到了一个简单的分布式算法，在对抗性存在的情况下，逼近时间O(logmlogn+logn)中n个数的中位数。
In the standard consensus problem there arenprocesses with possibly different input values and the goal is to eventually reach a point at which all processes commit to exactly one of these values. We are studying a slight variant of the consensus problem called thestabilizing consensus problem[2]. In this problem, we do not require that each process commits to a final value at some point, but that eventually they arrive at a common, stable value without necessarily being aware of that. This should work irrespective of the states in which the processes are starting. Our main result is a simple randomized algorithm calledmedian rulethat, with high probability, just needsO(logmlog logn+ logn) time and work per process to arrive at an almost stable consensus for any set ofmlegal values as long as an adversary can corrupt the states of at most √nprocesses at any time. Without adversarial involvement, justO(logn) time and work is needed for a stable consensus, with high probability. As a by-product, we obtain a simple distributed algorithm for approximating the median ofnnumbers in timeO(logmlog logn+ logn) under adversarial presence.
登录
查看更多内容
DOI：
--
发表时间：
1999
期刊：
40th Annual Symposium on Foundations of Computer Science (Cat. No.99CB37039)
影响因子：
--
作者：
U. Feige
通讯作者：
U. Feige
使用异步硬件的无等待共识
DOI：
--
发表时间：
1994
期刊：
SIAM journal on computing (Print)
影响因子：
--
作者：
B. Chor;A. Israeli;Ming Li
通讯作者：
Ming Li
分布式选择的严格界限
DOI：
--
发表时间：
2007
期刊：
ACM Symposium on Parallelism in Algorithms and Architectures
影响因子：
--
作者：
F. Kuhn;Thomas Locher;Roger Wattenhofer
通讯作者：
Roger Wattenhofer
尽管对手强大，但仍近似共享内存计数
DOI：
--
发表时间：
2009
期刊：
TALG
影响因子：
--
作者：
J. Aspnes;K. Censor
通讯作者：
K. Censor
在删除的球和垃圾箱上
DOI：
--
发表时间：
1998
期刊：
International Workshop Randomization and Approximation Techniques in Computer Science
影响因子：
--
作者：
R. Cole;A. Frieze;B. Maggs;M. Mitzenmacher;A. Richa;R. Sitaraman;E. Upfal
通讯作者：
E. Upfal