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 Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

A key way to construct complex distributed systems is through modularcomposition of linearizable concurrent objects. A prominent example is sharedregisters, which have crash-tolerant implementations on top of message-passingsystems, allowing the advantages of shared memory to carry over tomessage-passing. Yet linearizable registers do not always behave properly whenused inside randomized programs. A strengthening of linearizability, calledstrong linearizability, has been shown to preserve probabilistic behavior, aswell as other hypersafety properties. In order to exploit composition andabstraction in message-passing systems, it is crucial to know whether thereexist strongly-linearizable implementations of registers in message-passing.This paper answers the question in the negative: there are nostrongly-linearizable fault-tolerant message-passing implementations ofmulti-writer registers, max-registers, snapshots or counters. This result isproved by reduction from the corresponding result by Helmi et al. The reductionis a novel extension of the BG simulation that connects shared-memory andmessage-passing, supports long-lived objects, and preserves stronglinearizability. The main technical challenge arises from the discrepancybetween the potentially minuscule fraction of failures to be tolerated in thesimulated message-passing algorithm and the large fraction of failures that canafflict the simulating shared-memory system. The reduction is general and canbe viewed as the inverse of the ABD simulation of shared memory inmessage-passing.

Impossibility of Strongly-Linearizable Message-Passing Objects via Simulation by Single-Writer Registers