We consider asynchronous shared memory distributed systems, and investigate coordination problems in this model. We provide a waitfree randomized consensus protocol that requires an expected O(n2 log n) atomic operations.
This research was partially supported by the U.S.-Israel bi-national science foundation grant 88-00282.