2026-08-16T03:56:37Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:2429 2024-03-06T11:08:59Z ddc:004 open_access

Stabilizing Consensus with the Power of Two Choices Doerr, Benjamin Goldberg, Leslie Ann Minder, Lorenz Sauerwald, Thomas Scheideler, Christian Distributed consensus 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Benjamin Doerr and Leslie Ann Goldberg and Lorenz Minder and Thomas Sauerwald and Christian Scheideler 2010 Is Part Of Dagstuhl Seminar Proceedings, Volume 9371, Algorithmic Methods for Distributed Cooperative Systems (2010) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/DagSemProc.09371.6 urn:nbn:de:0030-drops-24290 https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.09371.6 eng https://creativecommons.org/licenses/by/4.0/legalcode