Wait-Free Consensus Using Asynchronous Hardware
Benny Chor, Amos Israeli, Ming Li · SIAM Journal on Computing · 1994
This paper studies the wait-free consensus problem in the asynchronous shared memory model. In this model, processors communicate by shared registers that allow atomic read and write operations (but do not support atomic test-and-set). It is known that the wait-free consensus problem cannot be solved by deterministic protocols. A randomized solution is presented. This protocol is simple, constructive, tolerates up to $n - 1$ processors crashes (where n is the number of processors), and its expected run-time is $O(n^2 )$.