Can an operation both update the state and return a meaningful value in the asynchronous PRAM model?

Share/Save/Bookmark

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

[img]PDF
Restricted to UT campus only
: Request a copy
83Kb
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.
Item Type:Article
Copyright:© 2001 Elsevier
Faculty:
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:http://purl.utwente.nl/publications/74492
Official URL:http://dx.doi.org/10.1016/S0020-0190(00)00188-5
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page

Metis ID: 204108