Document Open Access Logo

Durable Algorithms for Writable LL/SC and CAS with Dynamic Joining

Authors Prasad Jayanti , Siddhartha Jayanti , Sucharita Jayanti

PDF
Thumbnail PDF

File

LIPIcs.DISC.2023.25.pdf
  • Filesize: 0.83 MB
  • 20 pages

Document Identifiers

Author Details

Prasad Jayanti
  • Dartmouth College, Hanover, NH, USA
Siddhartha Jayanti
  • Google Research, Atlanta, GA, USA
Sucharita Jayanti
  • Brown University, Providence, RI, USA

Funding

Prasad Jayanti was supported in part by the James Frank Family Professorship. Siddhartha Jayanti was supported in part by an NDSEG Graduate Research Fellowship.

Cite As Get BibTex

Prasad Jayanti, Siddhartha Jayanti, and Sucharita Jayanti. Durable Algorithms for Writable LL/SC and CAS with Dynamic Joining. In 37th International Symposium on Distributed Computing (DISC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 281, pp. 25:1-25:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.DISC.2023.25

Abstract

We present durable implementations for two well known universal primitives - CAS (compare-and-swap), and its ABA-free counter-part LLSC (load-linked, store-conditional). Our implementations satisfy method-based recoverable linearizability (MRL) and method-based detectability (M-detectability) - novel correctness conditions that require only a simple usage pattern to guarantee resilience to individual process crashes (and system-wide crashes), including in implementations with nesting. Additionally, our implementations are: writable, meaning they support a Write() operation; have constant time complexity per operation; allow for dynamic joining, meaning newly created processes (a.k.a. threads) of arbitrary names can join a protocol and access our implementations; and have adaptive space complexity, meaning the space use scales in the number of processes n that actually use the objects, as opposed to previous protocols whose space complexity depends on N, the maximum number of processes that the protocol is designed for. Our durable Writable-CAS implementation, DuraCAS, requires O(m + n) space to support m objects that get accessed by n processes, improving on the state-of-the-art O(m + N²). By definition, LLSC objects must store "contexts" in addition to object values. Our Writable-LLSC implementation, DuraLL, requires O(m + n + C) space, where C is the number of "contexts" stored across all the objects. While LLSC has an advantage over CAS due to being ABA-free, the object definition seems to require additional space usage. To address this trade-off, we define an External Context (EC) variant of LLSC. Our EC Writable-LLSC implementation is ABA-free and has a space complexity of just O(m + n).

To our knowledge, our algorithms are the first durable CAS algorithms that allow for dynamic joining, and are the first to exhibit adaptive space complexity. To our knowledge, we are the first to implement any type of durable LLSC objects.

Subject Classification

ACM Subject Classification
  • Computer systems organization → Dependable and fault-tolerant systems and networks
  • Theory of computation → Concurrency
  • Theory of computation → Concurrent algorithms
  • Theory of computation → Parallel algorithms
  • Theory of computation → Data structures design and analysis
  • Theory of computation → Distributed algorithms
Keywords
  • durable
  • recoverable
  • detectable
  • persistent memory
  • dynamic joining
  • LL/SC
  • CAS

Metrics

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

Related Versions

References

  1. Zahra Aghazadeh, Wojciech Golab, and Philipp Woelfel. Making objects writable. In Proceedings of the 2014 ACM Symposium on Principles of Distributed Computing, PODC ’14, pages 385-395, New York, NY, USA, 2014. Association for Computing Machinery. URL: https://doi.org/10.1145/2611462.2611483.
  2. Marcos K. Aguilera and Svend Frølund. Strict linearizability and the power of aborting. In techreport, 2003. Google Scholar
  3. James H. Anderson and Mark Moir. Universal constructions for multi-object operations. In Proceedings of the Fourteenth Annual ACM Symposium on Principles of Distributed Computing, PODC '95, pages 184-193, New York, NY, USA, 1995. Association for Computing Machinery. URL: https://doi.org/10.1145/224964.224985.
  4. Hagit Attiya, Ohad Ben-Baruch, Panagiota Fatourou, Danny Hendler, and Eleftherios Kosmas. Detectable recovery of lock-free data structures. In Proceedings of the 27th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP '22, pages 262-277, New York, NY, USA, 2022. Association for Computing Machinery. URL: https://doi.org/10.1145/3503221.3508444.
  5. Hagit Attiya, Ohad Ben-Baruch, and Danny Hendler. Nesting-safe recoverable linearizability: Modular constructions for non-volatile memory. In Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, PODC ’18, pages 7-16, New York, NY, USA, 2018. Association for Computing Machinery. URL: https://doi.org/10.1145/3212734.3212753.
  6. Ohad Ben-Baruch, Danny Hendler, and Matan Rusanovsky. Upper and lower bounds on the space complexity of detectable objects. In Proceedings of the 39th Symposium on Principles of Distributed Computing, PODC '20, pages 11-20, New York, NY, USA, 2020. Association for Computing Machinery. URL: https://doi.org/10.1145/3382734.3405725.
  7. Naama Ben-David, Guy E. Blelloch, Michal Friedman, and Yuanhao Wei. Delay-free concurrency on faulty persistent memory. In The 31st ACM Symposium on Parallelism in Algorithms and Architectures, SPAA ’19, pages 253-264, New York, NY, USA, 2019. Association for Computing Machinery. URL: https://doi.org/10.1145/3323165.3323187.
  8. Naama Ben-David, Michal Friedman, and Yuanhao Wei. Brief announcement: Survey of persistent memory correctness conditions. In Christian Scheideler, editor, 36th International Symposium on Distributed Computing, DISC 2022, October 25-27, 2022, Augusta, Georgia, USA, volume 246 of LIPIcs, pages 41:1-41:4. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. URL: https://doi.org/10.4230/LIPIcs.DISC.2022.41.
  9. Ryan Berryhill, Wojciech M. Golab, and Mahesh Tripunitara. Robust shared objects for non-volatile main memory. In Emmanuelle Anceaume, Christian Cachin, and Maria Gradinariu Potop-Butucaru, editors, 19th International Conference on Principles of Distributed Systems, OPODIS 2015, December 14-17, 2015, Rennes, France, volume 46 of LIPIcs, pages 20:1-20:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015. URL: https://doi.org/10.4230/LIPIcs.OPODIS.2015.20.
  10. Guy E. Blelloch, Phillip B. Gibbons, Yan Gu, Charles McGuffey, and Julian Shun. The parallel persistent memory model. In Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures, SPAA '18, pages 247-258, New York, NY, USA, 2018. Association for Computing Machinery. URL: https://doi.org/10.1145/3210377.3210381.
  11. Guy E. Blelloch and Yuanhao Wei. LL/SC and atomic copy: Constant time, space efficient implementations using only pointer-width CAS. In Hagit Attiya, editor, 34th International Symposium on Distributed Computing, DISC 2020, October 12-16, 2020, Virtual Conference, volume 179 of LIPIcs, pages 5:1-5:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.DISC.2020.5.
  12. Philip Bohannon, Daniel Lieuwen, Avi Silberschatz, S. Sudarshan, and Jacques Gava. Recoverable User-Level Mutual Exclusion. In In Proc. 7th IEEE Symposium on Parallel and Distributed Processing, 1995. Google Scholar
  13. Wentao Cai, Haosen Wen, H. Alan Beadle, Chris Kjellqvist, Mohammad Hedayati, and Michael L. Scott. Understanding and optimizing persistent memory allocation. In Proceedings of the 2020 ACM SIGPLAN International Symposium on Memory Management, ISMM 2020, pages 60-73, New York, NY, USA, 2020. Association for Computing Machinery. URL: https://doi.org/10.1145/3381898.3397212.
  14. David Yu Cheng Chan and Philipp Woelfel. Recoverable mutual exclusion with constant amortized RMR complexity from standard primitives. In ACM Symposium on Principles of Distributed Computing (PODC). ACM, 2020. URL: https://doi.org/10.1145/3382734.3405736.
  15. David Yu Cheng Chan and Philipp Woelfel. Tight lower bound for the RMR complexity of recoverable mutual exclusion. In ACM Symposium on Principles of Distributed Computing (PODC). ACM, 2021. URL: https://doi.org/10.1145/3465084.3467938.
  16. D. Dechev, P. Pirkelbauer, and B. Stroustrup. Understanding and effectively preventing the aba problem in descriptor-based lock-free designs. In 2010 13th IEEE International Symposium on Object/Component/Service-Oriented Real-Time Distributed Computing, pages 185-192, 2010. URL: https://doi.org/10.1109/ISORC.2010.10.
  17. Sahil Dhoked and Neeraj Mittal. An adaptive approach to recoverable mutual exclusion. In PODC '20: ACM Symposium on Principles of Distributed Computing, Virtual Event, Italy, August 3-7, 2020. ACM, 2020. URL: https://doi.org/10.1145/3382734.3405739.
  18. Simon Doherty, Maurice Herlihy, Victor Luchangco, and Mark Moir. Bringing practical lock-free synchronization to 64-bit applications. In Soma Chaudhuri and Shay Kutten, editors, Proceedings of the Twenty-Third Annual ACM Symposium on Principles of Distributed Computing, PODC 2004, St. John’s, Newfoundland, Canada, July 25-28, 2004, pages 31-39. ACM, 2004. URL: https://doi.org/10.1145/1011767.1011773.
  19. Michal Friedman, Maurice Herlihy, Virendra J. Marathe, and Erez Petrank. A persistent lock-free queue for non-volatile memory. In Andreas Krall and Thomas R. Gross, editors, Proceedings of the 23rd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP 2018, Vienna, Austria, February 24-28, 2018, pages 28-40. ACM, 2018. URL: https://doi.org/10.1145/3178487.3178490.
  20. Wojciech M. Golab and Danny Hendler. Recoverable mutual exclusion in sub-logarithmic time. In Elad Michael Schiller and Alexander A. Schwarzmann, editors, Proceedings of the ACM Symposium on Principles of Distributed Computing, PODC 2017, Washington, DC, USA, July 25-27, 2017, pages 211-220. ACM, 2017. URL: https://doi.org/10.1145/3087801.3087819.
  21. Wojciech M. Golab and Aditya Ramaraju. Recoverable mutual exclusion: [extended abstract]. In George Giakkoupis, editor, Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, PODC 2016, Chicago, IL, USA, July 25-28, 2016, pages 65-74. ACM, 2016. URL: https://doi.org/10.1145/2933057.2933087.
  22. Rachid Guerraoui, Alex Kogan, Virendra J. Marathe, and Igor Zablotchi. Efficient multi-word compare and swap. In Hagit Attiya, editor, 34th International Symposium on Distributed Computing, DISC 2020, October 12-16, 2020, Virtual Conference, volume 179 of LIPIcs, pages 4:1-4:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.DISC.2020.4.
  23. Rachid Guerraoui and Ron R. Levy. Robust emulations of shared memory in a crash-recovery model. In Proceedings of the 24th International Conference on Distributed Computing Systems (ICDCS'04), ICDCS '04, pages 400-407, USA, 2004. IEEE Computer Society. Google Scholar
  24. happyware.com. Supermicro 8-socket intel xeon 7u rack server. https://happyware.com/uk-en/supermicro/sys-7089p-tr4t. Accessed: August 1, 2022.
  25. Maurice Herlihy. Wait-free synchronization. ACM Trans. Program. Lang. Syst., 13(1):124-149, 1991. URL: https://doi.org/10.1145/114005.102808.
  26. Maurice P. Herlihy and Jeannette M. Wing. Linearizability: A correctness condition for concurrent objects. ACM Trans. Program. Lang. Syst., 12(3):463-492, July 1990. URL: https://doi.org/10.1145/78969.78972.
  27. Intel. Intel optane technology, 2020. URL: https://software.intel.com/content/www/us/en/develop/articles/intel-sdm.html.
  28. Joseph Izraelevitz, Hammurabi Mendes, and Michael L. Scott. Linearizability of persistent memory objects under a full-system-crash failure model. In Cyril Gavoille and David Ilcinkas, editors, Distributed Computing - 30th International Symposium, DISC 2016, Paris, France, September 27-29, 2016. Proceedings, volume 9888 of Lecture Notes in Computer Science, pages 313-327. Springer, 2016. URL: https://doi.org/10.1007/978-3-662-53426-7_23.
  29. Prasad Jayanti. A complete and constant time wait-free implementation of cas from ll/sc and vice versa. In Proceedings of the 12th International Symposium on Distributed Computing, DISC ’98, pages 216-230, Berlin, Heidelberg, 1998. Springer-Verlag. Google Scholar
  30. Prasad Jayanti, Siddhartha Jayanti, and Sucharita Jayanti. Durable algorithms for writable ll/sc and cas with dynamic joining, 2023. URL: https://arxiv.org/abs/2302.00135.
  31. Prasad Jayanti, Siddhartha Jayanti, and Anup Joshi. A recoverable mutex algorithm with sub-logarithmic rmr on both cc and dsm. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC ’19, pages 177-186, New York, NY, USA, 2019. Association for Computing Machinery. URL: https://doi.org/10.1145/3293611.3331634.
  32. Prasad Jayanti, Siddhartha Jayanti, and Anup Joshi. Constant rmr system-wide failure resilient durable locks with dynamic joining. In Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA '23, pages 227-237, New York, NY, USA, 2023. Association for Computing Machinery. URL: https://doi.org/10.1145/3558481.3591100.
  33. Prasad Jayanti, Siddhartha V. Jayanti, and Anup Joshi. Optimal recoverable mutual exclusion using only FASAS. In Andreas Podelski and François Taïani, editors, Networked Systems - 6th International Conference, NETYS 2018, Essaouira, Morocco, May 9-11, 2018, Revised Selected Papers, volume 11028 of Lecture Notes in Computer Science, pages 191-206. Springer, 2018. URL: https://doi.org/10.1007/978-3-030-05529-5_13.
  34. Prasad Jayanti, Siddhartha Visveswara Jayanti, and Sucharita Jayanti. Brief announcement: Efficient recoverable writable-cas. In Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing, PODC '23, pages 366-369, New York, NY, USA, 2023. Association for Computing Machinery. URL: https://doi.org/10.1145/3583668.3594592.
  35. Prasad Jayanti and Anup Joshi. Recoverable FCFS mutual exclusion with wait-free recovery. In Andréa W. Richa, editor, 31st International Symposium on Distributed Computing, DISC 2017, October 16-20, 2017, Vienna, Austria, volume 91 of LIPIcs, pages 30:1-30:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. URL: https://doi.org/10.4230/LIPIcs.DISC.2017.30.
  36. Prasad Jayanti and Anup Joshi. Recoverable mutual exclusion with abortability. In Mohamed Faouzi Atig and Alexander A. Schwarzmann, editors, Networked Systems - 7th International Conference, NETYS 2019, Marrakech, Morocco, June 19-21, 2019, Revised Selected Papers, volume 11704 of Lecture Notes in Computer Science, pages 217-232. Springer, 2019. URL: https://doi.org/10.1007/978-3-030-31277-0_14.
  37. Prasad Jayanti and Srdjan Petrovic. Efficient and practical constructions of ll/sc variables. In Proceedings of the Twenty-Second Annual Symposium on Principles of Distributed Computing, PODC '03, pages 285-294, New York, NY, USA, 2003. Association for Computing Machinery. URL: https://doi.org/10.1145/872035.872078.
  38. Prasad Jayanti and Srdjan Petrovic. Efficiently implementing LL/SC objects shared by an unknown number of processes. In Ajit Pal, Ajay D. Kshemkalyani, Rajeev Kumar, and Arobinda Gupta, editors, Distributed Computing - IWDC 2005, 7th International Workshop, Kharagpur, India, December 27-30, 2005, Proceedings, volume 3741 of Lecture Notes in Computer Science, pages 45-56. Springer, 2005. URL: https://doi.org/10.1007/11603771_5.
  39. Nan Li and Wojciech M. Golab. Detectable sequential specifications for recoverable shared objects. In Seth Gilbert, editor, 35th International Symposium on Distributed Computing, DISC 2021, October 4-8, 2021, Freiburg, Germany (Virtual Conference), volume 209 of LIPIcs, pages 29:1-29:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. URL: https://doi.org/10.4230/LIPIcs.DISC.2021.29.
  40. Maged M. Michael. Practical lock-free and wait-free LL/SC/VL implementations using 64-bit CAS. In Rachid Guerraoui, editor, Distributed Computing, 18th International Conference, DISC 2004, Amsterdam, The Netherlands, October 4-7, 2004, Proceedings, volume 3274 of Lecture Notes in Computer Science, pages 144-158. Springer, 2004. URL: https://doi.org/10.1007/978-3-540-30186-8_11.
  41. Aditya Ramaraju. RGLock: Recoverable mutual exclusion for non-volatile main memory systems. Master’s thesis, University of Waterloo, 2015. URL: https://uwspace.uwaterloo.ca/handle/10012/9473.
  42. Tianzheng Wang, Justin J. Levandoski, and Per-Åke Larson. Easy lock-free indexing in non-volatile memory. In 34th IEEE International Conference on Data Engineering, ICDE 2018, Paris, France, April 16-19, 2018, pages 461-472. IEEE Computer Society, 2018. URL: https://doi.org/10.1109/ICDE.2018.00049.
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