  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 \emph{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 Ben-Or 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
\emph{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.
