Stabilizing Consensus With the Power of Two Choices

Christian Scheideler

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. I will talk about a slight variant of the consensus problem called the stabilizing consensus problem. In this problem, I 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. I will present a surprisingly simple rule for the standard message passing model that just needs \tilde{O}(log n) time and work for each process for any adversary that can manipulate up to \sqrt{n} processes at any time, with high probability, to reach an (almost) stable consensus from any initial state.

This is joint work with Benjamin