Efficient asynchronous consensus with the value-oblivious adversary scheduler

We consider the power given to adversary scheduler of an asynchronous system and define the value-oblivious scheduler. At each step this scheduler determines the next processor to operate based on the full history of the dynamics of the execution; the scheduler is oblivious to the intermediate values the processors manipulate. We argue that the value-oblivious scheduler captures the possible sources of asynchrony in real systems. Assuming the value oblivious adversary, we study the asynchronous consensus problem in the shared-memory setting with atomic reads and writes. We present a probabilistic algorithm that obtains consensus in O(n log² n) total work. Here, total work is defined as the total number of steps performed by all processors collectively. Thus, the amortized work per processor is O(log²n).