On the complexity of asynchronous agreement agains

Authors: Allison Lewko Mark Lewko

Publish Date: 2014/06/29

Volume: 28, Issue: 6, Pages: 377-389

PDF Link

Abstract

We introduce new techniques for proving lower bounds on the running time of randomized algorithms for asynchronous agreement against powerful adversaries In particular we define a strongly adaptive adversary that is computationally unbounded and has a limited ability to corrupt a dynamic subset of processors by erasing their memories We demonstrate that the randomized agreement algorithms designed by BenOr and Bracha to tolerate crash or Byzantine failures in the asynchronous setting extend to defeat a strongly adaptive adversary These algorithms have essentially perfect correctness and termination but at the expense of exponential running time In the case of the strongly adaptive adversary we show that this dismally slow running time is inherent we prove that any algorithm with essentially perfect correctness and termination against the strongly adaptive adversary must have exponential running time We additionally interpret this result as yielding an enhanced understanding of the tools needed to simultaneously achieving perfect correctness and termination as well as fast running time for randomized algorithms tolerating crash or Byzantine failures

Keywords: