A polylog time wait-free construction for closed objects
Tushar Deepak Chandra, Prasad Jayanti, King Tan · 1998
A (wait-free) universal construction is attractive because, no matter what types of wait-free objects are needed by applications, they can be implemented simply by instantiating the universal construction with the appropriate types. However, the worst-case time complexity of every existing n-process universal construction is # n): that is, in any implementation obtained by instantiating a universal construction, in the worst-case a process performs# n) computation in order to complete a single operation on the implemented object. In fact, a lower bound of # n) has been proved for the worst-case local time complexity of any oblivious universal construction [12]. Since universal constructions with sublinear time complexity do not seem possible, it is natural to explore "semiuniversal " constructions that can e#ciently implement large classes of objects (as opposed to all objects). We present such a construction in this paper. Our construction implements a large class of objects, that ...