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 Tools annual

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 monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

The emergence of systems with non-volatile main memory (NVM) increases theinterest in the design of \emph{recoverable concurrent objects} that are robustto crash-failures, since their operations are able to recover from suchfailures by using state retained in NVM. Of particular interest are recoverablealgorithms that, in addition to ensuring object consistency, also provide\emph{detectability}, a correctness condition requiring that the recovery codecan infer if the failed operation was linearized or not and, in the formercase, obtain its response.  In this work, we investigate the space complexity of detectable algorithmsand the external support they require. We make the following threecontributions. First, we present the first wait-free bounded-space detectableread/write and CAS object implementations. Second, we prove that the bitcomplexity of every $N$-process obstruction-free detectable CAS implementation,assuming values from a domain of size at least $N$, is $\Omega(N)$. Finally, weprove that the following holds for obstruction-free detectable implementationsof a large class of objects: their recoverable operations must be provided with\emph{auxiliary state} -- state that is not required by the non-recoverablecounterpart implementation -- whose value must be provided from outside theoperation, either by the system or by the caller of the operation. In contrast,this external support is, in general, not required if the recoverable algorithmis not detectable.

Upper and Lower Bounds on the Space Complexity of Detectable Object