Name
Abstract | ||
|---|---|---|
In the standard consensus problem there are n processes 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 the stabilizing 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 called median rule that, with high probability, just needs O(log m log log n + log n) time and work per process to arrive at an almost stable consensus for any set of m legal values as long as an adversary can corrupt the states of at most √n processes at any time. Without adversarial involvement, just O(log n) 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 of n numbers in time O(log m log log n + log n) under adversarial presence. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1145/1989493.1989516 | Proceedings of the twenty-third annual ACM symposium on Parallelism in algorithms and architectures |
Keywords | DocType | Citations |
standard consensus problem,n number,stable consensus,log n,n process,m log log n,time o,m legal value,consensus problem,high probability,randomized algorithms,distributed consensus,self stabilization,distributed algorithm,randomized algorithm | Conference | 34 |
PageRank | References | Authors |
1.25 | 32 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Benjamin Doerr | 1 | 1504 | 127.25 |
| leslie ann goldberg | 2 | 1411 | 125.20 |
| Lorenz Minder | 3 | 92 | 5.53 |
| Thomas Sauerwald | 4 | 575 | 39.99 |
| Christian Scheideler | 5 | 1729 | 152.71 |