James Aspnes and Maurice Herlihy. Wait-free data structures in the asynchronous PRAM model. Second Annual ACM Symposium on Parallel Algorithms and Architectures, July 1990, pp. 340–349.
In the asynchronous PRAM model, processes communicate by atomically reading and writing shared memory locations. This paper investigates the extent to which asynchronous PRAM permits long-lived, highly concurrent data structures. An implementation of a concurrent object is wait-free if every operation will complete in a finite number of steps, and it is k-bounded wait-free, for some k > 0, if every operation will complete within k steps. In the first part of this paper, we show that there are objects with wait-free implementations but no k-bounded wait-free implementations for any k, and that there is an infinite hierarchy of objects with implementations that are k-bounded wait-free but not K-bounded wait-free for some K > k. In the second part of the paper, we give an algebraic characterization of a large class of objects that do have wait-free implementations in asynchronous PRAM, as well as a general algorithm for implementing them. Our tools include simple iterative algorithms for wait-free approximate agreement and atomic snapshot.
@inproceedings(AspnesH1990waitfree,
title="Wait-free data structures in the asynchronous {PRAM} model",
author="James Aspnes and Maurice Herlihy",
booktitle="Second Annual ACM Symposium on Parallel Algorithms and Architectures",
month=jul,
year=1990,
pages={340--349}
)