English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

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 0 is an n-process type T object implemented using U, in the worst-case some process must perform n(n) local computation in order to complete a single operation on 0. 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 0 is implemented using an oblivious universal construction, then no matter what O’s type is, in the worst-case some process must perform n(n) local computation in order to complete a single operation on 0. Thus, if our goal is to implement shared objects whose operations run in sublinear time (preferably constant or polylogarithmic time), oblivious universal constructions cannot be useful; the design of sublinear time implementations must necessatily exploit the semantics of the type being implemented. It is especially notable that our lower bound holds regardless of how powerful the underlying shared-memory iseven if shared-memory has unbounded size and each process, in each step, can read all of the shared memory and update it in arbitrary ways. Further, the lower bound holds even if each process is restricted to applying only one operation on the universal construction. Finally, the lower bound is tight: some existing wait-free universal constructions [la, 13, l] have O(n) worst-case time complexity. *This work is partially supported by NSF RIA grant CCR9410421. Permissioo to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advaotage and that copies bear this notice and the tidl citation on the fti page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. PODC 98 Puerto Vallarta Mexico Copyright ACM 1998 O-89791-977-7/98/ 6...$5.00

A lower bound on the local time complexity of universal constructions