Document Open Access Logo

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

Authors Hagit Attiya , Constantin Enea , Jennifer L. Welch

PDF

File

Thumbnail PDF
PDF
LIPIcs.DISC.2021.7.pdf
  • Filesize: 0.74 MB
  • 18 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed computing models
  • Computing methodologies → Distributed algorithms
  • Computing methodologies → Concurrent algorithms
  • Theory of computation → Concurrent algorithms
  • Theory of computation → Distributed algorithms
Keywords
  • Concurrent Objects
  • Message-passing systems
  • Strong linearizability
  • Impossibility proofs
  • BG simulation
  • Shared registers

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

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.

Cite As Get BibTex

Hagit Attiya, Constantin Enea, and Jennifer L. Welch. Impossibility of Strongly-Linearizable Message-Passing Objects via Simulation by Single-Writer Registers. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 7:1-7:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.DISC.2021.7

Author Details

Hagit Attiya
  • Computer Science Department, Technion, Haifa, Israel
Constantin Enea
  • Université de Paris, IRIF, CNRS, France
Jennifer L. Welch
  • Texas A&M University, College Station, TX, USA

Funding

  • Attiya, Hagit: Partially supported by the Israel Science Foundation (grant number 380/18).
  • Enea, Constantin: Supported in part by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation program (grant agreement No 678177).
  • Welch, Jennifer L.: Supported in part by the U.S. National Science Foundation under grant number 1816922.

Acknowledgements

We thank the anonymous referees for helpful comments that improved the presentation of the paper.

References

  1. Yehuda Afek, Hagit Attiya, Danny Dolev, Eli Gafni, Michael Merritt, and Nir Shavit. Atomic snapshots of shared memory. J. ACM, 40(4):873-890, 1993. Google Scholar
  2. James Aspnes and Maurice Herlihy. Wait-free data structures in the asynchronous PRAM model. In SPAA, pages 340-349, 1990. Google Scholar
  3. Hagit Attiya, Amotz Bar-Noy, and Danny Dolev. Sharing memory robustly in message-passing systems. J. ACM, 42(1):124-142, 1995. Google Scholar
  4. Hagit Attiya, Armando Castañeda, and Danny Hendler. Nontrivial and universal helping for wait-free queues and stacks. Journal of Parallel and Distributed Computing, 121:1-14, 2018. Google Scholar
  5. Hagit Attiya and Constantin Enea. Putting strong linearizability in context: Preserving hyperproperties in programs that use concurrent objects. In DISC, pages 2:1-2:17, 2019. Google Scholar
  6. Hagit Attiya, Constantin Enea, and Jennifer L. Welch. Linearizable implementations suffice for termination of randomized concurrent programs. CoRR, abs/2106.15554, 2021. URL: http://arxiv.org/abs/2106.15554.
  7. Elizabeth Borowsky and Eli Gafni. Generalized FLP impossibility result for t-resilient asynchronous computations. In STOC, pages 91-100, 1993. Google Scholar
  8. Michael R. Clarkson and Fred B. Schneider. Hyperproperties. Journal of Computer Security, 18(6):1157-1210, 2010. Google Scholar
  9. Oksana Denysyuk and Philipp Woelfel. Wait-freedom is harder than lock-freedom under strong linearizability. In DISC, pages 60-74, 2015. Google Scholar
  10. Danny Dolev and Eli Gafni. Synchronous hybrid message-adversary. CoRR, abs/1605.02279, 2016. URL: http://arxiv.org/abs/1605.02279.
  11. Pierre Fraigniaud, Eli Gafni, Sergio Rajsbaum, and Matthieu Roy. Automatically adjusting concurrency to the level of synchrony. In DISC, pages 1-15, 2014. Google Scholar
  12. Eli Gafni. The extended BG-simulation and the characterization of t-resiliency. In STOC, pages 85-92, 2009. Google Scholar
  13. Eli Gafni and Leslie Lamport. Disk Paxos. Distributed Computing, 16(1):1-20, 2003. Google Scholar
  14. Wojciech Golab, Lisa Higham, and Philipp Woelfel. Linearizable implementations do not suffice for randomized distributed computation. In STOC, pages 373-382, 2011. Google Scholar
  15. Theophanis Hadjistasi, Nicolas Nicolaou, and Alexander A. Schwarzmann. Oh-ram! one and a half round atomic memory. In NETYS, pages 117-132. Springer International Publishing, 2017. Google Scholar
  16. Vassos Hadzilacos, Xing Hu, and Sam Toueg. On atomic registers and randomized consensus in M&M systems (version 4). CoRR, abs/1906.00298, 2020. URL: http://arxiv.org/abs/1906.00298.
  17. Vassos Hadzilacos, Xing Hu, and Sam Toueg. On register linearizability and termination. In PODC, pages 521-531, 2021. Google Scholar
  18. Maryam Helmi, Lisa Higham, and Philipp Woelfel. Strongly linearizable implementations: possibilities and impossibilities. In PODC, pages 385-394, 2012. Google Scholar
  19. Maurice P. Herlihy and Jeannette M. Wing. Linearizability: A correctness condition for concurrent objects. ACM Trans. Program. Lang. Syst., 12(3):463-492, 1990. Google Scholar
  20. Kaile Huang, Yu Huang, and Hengfeng Wei. Fine-grained analysis on fast implementations of distributed multi-writer atomic registers. In PODC, pages 200-209, 2020. Google Scholar
  21. Damien Imbs and Michel Raynal. Visiting Gafni’s reduction land: From the BG simulation to the extended BG simulation. In SSS, pages 369-383, 2009. Google Scholar
  22. Damien Imbs, Michel Raynal, and Julien Stainer. Are Byzantine failures really different from crash failures? In DISC, pages 215-229, 2016. Google Scholar
  23. Petr Kuznetsov. Universal model simulation: BG and extended BG as examples. In SSS, pages 17-31, 2013. Google Scholar
  24. Nancy A. Lynch and Alexander A. Shvartsman. Robust emulation of shared memory using dynamic quorum-acknowledged broadcasts. In FTCS, pages 272-281, 1997. Google Scholar
  25. Nancy A. Lynch and Frits W. Vaandrager. Forward and backward simulations: I. untimed systems. Inf. Comput., 121(2):214-233, 1995. URL: https://doi.org/10.1006/inco.1995.1134.
  26. Sean Ovens and Philipp Woelfel. Strongly linearizable implementations of snapshots and other types. In PODC, pages 197-206, 2019. Google Scholar
  27. Amgad Sadek Rady. Characterizing Implementations that Preserve Properties of Concurrent Randomized Algorithms. Master’s thesis, York University, Toronto, Canada, 2017. Google Scholar
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact