Stabilizing consensus with the power of two choices
Doerr, Benjamin
Goldberg, Leslie Ann
Minder, Lorenz
Sauerwald, Thomas
Scheideler, Christian
ddc:040
In the standard consensus problem there are n processes with possibly di®erent 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 ¯nal 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(logmlog 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 p 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(logmlog log n + log n) under adversarial presence.
2011
info:eu-repo/semantics/conferenceObject
doc-type:conferenceObject
text
http://purl.org/coar/resource_type/c_5794
https://ris.uni-paderborn.de/record/645
Doerr B, Goldberg LA, Minder L, Sauerwald T, Scheideler C. Stabilizing consensus with the power of two choices. In: <i>Proceedings of the 23rd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)</i>. ; 2011:149-158. doi:<a href="https://doi.org/10.1145/1989493.1989516">10.1145/1989493.1989516</a>
info:eu-repo/semantics/altIdentifier/doi/10.1145/1989493.1989516
info:eu-repo/semantics/closedAccess