2026-07-21T14:13:13Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14809 2025-06-20T09:17:04Z ddc:004 open_access

Impossibility of Strongly-Linearizable Message-Passing Objects via Simulation by Single-Writer Registers Attiya, Hagit Enea, Constantin Welch, Jennifer L. Concurrent Objects Message-passing systems Strong linearizability Impossibility proofs BG simulation Shared registers A key way to construct complex distributed systems is through modular composition of linearizable concurrent objects. A prominent example is shared registers, which have crash-tolerant implementations on top of message-passing systems, allowing the advantages of shared memory to carry over to message-passing. Yet linearizable registers do not always behave properly when used inside randomized programs. A strengthening of linearizability, called strong linearizability, has been shown to preserve probabilistic behavior, as well as other "hypersafety" properties. In order to exploit composition and abstraction in message-passing systems, it is crucial to know whether there exist strongly-linearizable implementations of registers in message-passing. This paper answers the question in the negative: there are no strongly-linearizable fault-tolerant message-passing implementations of multi-writer registers, max-registers, snapshots or counters. This result is proved by reduction from the corresponding result by Helmi et al. The reduction is a novel extension of the BG simulation that connects shared-memory and message-passing, supports long-lived objects, and preserves strong linearizability. The main technical challenge arises from the discrepancy between the potentially minuscule fraction of failures to be tolerated in the simulated message-passing algorithm and the large fraction of failures that can afflict the simulating shared-memory system. The reduction is general and can be viewed as the inverse of the ABD simulation of shared memory in message-passing. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Hagit Attiya and Constantin Enea and Jennifer L. Welch 2021 Is Part Of LIPIcs, Volume 209, 35th International Symposium on Distributed Computing (DISC 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.DISC.2021.7 urn:nbn:de:0030-drops-148096 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2021.7 eng https://creativecommons.org/licenses/by/4.0/legalcode