Doerr, Benjamin ;
Goldberg, Leslie Ann ;
Minder, Lorenz ;
Sauerwald, Thomas ;
Scheideler, Christian
Stabilizing Consensus with the Power of Two Choices
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 