License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.09371.6
URN: urn:nbn:de:0030-drops-24290
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2010/2429/
Go to the corresponding Portal

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

Stabilizing Consensus with the Power of Two Choices

pdf-format:
09371.ScheidelerChristian.Paper.2429.pdf (0.3 MB)

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:DagSemProc.09371.6,
  author =	{Doerr, Benjamin and Goldberg, Leslie Ann and Minder, Lorenz and Sauerwald, Thomas and Scheideler, Christian},
  title =	{{Stabilizing Consensus with the Power of Two Choices}},
  booktitle =	{Algorithmic Methods for Distributed Cooperative Systems},
  pages =	{1--21},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{9371},
  editor =	{S\'{a}ndor Fekete and Stefan Fischer and Martin Riedmiller and Suri Subhash},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2010/2429},
  URN =		{urn:nbn:de:0030-drops-24290},
  doi =		{10.4230/DagSemProc.09371.6},
  annote =	{Keywords: Distributed consensus}
}

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

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI