|
Abstract : |
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 nite number of steps, and it is k-bounded wait-free, for some k> 0, if every operation will complete within k steps. In the rst 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 innite 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. 1 During much of the work described in this paper, J. Aspnes was funded by an IBM, |
