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

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:	Computer Architecture for Embedded Systems (CAES)
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

Show download statistics for this publication

Repository Staff Only: item control page

Metis ID: 204108