# Noon lecture

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | 2018 | 2019 | 2020 | newer lectures)

On 25.3.2010 at 12:20 in S6, there is the following noon lecture:

# 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

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | 2018 | 2019 | 2020 | newer lectures)

Webmaster: kamweb.mff.cuni.cz Archive page