short-paper

Tracking in Order to Recover - Detectable Recovery of Lock-Free Data Structures

Authors:

Ohad Ben-Baruch,

Panagiota Fatourou,

Eleftherios KosmasAuthors Info & Claims

SPAA '20: Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures

Pages 503 - 505

https://doi.org/10.1145/3350755.3400257

Published: 09 July 2020 Publication History

Abstract

We present the tracking approach for deriving detectable implementations of many widely-used concurrent data structures for systems with non-volatile main memory (NVRAM). Detectable recovery ensures that in the crash-recovery model, every operation executed during a crash, resumes its execution and returns a correct response, and that the state of the data structure is not corrupted.

References

[1]

Hagit Attiya, Ohad Ben-Baruch, Panagiota Fatourou, Danny Hendler, and Eleftherios Kosmas. 2019. Tracking in Order to Recover: Recoverable Lock-Free Data Structures. CoRR, Vol. abs/1905.13600 (2019). http://arxiv.org/abs/1905.13600

[2]

Hagit Attiya, Ohad Ben-Baruch, and Danny Hendler. 2018. Nesting-Safe Recoverable Linearizability: Modular Constructions for Non-Volatile Memory. In ACM Symp on Principles of Distributed Computing (PODC). 7--16.

Digital Library

[3]

Greg Barnes. 1993. A Method for Implementing Lock-Free Shared-Data Structures. In 5th ACM Symp on Parallel Algorithms and Architectures (SPAA). 261--270.

Digital Library

[4]

Naama Ben-David, Guy E Blelloch, Michal Friedman, and Yuanhao Wei. 2019. Delay-free concurrency on faulty persistent memory. In 31st ACM Symp on Parallelism in Algorithms and Architectures (SPAA). 253--264.

Digital Library

[5]

Shimin Chen and Qin Jin. 2015. Persistent B+-Trees in Non-Volatile Main Memory. Proceedings VLDB, Vol. 8, 7 (2015), 786--797.

Digital Library

[6]

Joel Coburn, Adrian M. Caulfield, Ameen Akel, Laura M. Grupp, Rajesh K. Gupta, Ranjit Jhala, and Steven Swanson. 2011. NV-Heaps: making persistent objects fast and safe with next-generation, non-volatile memories. In 16th International Conf on Architectural Support for Programming Languages and Operating Systems (ASPLOS) .

Digital Library

[7]

Faith Ellen, Panagiota Fatourou, Eric Ruppert, and Franck van Breugel. 2010. Non-blocking binary search trees. In 29th ACM Symp on Principles of Distributed Computing (PODC). 131--140.

Digital Library

[8]

Steven Feldman, Carlos Valera-Leon, and Damian Dechev. 2016. An efficient wait-free vector. IEEE Trans on Parallel and Distributed Systems, Vol. 27, 3 (2016), 654--667.

Digital Library

[9]

Mikhail Fomitchev and Eric Ruppert. 2004. Lock-free linked lists and skip lists. In 23rd ACM Symp on Principles of Distributed Computing, PODC. 50--59.

Digital Library

[10]

Michal Friedman, Maurice Herlihy, Virendra J. Marathe, and Erez Petrank. 2018. A persistent lock-free queue for non-volatile memory. In 23rd ACM SIGPLAN Symp on Principles and Practice of Parallel Programming (PPoPP). 28--40.

Digital Library

[11]

Timothy L. Harris. 2001. A Pragmatic Implementation of Non-blocking Linked-Lists. In Distributed Computing, 15th International Conf (DISC). 300--314.

[12]

Danny Hendler, Nir Shavit, and Lena Yerushalmi. 2010. A scalable lock-free stack algorithm. J. Parallel Distrib. Comput., Vol. 70, 1 (2010), 1--12.

Digital Library

[13]

Joseph Izraelevitz, Hammurabi Mendes, and Michael L. Scott. 2016. Linearizability of Persistent Memory Objects Under a Full-System-Crash Failure Model. In 30th International Symp on Distributed Computing DISC. 313--327.

[14]

Maged M. Michael and Michael L. Scott. 1996. Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms. In 15th ACM Symp on Principles of Distributed Computing (PODC). 267--275.

[15]

Shivaram Venkataraman, Niraj Tolia, Parthasarathy Ranganathan, and Roy H. Campbell. 2011. Consistent and Durable Data Structures for Non-Volatile Byte-Addressable Memory. In 9th USENIX Conf on File and Storage Technologies. 61--75.

Cited By

Cho KJeon SRaad AKang J(2023)Memento: A Framework for Detectable Recoverability in Persistent MemoryProceedings of the ACM on Programming Languages10.1145/35912327:PLDI(292-317)Online publication date: 6-Jun-2023
https://dl.acm.org/doi/10.1145/3591232
Fatourou PKosmas EPalpanas TPaterakis G(2023)FreSh: A Lock-Free Data Series Index2023 42nd International Symposium on Reliable Distributed Systems (SRDS)10.1109/SRDS60354.2023.00029(209-220)Online publication date: 25-Sep-2023
https://doi.org/10.1109/SRDS60354.2023.00029
Moridi MWang ECui AGolab WGeorgiou CSchiller EAli-Eldin AIosup A(2022)A Closer Look at Detectable Objects for Persistent MemoryProceedings of the 2022 Workshop on Advanced tools, programming languages, and PLatforms for Implementing and Evaluating algorithms for Distributed systems10.1145/3524053.3542749(56-64)Online publication date: 25-Jul-2022
https://dl.acm.org/doi/10.1145/3524053.3542749
Show More Cited By

