@inproceedings{645,
abstract = {{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.}},
author = {{Doerr, Benjamin and Goldberg, Leslie Ann and Minder, Lorenz and Sauerwald, Thomas and Scheideler, Christian}},
booktitle = {{Proceedings of the 23rd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)}},
pages = {{149--158}},
title = {{{Stabilizing consensus with the power of two choices}}},
doi = {{10.1145/1989493.1989516}},
year = {{2011}},
}