When quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-24290
Go to the corresponding Portal

Doerr, Benjamin ; Goldberg, Leslie Ann ; Minder, Lorenz ; Sauerwald, Thomas ; Scheideler, Christian

Stabilizing Consensus with the Power of Two Choices

Document 1.pdf (261 KB)


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 self-stabilizing rule is easy without adversarial involvement, but we allow some T-bounded 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

  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 =	{1862-4405},
  publisher =	{Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany},
  address =	{Dagstuhl, Germany},
  URL =		{},
  annote =	{Keywords: Distributed consensus}

Keywords: Distributed consensus
Seminar: 09371 - Algorithmic Methods for Distributed Cooperative Systems
Issue Date: 2010
Date of publication: 22.04.2010

DROPS-Home | Fulltext Search | Imprint Published by LZI