WAIT-FREE CONSENSUS USING ASYNCHRONOUS HARDWARE

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 supp ort atomic test-and-set). It is known that the wait-free consensus pro blem cannot be solved by deterministic protocols. A randomized solutio n is presented. This protocol is simple, constructive, tolerates up to n - 1 processors crashes (where n is the number of processors), and i ts expected run-time is O(n2).