License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.DISC.2021.7
URN: urn:nbn:de:0030-drops-148096
URL: https://drops.dagstuhl.de/opus/volltexte/2021/14809/
Go to the corresponding LIPIcs Volume Portal

Attiya, Hagit ; Enea, Constantin ; Welch, Jennifer L.

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

pdf-format:
LIPIcs-DISC-2021-7.pdf (0.7 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{attiya_et_al:LIPIcs.DISC.2021.7,
  author =	{Attiya, Hagit and Enea, Constantin and Welch, Jennifer L.},
  title =	{{Impossibility of Strongly-Linearizable Message-Passing Objects via Simulation by Single-Writer Registers}},
  booktitle =	{35th International Symposium on Distributed Computing (DISC 2021)},
  pages =	{7:1--7:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-210-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{209},
  editor =	{Gilbert, Seth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/14809},
  URN =		{urn:nbn:de:0030-drops-148096},
  doi =		{10.4230/LIPIcs.DISC.2021.7},
  annote =	{Keywords: Concurrent Objects, Message-passing systems, Strong linearizability, Impossibility proofs, BG simulation, Shared registers}
}

Keywords: Concurrent Objects, Message-passing systems, Strong linearizability, Impossibility proofs, BG simulation, Shared registers
Collection: 35th International Symposium on Distributed Computing (DISC 2021)
Issue Date: 2021
Date of publication: 04.10.2021

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI