A lower bound on the local time complexity of universal constructions
Prasad Jayanti · 1998
Non-blocking and wait-free universal constructions have been a subject of active research in recent years. A universal construction is attractive because, no matter what types of shared objects are needed by applications, they can be implemented simply by instantiating the universal construction with appropriate types. This flexibility, however, comes at a cost: for each universal construction U , we prove that there is a type T such that, if O is an n-process type T object implemented using U , in the worst-case some process must perform# n) local computation in order to complete a single operation on O. A universal construction is oblivious if it does not exploit the semantics of the type that it is instantiated with. Our lower bound implies that if a shared object O is implemented using an oblivious universal construction, then no matter what O's type is, in the worst-case some process must perform# n) local computation in order to complete a single operation on O. Thu...