Document Open Access Logo

Brief Announcement: Recoverable and Detectable Self-Implementations of Swap

Authors Tomer Lev Lehman, Hagit Attiya , Danny Hendler

PDF
Thumbnail PDF

File

LIPIcs.DISC.2023.44.pdf
  • Filesize: 0.53 MB
  • 7 pages

Document Identifiers

Author Details

Tomer Lev Lehman
  • Department of Computer Science, Ben Gurion University, Beer Sheva, Israel
Hagit Attiya
  • Department of Computer Science, Technion, Haifa, Israel
Danny Hendler
  • Department of Computer Science, Ben Gurion University, Beer Sheva, Israel

Funding

Partially supported by the Israel Science Foundation (grants 380/18 and 22/1425).
  • Lev Lehman, Tomer: Partially supported by the Lynne and William Frankel Center for Computer Science.

Cite As Get BibTex

Tomer Lev Lehman, Hagit Attiya, and Danny Hendler. Brief Announcement: Recoverable and Detectable Self-Implementations of Swap. In 37th International Symposium on Distributed Computing (DISC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 281, pp. 44:1-44:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.DISC.2023.44

Abstract

Recoverable algorithms tolerate failures and recoveries of processes by using non-volatile memory. Of particular interest are self-implementations of key operations, in which a recoverable operation is implemented from its non-recoverable counterpart (in addition to reads and writes). 
This paper presents two self-implementations of the SWAP operation. One works in the system-wide failures model, where all processes fail and recover together, and the other in the independent failures model, where each process crashes and recovers independently of the other processes.
Both algorithms are wait-free in crash-free executions, but their recovery code is blocking. We prove that this is inherent for the independent failures model. The impossibility result is proved for implementations of distinguishable operations using interfering functions, and in particular, it applies to a recoverable self-implementation of swap.

Subject Classification

ACM Subject Classification
  • Theory of computation → Shared memory algorithms
Keywords
  • Persistent memory
  • non-volatile memory
  • recoverable objects
  • detectablitly

Metrics

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

Related Versions

References

  1. Hagit Attiya, Ohad Ben-Baruch, and Danny Hendler. Nesting-safe recoverable linearizability: Modular constructions for non-volatile memory. In ACM Symposium on Principles of Distributed Computing, pages 7-16, 2018. Google Scholar
  2. Ohad Ben-Baruch, Danny Hendler, and Matan Rusanovsky. Upper and lower bounds on the space complexity of detectable objects. In 39th ACM Symposium on Principles of Distributed Computing, pages 11-20, 2020. Google Scholar
  3. Naama Ben-David, Guy E Blelloch, Michal Friedman, and Yuanhao Wei. Delay-free concurrency on faulty persistent memory. In 31st ACM Symposium on Parallelism in Algorithms and Architectures, pages 253-264, 2019. Google Scholar
  4. Ryan Berryhill, Wojciech Golab, and Mahesh Tripunitara. Robust shared objects for non-volatile main memory. In 19th International Conference on Principles of Distributed Systems (OPODIS). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2016. Google Scholar
  5. Kyeongmin Cho, Seungmin Jeon, and Jeehoon Kang. Practical detectability for persistent lock-free data structures. arXiv preprint arXiv:2203.07621, 2022. Google Scholar
  6. Andreia Correia, Pascal Felber, and Pedro Ramalhete. Persistent memory and the rise of universal constructions. In 15th European Conference on Computer Systems, pages 1-15, 2020. Google Scholar
  7. Panagiota Fatourou, Nikolaos D Kallimanis, and Eleftherios Kosmas. The performance power of software combining in persistence. In 27th ACM Symposium on Principles and Practice of Parallel Programming, pages 337-352, 2022. Google Scholar
  8. Michal Friedman, Naama Ben-David, Yuanhao Wei, Guy E Blelloch, and Erez Petrank. NVTraverse: In NVRAM data structures, the destination is more important than the journey. In 41st ACM Conference on Programming Language Design and Implementation, pages 377-392, 2020. Google Scholar
  9. Michal Friedman, Maurice Herlihy, Virendra Marathe, and Erez Petrank. A persistent lock-free queue for non-volatile memory. ACM SIGPLAN Notices, 53(1):28-40, 2018. Google Scholar
  10. Wojciech Golab. The recoverable consensus hierarchy. In 32nd ACM Symposium on Parallelism in Algorithms and Architectures, pages 281-291, 2020. Google Scholar
  11. Wojciech Golab and Danny Hendler. Recoverable mutual exclusion in sub-logarithmic time. In ACM Symposium on Principles of Distributed Computing, pages 211-220, 2017. Google Scholar
  12. Wojciech Golab and Aditya Ramaraju. Recoverable mutual exclusion. In 2016 ACM Symposium on Principles of Distributed Computing, pages 65-74, 2016. Google Scholar
  13. Maurice Herlihy. Wait-free synchronization. ACM Transactions on Programming Languages and Systems, 13(1):124-149, 1991. Google Scholar
  14. Morteza Hoseinzadeh and Steven Swanson. Corundum: Statically-enforced persistent memory safety. In 26th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, pages 429-442, 2021. Google Scholar
  15. Joseph Izraelevitz, Terence Kelly, and Aasheesh Kolli. Failure-atomic persistent memory updates via justdo logging. ACM SIGARCH Computer Architecture News, 44(2):427-442, 2016. Google Scholar
  16. Joseph Izraelevitz, Hammurabi Mendes, and Michael L Scott. Linearizability of persistent memory objects under a full-system-crash failure model. In 30th International Symposium on Distributed Computing, pages 313-327. Springer, 2016. Google Scholar
  17. Prasad Jayanti, Siddhartha Jayanti, and Anup Joshi. A recoverable mutex algorithm with sub-logarithmic RMR on both cc and dsm. In ACM Symposium on Principles of Distributed Computing, pages 177-186, 2019. Google Scholar
  18. Nan Li and Wojciech Golab. Detectable sequential specifications for recoverable shared objects. In 35th International Symposium on Distributed Computing (DISC), 2021. Google Scholar
  19. John M Mellor-Crummey and Michael L Scott. Algorithms for scalable synchronization on shared-memory multiprocessors. ACM Transactions on Computer Systems, 9(1):21-65, 1991. Google Scholar
  20. Liad Nahum, Hagit Attiya, Ohad Ben-Baruch, and Danny Hendler. Recoverable and detectable fetch&add. In 25th International Conference on Principles of Distributed Systems (OPODIS 2021). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2022. Google Scholar
  21. Matan Rusanovsky, Hagit Attiya, Ohad Ben-Baruch, Tom Gerby, Danny Hendler, and Pedro Ramalhete. Flat-combining-based persistent data structures for non-volatile memory. In 23rd International Symposium on Stabilization, Safety, and Security of Distributed Systems, SSS, pages 505-509. Springer, 2021. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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