Can an operation both update the state and return a meaningfull value in the asynchronous pram model?

J.H. Hoepman

    Research output: Contribution to journalArticleAcademic

    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.
    Original languageUndefined
    Pages (from-to)161-166
    Number of pages5
    JournalInformation processing letters
    Volume79
    Issue number4
    DOIs
    Publication statusPublished - 2001

    Keywords

    • IR-74492
    • Read-modify-write objects
    • Shared memory
    • Fault Tolerance
    • METIS-204108
    • Asynchronous PRAM model
    • Distributed Computing
    • Parallel processing

    Cite this