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 hte 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 ocnsensus in O(nlog sup 2n) total work. Here, total work is defined as the total number of steps perfomred by all processors collectively. Thus, the amortized work per processor is O(log sup 2 n).
展开▼
