Document Open Access Logo

Recoverable and Detectable Fetch&Add

Authors Liad Nahum , Hagit Attiya , Ohad Ben-Baruch , Danny Hendler

PDF
Thumbnail PDF

File

LIPIcs.OPODIS.2021.29.pdf
  • Filesize: 0.75 MB
  • 17 pages

Document Identifiers

Author Details

Liad Nahum
  • Department of Computer Science, Ben Gurion University, Beer Sheva, Israel
Hagit Attiya
  • Department of Computer Science, Technion, Haifa, Israel
Ohad Ben-Baruch
  • Department of Computer Science, Ben Gurion University, Beer Sheva, Israel
Danny Hendler
  • Department of Computer Science, Ben Gurion University, Beer Sheva, Israel

Funding

Supported by the Israel Science Foundation (grant number 380/18).

Cite As Get BibTex

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). Leibniz International Proceedings in Informatics (LIPIcs), Volume 217, pp. 29:1-29:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.OPODIS.2021.29

Abstract

The emergence of systems with non-volatile main memory (NVRAM) increases the need for persistent concurrent objects. Of specific interest are recoverable implementations that, in addition to being robust to crash-failures, are also detectable. Detectability ensures that upon recovery, it is possible to infer whether the failed operation took effect or not and, in the former case, obtain its response.
This work presents two recoverable detectable Fetch&Add (FAA) algorithms that are self-implementations, i.e, use only a fetch&add base object, in addition to read/write registers. The algorithms target two different models for recovery: the global-crash model and the individual-crash model. In both algorithms, operations are wait-free when there are no crashes, but the recovery code may block if there are repeated failures. We also prove that in the individual-crash model, there is no implementation of recoverable and detectable FAA using only read, write and fetch&add primitives in which all operations, including recovery, are lock-free.

Subject Classification

ACM Subject Classification
  • Theory of computation → Shared memory algorithms
Keywords
  • Multi-core algorithms
  • persistent memory
  • non-volatile memory

Metrics

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

References

  1. M. K. Aguilera and S. Frølund. Strict linearizability and the power of aborting. HPL-2003-241. Google Scholar
  2. Hagit Attiya, Ohad Ben-Baruch, and Danny Hendler. Nesting-safe recoverable linearizability: Modular constructions for non-volatile memory. In PODC, pages 7-16, 2018. Google Scholar
  3. Ohad Ben-Baruch, Danny Hendler, and Matan Rusanovsky. Upper and lower bounds on the space complexity of detectable objects. In PODC, 2020. Google Scholar
  4. Naama Ben-David, Guy E. Blelloch, Michal Friedman, and Yuanhao Wei. Delay-free concurrency on faulty persistent memory. In SPAA, pages 253-264, 2019. Google Scholar
  5. Ryan Berryhill, Wojciech Golab, and Mahesh Tripunitara. Robust shared objects for non-volatile main memory. In OPODIS, pages 20:1-20:17, 2016. Google Scholar
  6. Dhruva R. Chakrabarti, Hans-Juergen Boehm, and Kumud Bhandari. Atlas: leveraging locks for non-volatile memory consistency. In OOPSLA, pages 433-452, 2014. Google Scholar
  7. D. Y. C. Chan and P. Woelfel. Recoverable mutual exclusion with constant amortized RMR complexity from standard primitives. In PODC, 2020. Google Scholar
  8. Nachshon Cohen, Rachid Guerraoui, and Igor Zablotchi. The inherent cost of remembering consistently. In SPAA, pages 259-269, 2018. Google Scholar
  9. Andreia Correia, Pascal Felber, and Pedro Ramalhete. Romulus: Efficient algorithms for persistent transactional memory. In SPAA, pages 271-282, 2018. Google Scholar
  10. Andreia Correia, Pascal Felber, and Pedro Ramalhete. Persistent memory and the rise of universal constructions. In EuroSys, pages 5:1-5:15, 2020. Google Scholar
  11. Tudor David, Aleksandar Dragojevic, Rachid Guerraoui, and Igor Zablotchi. Log-free concurrent data structures. In USENIX, pages 373-386, 2018. Google Scholar
  12. Michael J. Fischer, Nancy A. Lynch, and Michael Paterson. Impossibility of distributed consensus with one faulty process. J. ACM, 32(2):374-382, 1985. Google Scholar
  13. 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 PLDI, pages 377-392, 2020. Google Scholar
  14. Michal Friedman, Maurice Herlihy, Virendra J. Marathe, and Erez Petrank. Brief announcement: A persistent lock-free queue for non-volatile memory. In DISC, pages 50:1-50:4, 2017. Google Scholar
  15. Michal Friedman, Maurice Herlihy, Virendra J. Marathe, and Erez Petrank. A persistent lock-free queue for non-volatile memory. In PPoPP, pages 28-40, 2018. Google Scholar
  16. Wojciech Golab. The recoverable consensus hierarchy. In SPAA, pages 281-291, 2020. Google Scholar
  17. Wojciech Golab and Danny Hendler. Recoverable mutual exclusion in sub-logarithmic time. In PODC, pages 211-220, 2017. Google Scholar
  18. Wojciech Golab and Aditya Ramaraju. Recoverable mutual exclusion. In PODC, pages 65-74, 2016. Google Scholar
  19. Wojciech M. Golab and Danny Hendler. Recoverable mutual exclusion under system-wide failures. In PODC, pages 17-26, 2018. Google Scholar
  20. R. Guerraoui and R. R. Levy. Robust emulations of shared memory in a crash recovery model. In ICDCS, pages 400-407, 2004. Google Scholar
  21. Maurice Herlihy. Wait free synchronization. ACM Transactions on Programming Languages and Systems, 11(1):124-149, 1991. Google Scholar
  22. Maurice P. Herlihy and Jennette M. Wing. Linearizability: A correctness condition for concurrent objects. ACM Transactions on Programming Languages and Systems, 12(3):463-492, 1990. Google Scholar
  23. J. Izraelevitz, H. Mendes, and M. L. Scott. Linearizability of persistent memory objects under a full-system-crash failure model. In DISC, pages 313-327, 2016. Google Scholar
  24. Joseph Izraelevitz, Terence Kelly, and Aasheesh Kolli. Failure-atomic persistent memory updates via JUSTDO logging. In ASPLOS, pages 427-442, 2016. Google Scholar
  25. Prasad Jayanti, Siddhartha V. Jayanti, and Anup Joshi. Recoverable mutex algorithm with sub-logarithmic RMR on both CC and DSM. In PODC, pages 177-186, 2019. Google Scholar
  26. Faisal Nawab, Joseph Izraelevitz, Terence Kelly, Charles B. Morrey III, Dhruva R. Chakrabarti, and Michael L. Scott. Dalí: A periodically persistent hash map. In DISC, pages 37:1-37:16, 2017. Google Scholar
  27. Pedro Ramalhete, Andreia Correia, Pascal Felber, and Nachshon Cohen. Onefile: A wait-free persistent transactional memory. In DSN, pages 151-163, 2019. Google Scholar
  28. David Schwalb, Markus Dreseler, Matthias Uflacker, and Hasso Plattner. Nvc-hashmap: A persistent and concurrent hashmap for non-volatile memories. In VLDB Workshop on In-Memory Data Mangement and Analytics, pages 4:1-4:8, 2015. Google Scholar
  29. Yoav Zuriel, Michal Friedman, Gali Sheffi, Nachshon Cohen, and Erez Petrank. Efficient lock-free durable sets. In OOPSLA, pages 128:1-128:26, 2019. 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