Hierarchical Deadlock Detection in Nested Transactions: A Depth-First Search Optimization Framework

Abstract

Deadlock detection in nested transactions is crucial for maintaining system stability and ensuring efficient transaction processing. In nested transaction systems, deadlocks can occur not only between top-level transactions but also among subtransactions, resulting in intricate cycles that complicate resolution. Traditional methods, which often involve examining the entire Wait-For Graph (WFG) for cycles, tend to be resource-intensive and time-consuming. As the complexity of transactions increases, there is a growing need for efficient deadlock detection techniques to optimize resource utilization and enhance overall system performance. This research focuses on developing an efficient Depth-First Search (DFS)-based algorithm to address hierarchical deadlocks that arise from subtransaction dependencies. By modelling transaction relationships as a directed graph, where nodes represent transactions and edges denote dependencies, the proposed approach iteratively applies the DFS algorithm to identify cycles indicative of potential deadlocks. The algorithm not only detects deadlocks but also provides detailed insights into the involved transactions, the deadlock cycle, and indirect dependencies. Key performance metrics, such as execution time, memory usage, system throughput, response time, and success ratio, were computed during the detection process. Implemented and validated in a MATLAB simulation environment, the algorithm demonstrated significant improvements in deadlock detection efficiency within nested transactional systems. Results showed its effectiveness in identifying hierarchical deadlocks, with favourable performance in execution time, memory usage, and overall throughput, even in scenarios of varying transaction complexity. This research highlights the importance of efficient deadlock detection techniques in optimizing resource utilization and advancing concurrent system performance. The proposed DFS-based algorithm offers a robust solution for managing hierarchical deadlocks and lays the groundwork for future development of resilient and dependable transaction management systems.