Can an operation both update the state and return a meaningful value in the asynchronous PRAM model?
Hoepman, Jaap-Henk (2001) Can an operation both update the state and return a meaningful value in the asynchronous PRAM model? Information Processing Letters, 79 (4). pp. 161-166. ISSN 0020-0190
Restricted to UT campus only: Request a copy
|Abstract:||On an atomic Read-Modify-Write (RMW) object one can read the complete old contents s of the object and simultaneously update its contents as a function δ(s) of the old contents in a single, indivisible, atomic operation.
It is known that these RMW objects do not have a wait-free implementation in the asynchronous PRAM model—in which processors can only communicate with each other through atomic read-write registers. For the general case, in which operations P over an object can return a function φP(s) of the old contents s while simultaneously updating the object's state to δP(s), few results are known.
We give several characterizations, in terms of φP(·) and δP(·), of such objects for which no wait-free implementation in the asynchronous PRAM model exists. The resulting objects are remarkably similar to RMW objects. Indeed, we also exhibit two objects satisfying weaker conditions which do have a such a wait-free implementation. Our results suggest that only objects as strong as RMW objects do not have wait-free implementation in the asynchronous PRAM model.
|Copyright:||© 2001 Elsevier|
Electrical Engineering, Mathematics and Computer Science (EEMCS)
|Link to this item:||http://purl.utwente.nl/publications/74492|
|Export this item as:||BibTeX|
Daily downloads in the past month
Monthly downloads in the past 12 months
Repository Staff Only: item control page
Metis ID: 204108