---
res:
bibo_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.@eng
bibo_authorlist:
- foaf_Person:
foaf_givenName: Benjamin
foaf_name: Doerr, Benjamin
foaf_surname: Doerr
- foaf_Person:
foaf_givenName: Leslie Ann
foaf_name: Goldberg, Leslie Ann
foaf_surname: Goldberg
- foaf_Person:
foaf_givenName: Lorenz
foaf_name: Minder, Lorenz
foaf_surname: Minder
- foaf_Person:
foaf_givenName: Thomas
foaf_name: Sauerwald, Thomas
foaf_surname: Sauerwald
- foaf_Person:
foaf_givenName: Christian
foaf_name: Scheideler, Christian
foaf_surname: Scheideler
foaf_workInfoHomepage: http://www.librecat.org/personId=20792
bibo_doi: 10.1145/1989493.1989516
dct_date: 2011^xs_gYear
dct_title: Stabilizing consensus with the power of two choices@
...