Simple constant-time consensus protocols in realistic failure models
Benny Chor, Michael Merritt, David B. Shmoys · Journal of the ACM · 1989
Using simple protocols, it is shown how to achieve consensus in constant expected time, within a variety of fail-stop and omission failure models. Significantly, the strongest models considered are completely asynchronous. All of the results are based on distributively flipping a coin, which is usable by a significant majority of the processors. Finally, a nearly matching lower bound is also given for randomized protocols for consensus.