Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, April 18, 2019, 12:15 pm
Duration: 45 minutes
Location: OAT S15/S16/S17
Speaker: Seyedrouzbeh Hasheminezhad
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, stable value without necessarily being aware of that. This should work irrespective of the states in which the processes are starting. The main result is a simple randomized algorithm called median rule that, with high probability, just needs O(log m log log n + log n) time and work per process to arrive at an almost stable consensus for any set of m legal values as long as an adversary can corrupt the states of at most n^0.5 processes at any time. Without adversarial involvement, just O(log n) time and work are needed for a stable consensus, with high probability.
Automatic MiSe System Software Version 1.4803M | admin login