Theory Seminar: Lower Bound on the Step Complexity of Anonymous Binary Consensus

Speaker:
Ohad Ben Baruch (Ben-Gurion University)
Date:
Wednesday, 25.1.2017, 12:30
Place:
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.

Back to the index of events