Abstract A universal construction is a general mechanism for obtaining a concurrent implementation of an object from its sequential code. We show that there is no universal construction that is both disjoint-access parallel (guaranteeing the processes operating on different parts of an implemented object do not interfere with one another) and wait-free (guaranteeing progress for each nonfaulty process when accessing an object). In contrast, we present a universal construction which results in disjoint-access parallel, wait-free implementations of any object provided there is a bound on the number of data items accessed by each operation supported by the object. A preliminary version of this work appeared in the
The universal construction in REF ensures wait-freedom when applied to objects that have a bound on the number of data items accessed by each operation they support, and lock-freedom in other cases.
Universal constructions that ensure disjoint-access parallelism and wait-freedom
Distributed Computing
Distributed Computing
Engineering Computer Science