Randomized wait-free concurrent objects (extended abstract)
Maurice P. Herlihy · 1991
A concurrent object is a data structure shared by concurrent processes, A w aii-free implementation of a concurrent object guarantees that every operation completes in a finite number of steps, regardless of how processes interleave.It is known, however, that if concurrent processes communicate only by applying read and write operations to a shared memory, then it is impossible to construct wait-free implementations of many simple and useful data objects.In this paper we show how to construct randomized wait-free implementations of long-lived concurrent objects, implementations that guarantee that every operation completes in a finite ezpected number of steps, even against a powerful adversary.