Polylog time wait-free construction for closed objects

Abstract

A wait-free universal construction is attractive because, no matter what type 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.