Index Terms

Tracking in Order to Recover - Detectable Recovery of Lock-Free Data Structures
1. Hardware
  1. Integrated circuits
    1. Semiconductor memory
      1. Non-volatile memory
2. Theory of computation
  1. Models of computation
    1. Concurrency
      1. Parallel computing models

Recommendations

Detectable recovery of lock-free data structures
PPoPP '22: Proceedings of the 27th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming

This paper presents a generic approach for deriving detectably recoverable implementations of many widely-used concurrent data structures. Such implementations are appealing for emerging systems featuring byte-addressable non-volatile main memory (NVMM), ...
Mirror: making lock-free data structures persistent
PLDI 2021: Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation

With the recent launch of the Intel Optane memory platform, non-volatile main memory in the form of fast, dense, byte-addressable non-volatile memory has now become available. Nevertheless, designing crash-resilient algorithms and data structures is ...
Upper and Lower Bounds on the Space Complexity of Detectable Objects
PODC '20: Proceedings of the 39th Symposium on Principles of Distributed Computing

The emergence of systems with non-volatile main memory (NVM) increases the interest in the design of recoverable concurrent objects that are robust to crash-failures, since their operations are able to recover from such failures by using state retained ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SPAA '20: Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures

July 2020

601 pages

ISBN:9781450369350

DOI:10.1145/3350755

General Chair:
Christian Scheideler
Institut fuer Informatik Universitaet Paderborn Fuerstenallee 11
,
Program Chair:
Michael Spear

Copyright © 2020 Owner/Author.

Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for third-party components of this work must be honored. For all other uses, contact the Owner/Author.

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGARCH: ACM Special Interest Group on Computer Architecture
EATCS: European Association for Theoretical Computer Science

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 09 July 2020

Check for updates

Author Tags

Qualifiers

Short-paper

Funding Sources

ISF
ESF

Conference

SPAA '20

Sponsor:

SPAA '20: 32nd ACM Symposium on Parallelism in Algorithms and Architectures

July 15 - 17, 2020

Virtual Event, USA

Acceptance Rates

Overall Acceptance Rate 447 of 1,461 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
140
Total Downloads

Downloads (Last 12 months)5
Downloads (Last 6 weeks)0

Reflects downloads up to 26 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Cho KJeon SRaad AKang J(2023)Memento: A Framework for Detectable Recoverability in Persistent MemoryProceedings of the ACM on Programming Languages10.1145/35912327:PLDI(292-317)Online publication date: 6-Jun-2023
https://dl.acm.org/doi/10.1145/3591232
Fatourou PKosmas EPalpanas TPaterakis G(2023)FreSh: A Lock-Free Data Series Index2023 42nd International Symposium on Reliable Distributed Systems (SRDS)10.1109/SRDS60354.2023.00029(209-220)Online publication date: 25-Sep-2023
https://doi.org/10.1109/SRDS60354.2023.00029
Moridi MWang ECui AGolab WGeorgiou CSchiller EAli-Eldin AIosup A(2022)A Closer Look at Detectable Objects for Persistent MemoryProceedings of the 2022 Workshop on Advanced tools, programming languages, and PLatforms for Implementing and Evaluating algorithms for Distributed systems10.1145/3524053.3542749(56-64)Online publication date: 25-Jul-2022
https://dl.acm.org/doi/10.1145/3524053.3542749
Attiya HBen-Baruch OFatourou PHendler DKosmas ELee JAgrawal KSpear M(2022)Detectable recovery of lock-free data structuresProceedings of the 27th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming10.1145/3503221.3508444(262-277)Online publication date: 2-Apr-2022
https://dl.acm.org/doi/10.1145/3503221.3508444
Wei YBen-David NFriedman MBlelloch GPetrank ELee JAgrawal KSpear M(2022)FliTProceedings of the 27th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming10.1145/3503221.3508436(309-321)Online publication date: 2-Apr-2022
https://dl.acm.org/doi/10.1145/3503221.3508436
Fatourou PKallimanis NKosmas ELee JAgrawal KSpear M(2022)The performance power of software combining in persistenceProceedings of the 27th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming10.1145/3503221.3508426(337-352)Online publication date: 2-Apr-2022
https://dl.acm.org/doi/10.1145/3503221.3508426
Fridman YSnir YLevin HHendler DAttiya HOren G(2022)Recovery of Distributed Iterative Solvers for Linear Systems Using Non-Volatile RAM2022 IEEE/ACM 12th Workshop on Fault Tolerance for HPC at eXtreme Scale (FTXS)10.1109/FTXS56515.2022.00007(11-23)Online publication date: Nov-2022
https://doi.org/10.1109/FTXS56515.2022.00007
Dhulipala LMcGuffey CKang HGu YBlelloch GGibbons PShun J(2020)SageProceedings of the VLDB Endowment10.14778/3397230.339725113:9(1598-1613)Online publication date: 1-May-2020
https://dl.acm.org/doi/10.14778/3397230.3397251

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents