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 O( n log(2) n) total work and O( log n) (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.( n) memory contention.