Efficient low-contention asynchronous consensus with the value-oblivious adversary scheduler

We consider asynchronous consensus in the shared-memory setting. We present the first efficient low-contention consensus algorithm for the weak-adversary-scheduler model. The algorithm achieves consensus in total work and (hot-spot) contention, both expected and with high probability. The algorithm assumes the value-oblivious scheduler, which is defined in the paper. Previous efficient consensus algorithms for weak adversaries suffer from memory contention.Yonatan Aumann: This work was partially completed while theauthor was at Harvard University, supported in part by ONRcontract ONR-N00014-91-J-1981.Michael A. Bender: This work was supported inpart by HRL Laboratories, Sandia National Laboratories, and NSF GrantsACI-032497, CCR-0208670, and EIA-0112849. This work was partiallycompleted while the author was at Harvard University, supported inpart by NSF grants CCR-9700365, CCR-9504436, and CCR-9313775.An early version of this paper was presented in the 23rd International Colloquium on Automata, Languages, and Programming (ICALP 96) 8].