{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,7]],"date-time":"2026-05-07T15:36:32Z","timestamp":1778168192713,"version":"3.51.4"},"reference-count":47,"publisher":"Association for Computing Machinery (ACM)","issue":"10","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2025,6]]},"abstract":"<jats:p>Distributed databases are widely used in various fields, such as financial services and e-commerce. These businesses generally exhibit characteristics of large-scale and rapid growth. However, these business systems often suffer from deadlocks that prevent them from operating normally for extended periods. Traditional deadlock detection methods face challenges in scalability and efficiency, especially as the number of nodes increases. Therefore, deadlock detection has always been a research area in distributed databases.<\/jats:p>\n          <jats:p>\n            In this paper, we introduce an efficient deadlock detection algorithm called HAWK, leveraging a\n            <jats:bold>H<\/jats:bold>\n            ierarchical\n            <jats:bold>A<\/jats:bold>\n            pproach based on\n            <jats:bold>W<\/jats:bold>\n            or\n            <jats:bold>K<\/jats:bold>\n            load modeling. Our algorithm addresses these issues by constructing a dynamic hierarchical detection tree that adapts to transaction patterns, significantly reducing time complexity and communication overhead. HAWK first models the workload and generates a\n            <jats:italic toggle=\"yes\">predicted access graph<\/jats:italic>\n            (PAG), transforming the problem of partitioning detection task in the basic hierarchical detection into partition detection zone (DZ) in the PAG by a graph-cutting algorithm. Then, leveraging the properties of strongly connected components (SCCs) and deadlock cycles, the SCC-cut algorithm naturally partitions the system-wide deadlock detection into multiple non-intersecting detection zones, thereby enhancing detection efficiency. We used the greedy SCC-cut algorithm to perform a more fine-grained partitioning of the complex PAG. Finally, by periodically sampling and updating the hierarchical structure, the algorithm remains responsive to dynamic workload variations, ensuring efficient detection. Our approach outperforms both centralized and distributed methods, offering a more efficient and adaptive solution. Extensive experimental results demonstrate the effectiveness of the HAWK algorithm, showing significant reductions in the duration of the deadlock and improved system throughput.\n          <\/jats:p>","DOI":"10.14778\/3748191.3748224","type":"journal-article","created":{"date-parts":[[2025,9,4]],"date-time":"2025-09-04T13:50:16Z","timestamp":1756993816000},"page":"3682-3694","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["HAWK: A Workload-Driven Hierarchical Deadlock Detection Approach in Distributed Database System"],"prefix":"10.14778","volume":"18","author":[{"given":"Rongrong","family":"Zhang","sequence":"first","affiliation":[{"name":"East China Normal University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zhiwei","family":"Ye","sequence":"additional","affiliation":[{"name":"China Mobile Cloud Center"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jun-Peng","family":"Zhu","sequence":"additional","affiliation":[{"name":"East China Normal University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Peng","family":"Cai","sequence":"additional","affiliation":[{"name":"East China Normal University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xuan","family":"Zhou","sequence":"additional","affiliation":[{"name":"East China Normal University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dunbo","family":"Cai","sequence":"additional","affiliation":[{"name":"China Mobile Cloud Center"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ling","family":"Qian","sequence":"additional","affiliation":[{"name":"China Mobile Cloud Center"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,9,4]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"2025. Postgres. https:\/\/www.postgresql.org\/"},{"key":"e_1_2_1_2_1","unstructured":"2025. TPC-C Benchmark. https:\/\/www.tpc.org\/tpcc\/results\/tpcc_results5.asp"},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the 2017 ACM International Conference on Management of Data. 331\u2013343","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 al. 2017. Spanner: Becoming a SQL system. In Proceedings of the 2017 ACM International Conference on Management of Data. 331\u2013343."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/6513.6516"},{"key":"e_1_2_1_5_1","volume-title":"Don't Get Stuck: A Deadlock Recovery Approach. arXiv preprint arXiv:2408.10167","author":"Baldini Francesca","year":"2024","unstructured":"Francesca Baldini, Faizan M Tariq, Sangjae Bae, and David Isele. 2024. Don't Get Stuck: A Deadlock Recovery Approach. arXiv preprint arXiv:2408.10167 (2024)."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1088\/0967-1846\/4\/4\/006"},{"key":"e_1_2_1_7_1","unstructured":"Valmir C Barbosa and Mario RF Benevides. 1998. A graph-theoretic characterization of AND-OR deadlocks. In UFRJ Technical Report COPPE-ES-472\/98 Rio de Janeiro Brazil. Citeseer."},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the 31st annual ACM symposium on applied computing. 538\u2013541","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. 538\u2013541."},{"key":"e_1_2_1_9_1","unstructured":"Philip A Bernstein Vassos Hadzilacos Nathan Goodman et al. 1987. Concurrency control and recovery in database systems. Vol. 370. Addison-wesley Reading."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/71.706047"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/800222.806756"},{"key":"e_1_2_1_12_1","unstructured":"Wilson Chan. 2010. Method and system for deadlock detection in a distributed environment."},{"key":"e_1_2_1_13_1","volume-title":"A Distributed Deadlock Detection Algorithm and Its Correctness Proof. submitted to the Communications of the ACM","author":"Chandy KM","year":"1982","unstructured":"KM Chandy, J Misra, L Haas, and TEXAS UNIV AT AUSTIN DEPT OF COMPUTER SCIENCES. 1982. A Distributed Deadlock Detection Algorithm and Its Correctness Proof. submitted to the Communications of the ACM (1982)."},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the first ACM SIGACT-SIGOPS symposium on Principles of distributed computing. 157\u2013164","author":"Mani Chandy K","year":"1982","unstructured":"K Mani Chandy and Jayadev Misra. 1982. A distributed algorithm for detecting resource deadlocks in distributed systems. In Proceedings of the first ACM SIGACT-SIGOPS symposium on Principles of distributed computing. 157\u2013164."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/357360.357365"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/32.21721"},{"key":"e_1_2_1_17_1","volume-title":"Yang Zhang, and Samuel R Madden.","author":"Curino Carlo","year":"2010","unstructured":"Carlo Curino, Evan Philip Charles Jones, Yang Zhang, and Samuel R Madden. 2010. Schism: a workload-driven approach to database replication and partitioning. (2010)."},{"key":"e_1_2_1_18_1","volume-title":"Bernabeu-Auban","author":"Gonz\u00e1lez De Mend\u00edvil JR","year":"1999","unstructured":"JR Gonz\u00e1lez De Mend\u00edvil, Federico Fari\u00f1a, JR Garitagotia, Carlos F Alastruey, and Jose M. Bernabeu-Auban. 1999. A distributed deadlock resolution algorithm for the AND model. IEEE transactions on parallel and distributed systems 10, 5 (1999), 433\u2013447."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(80)90021-6"},{"key":"e_1_2_1_20_1","volume-title":"Path-based depth-first search for strong and biconnected components","author":"Gabow Harold N","year":"1999","unstructured":"Harold N Gabow. 1999. Path-based depth-first search for strong and biconnected components; CU-CS-890-99. (1999)."},{"key":"e_1_2_1_21_1","doi-asserted-by":"crossref","unstructured":"Tarek Helmy. 2024. An Improved Deadlock Detection and Resolution Algorithm for Distributed Computing Systems. (2024).","DOI":"10.20944\/preprints202403.1310.v1"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389704"},{"key":"e_1_2_1_23_1","first-page":"554","article-title":"Protocols for deadlock detection in distributed database systems","volume":"6","author":"Ho Gary S.","year":"1982","unstructured":"Gary S. Ho and CV Ramamoorthy. 1982. Protocols for deadlock detection in distributed database systems. IEEE Transactions on Software Engineering 6 (1982), 554\u2013557.","journal-title":"IEEE Transactions on Software Engineering"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.14778\/3415478.3415535"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/45075.46163"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/32.263754"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.2004.51"},{"key":"e_1_2_1_28_1","unstructured":"Eric Lehman F Thomson Leighton and Albert R Meyer. 2015. Mathematics for Computer Science . 317\u2013327 pages."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457562"},{"key":"e_1_2_1_30_1","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1109\/TSE.1979.234181","article-title":"Locking and deadlock detection in distributed databases","volume":"3","author":"Menasce Daniel A","year":"1979","unstructured":"Daniel A Menasce and Richard R Muntz. 1979. Locking and deadlock detection in distributed databases. IEEE Transactions on Software Engineering 3 (1979), 195\u2013202.","journal-title":"IEEE Transactions on Software Engineering"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/69622.357190"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/800222.806755"},{"key":"e_1_2_1_33_1","unstructured":"MySQL. 2024. https:\/\/www.mysql.com."},{"key":"e_1_2_1_34_1","volume-title":"2009 Fifth International Conference on Information Assurance and Security","volume":"2","author":"Ni Qinqin","year":"2009","unstructured":"Qinqin Ni, Weizhen Sun, and Sen Ma. 2009. Deadlock detection based on resource allocation graph. In 2009 Fifth International Conference on Information Assurance and Security, Vol. 2. IEEE, 135\u2013138."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/319702.319717"},{"key":"e_1_2_1_36_1","unstructured":"M Tamer \u00d6zsu Patrick Valduriez et al. 1999. Principles of distributed database systems. Vol. 2. Springer."},{"key":"e_1_2_1_37_1","volume-title":"Proceedings of the 16th international conference on extending database technology. 430\u2013441","author":"Quamar Abdul","year":"2013","unstructured":"Abdul Quamar, K Ashwin Kumar, and Amol Deshpande. 2013. SWORD: scalable workload-aware data placement for transactional workloads. In Proceedings of the 16th international conference on extending database technology. 430\u2013441."},{"key":"e_1_2_1_38_1","volume-title":"Amany Khalifa Alarbish, and Amal Apojila Osha.","author":"Rgibi Ahmed Elajeli","year":"2024","unstructured":"Ahmed Elajeli Rgibi, Abdusamea Ibrahim Omer, Amany Khalifa Alarbish, and Amal Apojila Osha. 2024. EXPLORING DEADLOCK DETECTION ALGORITHMS IN CONCURRENT PROGRAMMING: A COMPARATIVE ANALYSIS AND EVALUATION. Scientific Journal of Applied Sciences of Sabratha University (2024), 106\u2013117."},{"key":"e_1_2_1_39_1","article-title":"Deadlock detection and recovery in distributed databases","volume":"73","author":"Sapra Pooja","year":"2013","unstructured":"Pooja Sapra, Suresh Kumar, and RK Rathy. 2013. Deadlock detection and recovery in distributed databases. International Journal of Computer Applications 73, 1 (2013).","journal-title":"International Journal of Computer Applications"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/0898-1221(81)90008-0"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10619-011-7078-7"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3386134"},{"key":"e_1_2_1_43_1","series-title":"SIAM journal on computing 1, 2","volume-title":"Depth-first search and linear graph algorithms","author":"Tarjan Robert","year":"1972","unstructured":"Robert Tarjan. 1972. Depth-first search and linear graph algorithms. SIAM journal on computing 1, 2 (1972), 146\u2013160."},{"key":"e_1_2_1_44_1","volume-title":"LCL: A Lock Chain Length-based Distributed Algorithm for Deadlock Detection and Resolution. In 2023 IEEE 39th International Conference on Data Engineering (ICDE). IEEE, 151\u2013163","author":"Yang Zhenkun","year":"2023","unstructured":"Zhenkun Yang, Chen Qian, Xuwang Teng, Fanyu Kong, Fusheng Han, and Quanqing Xu. 2023. LCL: A Lock Chain Length-based Distributed Algorithm for Deadlock Detection and Resolution. In 2023 IEEE 39th International Conference on Data Engineering (ICDE). IEEE, 151\u2013163."},{"key":"e_1_2_1_45_1","doi-asserted-by":"crossref","first-page":"3385","DOI":"10.14778\/3554821.3554830","article-title":"OceanBase: a 707 million tpmC distributed relational database OceanBasesystem","volume":"15","author":"Yang Zhenkun","year":"2022","unstructured":"Zhenkun Yang, Chuanhui Yang, Fusheng Han, Mingqiang Zhuang, Bing Yang, Zhifeng Yang, Xiaojun Cheng, Yuzhong Zhao, Wenhui Shi, Huafeng Xi, et al. 2022. OceanBase: a 707 million tpmC distributed relational database OceanBasesystem. Proceedings of the VLDB Endowment 15, 12 (2022), 3385\u20133397.","journal-title":"Proceedings of the VLDB Endowment"},{"key":"e_1_2_1_46_1","volume-title":"Proceedings of the 2018 International Conference on Management of Data. 1571\u20131586","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. 1571\u20131586."},{"key":"e_1_2_1_47_1","volume-title":"Proceedings of the Annual conference of the ACM Special Interest Group on Data Communication on the applications, technologies, architectures, and protocols for computer communication. 126\u2013138","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 Proceedings of the Annual conference of the ACM Special Interest Group on Data Communication on the applications, technologies, architectures, and protocols for computer communication. 126\u2013138."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3748191.3748224","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,4]],"date-time":"2025-09-04T13:54:33Z","timestamp":1756994073000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3748191.3748224"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6]]},"references-count":47,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2025,6]]}},"alternative-id":["10.14778\/3748191.3748224"],"URL":"https:\/\/doi.org\/10.14778\/3748191.3748224","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2025,6]]},"assertion":[{"value":"2025-09-04","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}