Efficient detection and resolution of deadlocks in distributed databases

Deadlock detection and resolution is one of the major components of a succe ssful distributed database management system. In this article, we discuss d eadlock detection and resolution strategies and present two approaches for detecting and resolving deadlocks in both general distributed database syst ems and distributed real-time database systems. Our first approach is to co llect information on the connectivity of nodes of the overall Transaction W ait-For Graph (TWFG) of the distributed database system and then use these connectivities information to build a local TWFG at each node of the overal l TWFG. We then detect the deadlocks by locating the cycles in each local T WFG. To resolve the deadlocks, the nodes involved in those cycles in each l ocal TWFG, are removed until there is no cycle in the local TWFGs. Our seco nd approach continuously checks for the occurrence of a deadlock between di fferent transaction trees. As soon as it detects a deadlock, it resolves it by aborting one of the transaction tree which has been initiated more rece ntly. Some of the advantages of our approaches over the approaches which us e Probe messages are: (1) no extra storage required to store different prob e messages, (2) no false (Phantom) deadlocks are reported, (3) detects and resolves all deadlocks. In addition, our approaches use less message and ti me to detect and resolve all deadlocks in existing TWFG of the distributed database system. (C) 1999 Elsevier Science B.V. All rights reserved.