{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,6]],"date-time":"2025-11-06T13:22:08Z","timestamp":1762435328241,"version":"build-2065373602"},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"4","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Syst."],"published-print":{"date-parts":[[2025,11,30]]},"abstract":"<jats:p>\n                    The problem of deadlock detection and resolution in database systems has been studied for decades. Although it has long been a mature feature of classical centralized database systems for many years, its use in distributed database systems remains in its infancy. A simple and fully distributed deadlock detection and resolution algorithm was proposed by Don P. Mitchell and Michael J. Merritt (\n                    <jats:italic toggle=\"yes\">M&amp;M<\/jats:italic>\n                    ), but its assumption that each process waits for only one resource at a time prevents it from being generally applicable. The distributed deadlock detection algorithm based on Lock Chain Length (LCL) surpasses the limitations of the\n                    <jats:italic toggle=\"yes\">M&amp;M<\/jats:italic>\n                    algorithm. However, it is less effective in quickly detecting deadlocks that encompass both distributed and local deadlocks. In this article, we introduce\n                    <jats:italic toggle=\"yes\">\n                      LCL\n                      <jats:sup>+<\/jats:sup>\n                    <\/jats:italic>\n                    , an advanced and universally applicable algorithm specifically designed for the detection and resolution of resource deadlocks in distributed environments. This algorithm improves the efficiency of identifying distributed deadlocks by accelerating the detection of hybrid deadlocks. Our extensive experiments demonstrate that\n                    <jats:italic toggle=\"yes\">\n                      LCL\n                      <jats:sup>+<\/jats:sup>\n                    <\/jats:italic>\n                    significantly outperforms its predecessor, LCL, in efficiency. In addition, it has been successfully implemented in the OceanBase distributed relational database system. Detailed analyses from multiple perspectives within OceanBase confirm that\n                    <jats:italic toggle=\"yes\">\n                      LCL\n                      <jats:sup>+<\/jats:sup>\n                    <\/jats:italic>\n                    significantly improves the system\u2019s scalability and ensures the provision of high-quality service.\n                  <\/jats:p>","DOI":"10.1145\/3768621","type":"journal-article","created":{"date-parts":[[2025,10,3]],"date-time":"2025-10-03T10:58:22Z","timestamp":1759489102000},"page":"1-33","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["LCL+: a Lock Chain Length-based Distributed Deadlock Detection and Resolution Service Built for OceanBase"],"prefix":"10.1145","volume":"43","author":[{"ORCID":"https:\/\/orcid.org\/0009-0009-9993-4244","authenticated-orcid":false,"given":"Zhenkun","family":"Yang","sequence":"first","affiliation":[{"name":"OceanBase, Ant Group CO Ltd","place":["Beijing, China"]}]},{"ORCID":"https:\/\/orcid.org\/0009-0002-7303-8950","authenticated-orcid":false,"given":"Chen","family":"Qian","sequence":"additional","affiliation":[{"name":"OceanBase, Ant Group CO Ltd","place":["Beijing, China"]}]},{"ORCID":"https:\/\/orcid.org\/0009-0000-2754-0478","authenticated-orcid":false,"given":"Xuwang","family":"Teng","sequence":"additional","affiliation":[{"name":"OceanBase, Ant Group CO Ltd","place":["Beijing, China"]}]},{"ORCID":"https:\/\/orcid.org\/0009-0002-8911-8533","authenticated-orcid":false,"given":"Fanyu","family":"Kong","sequence":"additional","affiliation":[{"name":"OceanBase, Ant Group CO Ltd","place":["Beijing, China"]}]},{"ORCID":"https:\/\/orcid.org\/0009-0000-2900-0109","authenticated-orcid":false,"given":"Fusheng","family":"Han","sequence":"additional","affiliation":[{"name":"OceanBase, Ant Group CO Ltd","place":["Beijing, China"]}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8989-9662","authenticated-orcid":false,"given":"Quanqing","family":"Xu","sequence":"additional","affiliation":[{"name":"OceanBase, Ant Group CO Ltd","place":["Hangzhou, China"]}]},{"ORCID":"https:\/\/orcid.org\/0009-0002-5538-0517","authenticated-orcid":false,"given":"Daokun","family":"Hu","sequence":"additional","affiliation":[{"name":"OceanBase, Ant Group CO Ltd","place":["Hangzhou, China"]}]}],"member":"320","published-online":{"date-parts":[[2025,11,6]]},"reference":[{"key":"e_1_3_1_2_2","unstructured":"MulanPubL. 2025. MulanPubL-2.0. Retrieved June 30 2025 from https:\/\/license.coscl.org.cn\/MulanPubL-2.0"},{"key":"e_1_3_1_3_2","unstructured":"TPC. 2025. TPC-C Result Highlights. Retrieved June 30 2025 from http:\/\/tpc.org\/1803"},{"key":"e_1_3_1_4_2","unstructured":"TPC. 2025. TPC-H V3 Result Highlights. Retrieved June 30 2025 from http:\/\/tpc.org\/3375"},{"key":"e_1_3_1_5_2","unstructured":"MySQL. 2025. MySQL\u2019s Lock Waiting Timeout. Retrieved June 30 2025 from https:\/\/dev.mysql.com\/doc\/refman\/8.0\/en\/innodb_parameters.html#sysvar_innodb_lock_wait_timeout"},{"key":"e_1_3_1_6_2","unstructured":"OceanBase. 2025. OceanBase. Retrieved June 30 2025 from https:\/\/gitee.com\/oceanbase"},{"key":"e_1_3_1_7_2","unstructured":"OceanBase. 2025. OceanBase. Retrieved June 30 2025 from https:\/\/github.com\/oceanbase"},{"key":"e_1_3_1_8_2","unstructured":"PingCAP. 2025. TiDB\u2019s Lock Waiting Timeout. Retrieved June 30 2025 from https:\/\/docs-archive.pingcap.com\/tidb\/v7.6\/system-variables\/#innodb_lock_wait_timeout"},{"key":"e_1_3_1_9_2","doi-asserted-by":"crossref","first-page":"331","DOI":"10.1145\/3035918.3056103","volume-title":"Proceedings of the 2017 ACM International Conference on Management of Data","author":"Bacon David F.","year":"2017","unstructured":"David F. Bacon, Nathan Bales, Nico Bruno, Brian F. Cooper, Adam Dickinson, Andrew Fikes, Campbell Fraser, Andrey Gubarev, Milind Joshi, Eugene Kogan, et\u00a0al. 2017. Spanner: Becoming a SQL system. In Proceedings of the 2017 ACM International Conference on Management of Data. 331\u2013343."},{"key":"e_1_3_1_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/800220.806696"},{"key":"e_1_3_1_11_2","doi-asserted-by":"crossref","first-page":"538","DOI":"10.1145\/2851613.2851880","volume-title":"Proceedings of the 31st Annual ACM Symposium on Applied Computing","author":"Barbosa Valmir Carneiro","year":"2016","unstructured":"Valmir Carneiro Barbosa, Alan Di\u00eago A. Carneiro, F\u00e1bio Protti, and U\u00e9verton S. Souza. 2016. Deadlock models in distributed computation: Foundations, design, and computational complexity. In Proceedings of the 31st Annual ACM Symposium on Applied Computing, Sascha Ossowski (Ed.). ACM, 538\u2013541."},{"key":"e_1_3_1_12_2","doi-asserted-by":"publisher","DOI":"10.5555\/12518"},{"key":"e_1_3_1_13_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01782773"},{"key":"e_1_3_1_14_2","unstructured":"Wilson Chan. 2010. Method and system for deadlock detection in a distributed environment. US Patent 7 735 089."},{"key":"e_1_3_1_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/357360.357365"},{"key":"e_1_3_1_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/2491245"},{"key":"e_1_3_1_17_2","first-page":"223","volume-title":"Proceedings of the 2012 USENIX Annual Technical Conference (USENIX ATC 12)","author":"Cowling James","year":"2012","unstructured":"James Cowling and Barbara Liskov. 2012. Granola: \\(\\lbrace\\) Low-overhead \\(\\rbrace\\) distributed transaction coordination. In Proceedings of the 2012 USENIX Annual Technical Conference (USENIX ATC 12). 223\u2013235."},{"key":"e_1_3_1_18_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICPP.2005.34"},{"key":"e_1_3_1_19_2","doi-asserted-by":"crossref","first-page":"262","DOI":"10.1145\/2806777.2806837","volume-title":"Proceedings of the 6th ACM Symposium on Cloud Computing","author":"Ding Bailu","year":"2015","unstructured":"Bailu Ding, Lucja Kot, Alan Demers, and Johannes Gehrke. 2015. Centiman: Elastic, high performance optimistic concurrency control by watermarking. In Proceedings of the 6th ACM Symposium on Cloud Computing. 262\u2013275."},{"key":"e_1_3_1_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/2815400.2815425"},{"key":"e_1_3_1_21_2","doi-asserted-by":"publisher","DOI":"10.1145\/15833.15837"},{"key":"e_1_3_1_22_2","doi-asserted-by":"publisher","DOI":"10.14778\/3055540.3055548"},{"key":"e_1_3_1_23_2","doi-asserted-by":"publisher","DOI":"10.14778\/3415478.3415535"},{"key":"e_1_3_1_24_2","first-page":"252","volume-title":"Proceedings of the 10th Annual International Phoenix Conference on Computers and Communications","author":"Johnston Brian M.","year":"1991","unstructured":"Brian M. Johnston, Ramesh Dutt Javagal, Ajoy Kumar Datta, and Sukumar Ghosh. 1991. A distributed algorithm for resource deadlock detection. In Proceedings of the 10th Annual International Phoenix Conference on Computers and Communications. IEEE Computer Society, 252\u2013253."},{"key":"e_1_3_1_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/45075.46163"},{"issue":"2","key":"e_1_3_1_26_2","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1007\/s007780050075","article-title":"Deadlock detection in distributed database systems: A new algorithm and a comparative performance analysis","volume":"8","author":"Krivokapic Natalija","year":"1999","unstructured":"Natalija Krivokapic, Alfons Kemper, and Ehud Gudes. 1999. Deadlock detection in distributed database systems: A new algorithm and a comparative performance analysis. The VLDB Journal 8, 2 (1999), 79\u2013100.","journal-title":"The VLDB Journal"},{"key":"e_1_3_1_27_2","unstructured":"Eric Lehman F. Thomson Leighton and Albert R. Meyer. 2015. Mathematics for Computer Science. MIT Open Course Ware 317\u2013327."},{"key":"e_1_3_1_28_2","doi-asserted-by":"publisher","DOI":"10.1145\/800222.806755"},{"key":"e_1_3_1_29_2","first-page":"583","volume-title":"Proceedings of the 7th IEEE International Symposium on Cluster Computing and the Grid (CCGrid 2007)","author":"Narravula Sundeep","year":"2007","unstructured":"Sundeep Narravula, A. Marnidala, Abhinav Vishnu, Karthikeyan Vaidyanathan, and Dhabaleswar K. Panda. 2007. High performance distributed lock management services using network-based remote atomic operations. In Proceedings of the 7th IEEE International Symposium on Cluster Computing and the Grid (CCGrid 2007). IEEE Computer Society, 583\u2013590."},{"key":"e_1_3_1_30_2","doi-asserted-by":"publisher","DOI":"10.1145\/319702.319717"},{"key":"e_1_3_1_31_2","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3386134"},{"key":"e_1_3_1_32_2","doi-asserted-by":"publisher","DOI":"10.1137\/0201010"},{"key":"e_1_3_1_33_2","doi-asserted-by":"publisher","DOI":"10.1145\/2815400.2815419"},{"key":"e_1_3_1_34_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE55515.2023.00019"},{"key":"e_1_3_1_35_2","doi-asserted-by":"publisher","DOI":"10.14778\/3611540.3611560"},{"key":"e_1_3_1_36_2","doi-asserted-by":"publisher","DOI":"10.14778\/3554821.3554830"},{"key":"e_1_3_1_37_2","doi-asserted-by":"crossref","first-page":"1571","DOI":"10.1145\/3183713.3196890","volume-title":"Proceedings of the 2018 International Conference on Management of Data","author":"Yoon Dong Young","year":"2018","unstructured":"Dong Young Yoon, Mosharaf Chowdhury, and Barzan Mozafari. 2018. Distributed lock management with RDMA: Decentralization without starvation. In Proceedings of the 2018 International Conference on Management of Data, Gautam Das, Christopher M. Jermaine, and Philip A. Bernstein (Eds.). ACM, 1571\u20131586."},{"key":"e_1_3_1_38_2","first-page":"126","volume-title":"SIGCOMM\u201920","author":"Yu Zhuolong","year":"2020","unstructured":"Zhuolong Yu, Yiwen Zhang, Vladimir Braverman, Mosharaf Chowdhury, and Xin Jin. 2020. NetLock: Fast, centralized lock management using programmable switches. In SIGCOMM\u201920, Henning Schulzrinne and Vishal Misra (Eds.). ACM, 126\u2013138."}],"container-title":["ACM Transactions on Computer Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3768621","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,11,6]],"date-time":"2025-11-06T13:19:20Z","timestamp":1762435160000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3768621"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,11,6]]},"references-count":37,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2025,11,30]]}},"alternative-id":["10.1145\/3768621"],"URL":"https:\/\/doi.org\/10.1145\/3768621","relation":{},"ISSN":["0734-2071","1557-7333"],"issn-type":[{"type":"print","value":"0734-2071"},{"type":"electronic","value":"1557-7333"}],"subject":[],"published":{"date-parts":[[2025,11,6]]},"assertion":[{"value":"2024-07-22","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-08-13","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-11-06","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}