License
when quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-24290
URL: http://drops.dagstuhl.de/opus/volltexte/2010/2429/

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

Stabilizing Consensus with the Power of Two Choices

pdf-format:
Dokument 1.pdf (261 KB)


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 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

@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 =	{1862-4405},
  publisher =	{Schloss Dagstuhl - Leibniz-Zentrum 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


DROPS-Home | Fulltext Search | Imprint Published by LZI