Towards an efficient probabilistic deadlock detection method for multidatabase systems

Deadlock detection is an important issue in multidatabase systems. Due to the autonomy of the local systems, the visibility of the state of local transactions and the contention on items is not available. The well known PCG method exploits a weaker mean condition to detect potential global deadlock, that does not necessarily correspond to a real one. We present a probabilistic analysis of PCG using random graph theory and establish the foundations of a new method called random deadlock detection (RDD) for which implementation and performance should be better