Theory Seminar: Lower Bound on the Step Complexity of Anonymous Binary Consensus
- Ohad Ben Baruch (Ben-Gurion University)
- Wednesday, 25.1.2017, 12:30
- Taub 201
Obstruction-free consensus, ensuring that a process running solo will eventually terminate, is at the core of practical ways to solve consensus, e.g., by using randomization or failure detectors. An obstruction-free consensus algorithm may not terminate in many executions, but it must terminate whenever a process runs solo. Such an algorithm can be evaluated by its solo step complexity, which bounds the worst case number of steps taken by a process running alone, from any configuration, until it decides.
We will present a lower bound of $\Omega(\log n)$ on the solo step complexity of obstruction-free binary anonymous consensus. The proof constructs a sequence of executions in which more and more distinct variables are about to be written to, and then uses the backtracking covering technique to obtain a single execution in which many variables are accessed.