Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People

The Taub Faculty of Computer Science Events and Talks

Theory Seminar: Lower Bound on the Step Complexity of Anonymous Binary Consensus
event speaker icon
Ohad Ben Baruch (Ben-Gurion University)
event date icon
Wednesday, 25.01.2017, 12:30
event location icon
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.