An Optimal Deadlock Resolution Algorithm in Multidatabase Systems

In this paper, we propose a novel deadlock resolution algorithm. In the presence of global deadlocks in a multidatabase system, this algorithm always selects an optimal set of victims for removing deadlocks. It makes the use of network flow techniques, and runs in time O(n 3 ), where n is the number of the deadlocked global transactions. Furthermore, the proposed deadlock resolution algorithm dose not have livelock and transaction processing starvation problems. Keywords: Deadlock, Multidatabase, Concurrency Control, Optimization. 1 Introduction A multidatabase system (MDBS) is a federation of independently developed component database systems through a communication network. These component database systems are also called local database systems (LDBSs) in contrast to an MDBS. There are two types of transactions in an MDBS: ffl Local transactions - that execute in a single LDBS. ffl Global transactions - that execute on several LDBSs. One major issue in transaction management ..