Abstract
Consensus problems occur in many contexts and have therefore been intensively studied in the past. 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. 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 value without necessarily being aware of that. This should work irrespective of the states in which the processes are starting. Coming up with a selfstabilizing rule is easy without adversarial involvement, but we allow some Tbounded adversary to manipulate any T processes at any time. In this situation, a perfect consensus is impossible to reach, so we only require that there is a time point t and value v so that at any point after t, all but up to O(T) processes agree on v, which we call an almost stable consensus. As we will demonstrate, there is a surprisingly simple rule for the standard message passing model that just needs O(log n loglog n) time for any sqrt{n}bounded adversary and just O(log n) time without adversarial involvement, with high probability, to reach an (almost) stable consensus from any initial state. A stable consensus is reached, with high probability, in the absence of adversarial involvement.
BibTeX  Entry
@InProceedings{doerr_et_al:DSP:2010:2429,
author = {Benjamin Doerr and Leslie Ann Goldberg and Lorenz Minder and Thomas Sauerwald and Christian Scheideler},
title = {Stabilizing Consensus with the Power of Two Choices},
booktitle = {Algorithmic Methods for Distributed Cooperative Systems},
year = {2010},
editor = {S{\'a}ndor Fekete and Stefan Fischer and Martin Riedmiller and Suri Subhash},
number = {09371},
series = {Dagstuhl Seminar Proceedings},
ISSN = {18624405},
publisher = {Schloss Dagstuhl  LeibnizZentrum fuer Informatik, Germany},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2010/2429},
annote = {Keywords: Distributed consensus}
}
Keywords: 

Distributed consensus 
Seminar: 

09371  Algorithmic Methods for Distributed Cooperative Systems 
Issue Date: 

2010 
Date of publication: 

22.04.2010 