{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,2]],"date-time":"2025-08-02T18:46:33Z","timestamp":1754160393284,"version":"3.41.2"},"reference-count":41,"publisher":"Association for Computing Machinery (ACM)","issue":"4","funder":[{"name":"National Science Foundation","award":["CNS-1619197"],"award-info":[{"award-number":["CNS-1619197"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2025,8,31]]},"abstract":"<jats:p>\n            Mutual exclusion is one of the most commonly used techniques to handle contention in concurrent systems. Traditionally, mutual exclusion algorithms have been designed under the assumption that a process does not fail while acquiring\/releasing a lock or while executing its critical section. However, failures do occur in real life, potentially leaving the lock in an inconsistent state. This gives rise to the problem of\n            <jats:italic toggle=\"yes\">recoverable mutual exclusion (RME)<\/jats:italic>\n            , which involves designing a mutual exclusion (ME) algorithm that can tolerate failures while maintaining required safety and liveness properties.\n          <\/jats:p>\n          <jats:p>\n            In this work, we present a framework that transforms any algorithm that solves the RME problem into an algorithm that can also simultaneously\n            <jats:italic toggle=\"yes\">adapt<\/jats:italic>\n            to (i) the number of processes concurrently competing for the lock,\n            <jats:italic toggle=\"yes\">as well as<\/jats:italic>\n            (ii) the number of unresolved failures in the system, while maintaining the correctness properties and performance characteristics of the underlying RME algorithm. Additionally, the algorithm constructed as a result of this transformation adds certain desirable properties such as bounded recovery and fairness.\n          <\/jats:p>\n          <jats:p>\n            One of the important performance measures of any ME algorithm, including an RME algorithm, is the number of\n            <jats:italic toggle=\"yes\">remote memory references (RMRs)<\/jats:italic>\n            made by a process\u2014to acquire and release a lock, as well as to recover the lock structure after a failure. Let\n            <jats:italic toggle=\"yes\">R(n)<\/jats:italic>\n            denote the RMR complexity of a critical section request in the underlying RME algorithm, where\n            <jats:italic toggle=\"yes\">n<\/jats:italic>\n            denotes the number of processes in the system. Then, our framework yields an RME algorithm for which the RMR complexity of a critical section request is given by\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\mathcal {O}(\\min \\lbrace \\ddot{c},\\sqrt {F+1},\\ R(n) \\rbrace)\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            , where\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\ddot{c}\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            denotes the\n            <jats:italic toggle=\"yes\">point contention<\/jats:italic>\n            of the request and\n            <jats:italic toggle=\"yes\">F<\/jats:italic>\n            denotes the\n            <jats:italic toggle=\"yes\">failure-density<\/jats:italic>\n            of the request.\n          <\/jats:p>\n          <jats:p>We further extend our framework by presenting a novel memory reclamation algorithm to bound the space complexity of the RME algorithm. Our memory reclamation algorithm maintains the correctness, performance, and fairness properties of our transformation. Our approach is general enough that it may also be used to bound the space complexity of other RME algorithms.<\/jats:p>\n          <jats:p>\n            In addition to read and write instructions, our algorithm uses compare-and-swap (\n            <jats:sans-serif>CAS<\/jats:sans-serif>\n            ) and fetch-and-store (\n            <jats:sans-serif>FAS<\/jats:sans-serif>\n            ) hardware instructions, both of which are commonly available in most modern processors.\n          <\/jats:p>","DOI":"10.1145\/3744236","type":"journal-article","created":{"date-parts":[[2025,6,11]],"date-time":"2025-06-11T07:04:52Z","timestamp":1749625492000},"page":"1-61","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Adaptive and Fair Transformation for Recoverable Mutual Exclusion"],"prefix":"10.1145","volume":"72","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2893-377X","authenticated-orcid":false,"given":"Sahil","family":"Dhoked","sequence":"first","affiliation":[{"name":"Computer Science, The University of Texas at Dallas","place":["Richardson, United States"]}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8734-1400","authenticated-orcid":false,"given":"Neeraj","family":"Mittal","sequence":"additional","affiliation":[{"name":"Computer Science, The University of Texas at Dallas","place":["Richardson, United States"]}]}],"member":"320","published-online":{"date-parts":[[2025,7,26]]},"reference":[{"key":"e_1_3_3_2_2","volume-title":"AMD64 Architecture Programmer\u2019s Manual Volume 3: General Purpose and System Instructions","author":"AMD","year":"2024","unstructured":"AMD 2024. AMD64 Architecture Programmer\u2019s Manual Volume 3: General Purpose and System Instructions. AMD. Retrieved from https:\/\/www.amd.com\/content\/dam\/amd\/en\/documents\/processor-tech-docs\/programmer-references\/24594.pdf"},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-002-0084-2"},{"key":"e_1_3_3_4_2","first-page":"297","volume-title":"Proceedings of the USENIX Annual Technical Conference, FREENIX Track","author":"Arcangeli Andrea","year":"2003","unstructured":"Andrea Arcangeli, Mingming Cao, Paul E. McKenney, and Dipankar Sarma. 2003. Using read-copy-update techniques for system V IPC in the Linux 2.5 kernel. In Proceedings of the USENIX Annual Technical Conference, FREENIX Track. USENIX Association, San Antonio, Texas, USA, 297\u2013309. Retrieved from https:\/\/www.usenix.org\/legacy\/events\/usenix03\/tech\/freenix03\/arcangeli.html"},{"key":"e_1_3_3_5_2","first-page":"217","volume-title":"Proceedings of the 40th Annual ACM Symposium on Theory of Computing (STOC\u201908)","author":"Attiya Hagit","year":"2008","unstructured":"Hagit Attiya, Danny Hendler, and Philipp Woelfel. 2008. Tight RMR lower bounds for mutual exclusion and other problems. In Proceedings of the 40th Annual ACM Symposium on Theory of Computing (STOC\u201908). ACM, 217\u2013226. DOI:DOI:10.1145\/1374376.1374410"},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/1835698.1835803"},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","DOI":"10.5555\/829517.830751"},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.5555\/829516.830651"},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2008.12.002"},{"key":"e_1_3_3_10_2","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1145\/3382734.3405736","volume-title":"Proceedings of the 39th ACM Symposium on Principles of Distributed Computing (PODC\u201920)","author":"Chan David Yu Cheng","year":"2020","unstructured":"David Yu Cheng Chan and Philipp Woelfel. 2020. Recoverable mutual exclusion with constant amortized RMR complexity from standard primitives. In Proceedings of the 39th ACM Symposium on Principles of Distributed Computing (PODC\u201920). ACM, 181\u2013190. DOI:DOI:10.1145\/3382734.3405736"},{"key":"e_1_3_3_11_2","doi-asserted-by":"crossref","first-page":"533","DOI":"10.1145\/3465084.3467938","volume-title":"Proceedings of the 40th ACM Symposium on Principles of Distributed Computing (PODC\u201921)","author":"Chan David Yu Cheng","year":"2021","unstructured":"David Yu Cheng Chan and Philipp Woelfel. 2021. Tight lower bound for the RMR complexity of recoverable mutual exclusion. In Proceedings of the 40th ACM Symposium on Principles of Distributed Computing (PODC\u201921). ACM, 533\u2013543. DOI:DOI:10.1145\/3465084.3467938"},{"key":"e_1_3_3_12_2","volume-title":"Synchronization and Fault Tolerance Techniques in Concurrent Shared Memory Systems","author":"Dhoked Sahil","year":"2022","unstructured":"Sahil Dhoked. 2022. Synchronization and Fault Tolerance Techniques in Concurrent Shared Memory Systems. Ph.D. Dissertation. Department of Computer Science, The University of Texas at Dallas. Retrieved from https:\/\/utd-ir.tdl.org\/items\/9b493b52-5bd7-45f0-9a4c-80d0835dc96e"},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/3558481.3591317"},{"key":"e_1_3_3_14_2","first-page":"17:1\u201317:24","volume-title":"Proceedings of the 37th Symposium on Distributed Computing (DISC\u201923)","author":"Dhoked Sahil","year":"2023","unstructured":"Sahil Dhoked, Wojciech Golab, and Neeraj Mittal. 2023. Modular recoverable mutual exclusion under system-wide failures. In Proceedings of the 37th Symposium on Distributed Computing (DISC\u201923). Dagstuhl Publishing, L\u2019aquila, Italy, 17:1\u201317:24. DOI:DOI:10.4230\/LIPIcs.DISC.2023.17"},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-20002-1"},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/365559.365617"},{"key":"e_1_3_3_17_2","first-page":"17:1\u201317:16","volume-title":"Proceedings of the 21st International Conference on Principles of Distributed Systems (OPODIS\u201917)","author":"Dvir Rotem","year":"2017","unstructured":"Rotem Dvir and Gadi Taubenfeld. 2017. Mutual exclusion algorithms with constant RMR complexity and wait-free exit code. In Proceedings of the 21st International Conference on Principles of Distributed Systems (OPODIS\u201917). Dagstuhl Publishing, Lisbon, Portugal, 17:1\u201317:16. DOI:DOI:10.4230\/LIPIcs.OPODIS.2017.17"},{"key":"e_1_3_3_18_2","unstructured":"U.S.-Canada Power System Outage Task Force. 2004. Final Report on the August 14 2003 Blackout in the United States and Canada: Causes and Recommendations. (April2004). Retrieved from https:\/\/www3.epa.gov\/region1\/npdes\/merrimackstation\/pdfs\/ar\/AR-1165.pdf"},{"key":"e_1_3_3_19_2","volume-title":"Practical Lock-Freedom","author":"Fraser Keir","year":"2003","unstructured":"Keir Fraser. 2003. Practical Lock-Freedom. Ph.D. Dissertation. King\u2019s College, University of Cambridge. Available as technical report #579 at https:\/\/www.cl.cam.ac.uk\/techreports\/UCAM-CL-TR-579.pdf"},{"key":"e_1_3_3_20_2","first-page":"446","volume-title":"Proceedings of the 26th ACM Symposium on Principles and Practice of Parallel Programming (PPoPP\u201921)","author":"Gokhale Shreyas","year":"2021","unstructured":"Shreyas Gokhale, Sahil Dhoked, and Neeraj Mittal. 2021. On group mutual exclusion for dynamic systems. In Proceedings of the 26th ACM Symposium on Principles and Practice of Parallel Programming (PPoPP\u201921). ACM, 446\u2013447. DOI:DOI:10.1145\/3437801.3441608"},{"key":"e_1_3_3_21_2","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1145\/3087801.3087819","volume-title":"Proceedings of the 36th ACM Symposium on Principles of Distributed Computing (PODC\u201917)","author":"Golab Wojciech","year":"2017","unstructured":"Wojciech Golab and Danny Hendler. 2017. Recoverable mutual exclusion in sub-logarithmic time. In Proceedings of the 36th ACM Symposium on Principles of Distributed Computing (PODC\u201917). ACM, 211\u2013220. DOI:DOI:10.1145\/3087801.3087819"},{"key":"e_1_3_3_22_2","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1145\/3212734.3212755","volume-title":"Proceedings of the 37th ACM Symposium on Principles of Distributed Computing (PODC\u201918)","author":"Golab Wojciech","year":"2018","unstructured":"Wojciech Golab and Danny Hendler. 2018. Recoverable mutual exclusion under system-wide failures. In Proceedings of the 37th ACM Symposium on Principles of Distributed Computing (PODC\u201918). ACM, 17\u201326. DOI:DOI:10.1145\/3212734.3212755"},{"key":"e_1_3_3_23_2","first-page":"238","volume-title":"Proceedings of the 25th ACM Symposium on Principles of Distributed Computing (PODC\u201906)","author":"Golab Wojciech","year":"2006","unstructured":"Wojciech Golab, Danny Hendler, and Philipp Woelfel. 2006. An \\(O(1)\\) RMRs leader election algorithm. In Proceedings of the 25th ACM Symposium on Principles of Distributed Computing (PODC\u201906). ACM, 238\u2013247. DOI:DOI:10.1145\/1146381.1146417"},{"key":"e_1_3_3_24_2","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1145\/2933057.2933087","volume-title":"Proceedings of the 35th ACM Symposium on Principles of Distributed Computing (PODC\u201916)","author":"Golab Wojciech","year":"2016","unstructured":"Wojciech Golab and Aditya Ramaraju. 2016. Recoverable mutual exclusion: [Extended Abstract]. In Proceedings of the 35th ACM Symposium on Principles of Distributed Computing (PODC\u201916). ACM, 65\u201374. DOI:DOI:10.1145\/2933057.2933087"},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-019-00364-0"},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2007.04.010"},{"key":"e_1_3_3_27_2","first-page":"22:1\u201322:10","volume-title":"Proceedings of the 17th International Conference on Distributed Computing and Networking (ICDCN\u201916)","author":"He Yuan","year":"2016","unstructured":"Yuan He, Krishnan Gopalakrishnan, and Eli Gafni. 2016. Group mutual exclusion in linear time and space. In Proceedings of the 17th International Conference on Distributed Computing and Networking (ICDCN\u201916). ACM, 22:1\u201322:10. DOI:DOI:10.1145\/2833312.2833316"},{"key":"e_1_3_3_28_2","doi-asserted-by":"publisher","DOI":"10.5555\/2385452"},{"key":"e_1_3_3_29_2","volume-title":"Intel 64 and IA-32 Architectures Software Developer Manual","author":"Intel","year":"2024","unstructured":"Intel 2024. Intel 64 and IA-32 Architectures Software Developer Manual. Intel. Retrieved from https:\/\/www.intel.com\/content\/www\/us\/en\/developer\/articles\/technical\/intel-sdm.html"},{"key":"e_1_3_3_30_2","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1145\/3293611.3331634","volume-title":"Proceedings of the 37th ACM Symposium on Principles of Distributed Computing (PODC\u201919)","author":"Jayanti Prasad","year":"2019","unstructured":"Prasad Jayanti, Siddhartha Jayanti, and Anup Joshi. 2019. A recoverable mutex algorithm with sub-logarithmic RMR on both CC and DSM. In Proceedings of the 37th ACM Symposium on Principles of Distributed Computing (PODC\u201919). ACM, 177\u2013186. DOI:DOI:10.1145\/3293611.3331634"},{"key":"e_1_3_3_31_2","first-page":"227","volume-title":"Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA\u201923)","author":"Jayanti Prasad","year":"2023","unstructured":"Prasad Jayanti, Siddhartha Jayanti, and Anup Joshi. 2023. 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\u201923). ACM, 227\u2013237. DOI:DOI:10.1145\/3558481.3591100"},{"key":"e_1_3_3_32_2","first-page":"30:1\u201330:15","volume-title":"Proceedings of the 31st Symposium on Distributed Computing (DISC\u201917)","author":"Jayanti Prasad","year":"2017","unstructured":"Prasad Jayanti and Anup Joshi. 2017. Recoverable FCFS mutual exclusion with wait-free recovery. In Proceedings of the 31st Symposium on Distributed Computing (DISC\u201917). Dagstuhl Publishing, Vienna, Austria, 30:1\u201330:15. DOI:DOI:10.4230\/LIPIcs.DISC.2017.30"},{"key":"e_1_3_3_33_2","first-page":"217","volume-title":"Proceedings of the 7th International Conference on Networked Systems (NETYS\u201919)","author":"Jayanti Prasad","year":"2019","unstructured":"Prasad Jayanti and Anup Joshi. 2019. Recoverable mutual exclusion with abortability. In Proceedings of the 7th International Conference on Networked Systems (NETYS\u201919). Springer Cham, Marrakech, Morocco, 217\u2013232. DOI:DOI:10.1007\/978-3-030-31277-0_14"},{"key":"e_1_3_3_34_2","first-page":"777","volume-title":"Proceedings of the 8th IEEE\/ACM International Symposium on Cluster, Cloud and Internet Computing (CCGrid\u201908)","author":"Kandaswamy Gopi","year":"2008","unstructured":"Gopi Kandaswamy, Anirban Mandal, and Daniel A. Reed. 2008. Fault tolerance and recovery of scientific workflows on computational grid. In Proceedings of the 8th IEEE\/ACM International Symposium on Cluster, Cloud and Internet Computing (CCGrid\u201908). IEEE Computer Society, Lyon, France, 777\u2013782. DOI:DOI:10.1109\/CCGRID.2008.79"},{"key":"e_1_3_3_35_2","first-page":"15:1\u201315:16","volume-title":"Proceedings of the 24th International Conference on Principles of Distributed Systems (OPODIS\u201921)","author":"Katzan Daniel","year":"2021","unstructured":"Daniel Katzan and Adam Morrison. 2021. Recoverable, abortable, and adaptive mutual exclusion with sublogarithmic RMR complexity. In Proceedings of the 24th International Conference on Principles of Distributed Systems (OPODIS\u201921). Dagstuhl Publishing, Strasbourg, France (Virtual Conference), 15:1\u201315:16. DOI:DOI:10.4230\/LIPIcs.OPODIS.2020.15"},{"key":"e_1_3_3_36_2","doi-asserted-by":"publisher","DOI":"10.1109\/MC.1993.274940"},{"key":"e_1_3_3_37_2","doi-asserted-by":"publisher","DOI":"10.1145\/103727.103729"},{"key":"e_1_3_3_38_2","first-page":"401","volume-title":"Proceedings of the 17th International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS\u201912)","author":"Narayanan Dushyanth","year":"2012","unstructured":"Dushyanth Narayanan and Orion Hodson. 2012. Whole-system persistence. In Proceedings of the 17th International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS\u201912). ACM, 401\u2013410. DOI:DOI:10.1145\/2150976.2151018"},{"key":"e_1_3_3_39_2","volume-title":"RGLock: Recoverable Mutual Exclusion for Non-Volatile Main Memory Systems","author":"Ramaraju Aditya","year":"2015","unstructured":"Aditya Ramaraju. 2015. RGLock: Recoverable Mutual Exclusion for Non-Volatile Main Memory Systems. Ph.D. Dissertation. Electrical and Computer Engineering Department, University of Waterloo. Retrieved from http:\/\/hdl.handle.net\/10012\/9473"},{"key":"e_1_3_3_40_2","doi-asserted-by":"publisher","DOI":"10.1145\/1288783.1288785"},{"key":"e_1_3_3_41_2","first-page":"31","volume-title":"Proceedings of the 10th International Conference on Networked Systems (NETYS\u201922)","author":"Segu Aravind","year":"2022","unstructured":"Aravind Segu and Wojciech Golab. 2022. Recycling memory in recoverable mutex locks. In Proceedings of the 10th International Conference on Networked Systems (NETYS\u201922). Dagstuhl Publishing, Virtual Event, 31\u201336. DOI:DOI:10.1007\/978-3-031-17436-0_3"},{"key":"e_1_3_3_42_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01784242"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3744236","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,26]],"date-time":"2025-07-26T14:06:42Z","timestamp":1753538802000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3744236"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,7,26]]},"references-count":41,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2025,8,31]]}},"alternative-id":["10.1145\/3744236"],"URL":"https:\/\/doi.org\/10.1145\/3744236","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2025,7,26]]},"assertion":[{"value":"2021-09-22","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-01-27","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-07-26","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}