Efficient asynchronous consensus with the weak adversary scheduler
Yonatan Aumann · 1997
Abstract We consider the problem of asynchronous consensus with a weak dynamic adversary scheduler. We provide the first algorithm to obtain ~O(n) total work in the weak adversary model using only single-writer registers. For the multi-writer setting we give an O(log n) workper-processor algorithm, improving upon the previous O(log2 n) bound. The adversary model considered is the content oblivious adversary model, which assumes that the adversary does not know the content of a register until it is read by some processor [13].