Open Collections

Lower Bound on the Step Complexity of Anonymous Binary Consensus

Banff International Research Station for Mathematical Innovation and Discovery

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.

Mathematics; Computer science; Theoretical computer science

video/mp4

Author affiliation: Ben Guruion University of the Negev

2017-06-22

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/62087

Unreviewed

http://creativecommons.org/licenses/by-nc-nd/4.0/