This thesis shows that the edge-chasing deadlock detection algorithm of Choudhary fails to remove the existing deadlocks after committing the transaction whose priority is lowest on the transaction wait-for path. A modified algorithm that solves this problem is proposed. In addition, the performance of the modified algorithm is compared with that of the Tsai's deadlock detection algorithm that uses transaction-resource graph (TR graph) using simulation approach. The correctness of the modified algorithm and Tsai's algorithm is verified through the simulations.
According to the simulation results, when the global resource request ratio is low, Tsai's algorithm performs better than the modified algorithm, since Tsai's algorithm stores TR graph in main memory, while the modified algorithm stores the lock table on disk storage. When the global resource request ratio is high, however, the modified algorithm outperforms Tsai's algorithm; the reason is that Tsai's algorithm has more interprocess communication messages for lock requests or allocations than the modified algorithm because in Tsai's algorithm transaction manager sends every message to remote data manager via its local data manager, whereas the modified algorithm because in Tsai's algorithm transaction manager sends every message to remote data manager via its local data manager, whereas the modified algorithm sends the message directly to the remote data manager.
