Deadlock detection in distributed database systems: a new algorithm and a comparative performance analysis

This paper attempts a comprehensive study of deadlock detection in distribu ted database systems. First, the two predominant deadlock models in these s ystems and the four different distributed deadlock detection approaches are discussed. Afterwards, a new deadlock detection algorithm is presented. Th e algorithm is based on dynamically creating deadlock detection agents (DDA s), each being responsible for detecting deadlocks in one connected compone nt of the global wait-for-graph (WFG). The DDA scheme is a "self-tuning" sy stem: after an initial warm-up phase, dedicated DDAs will be formed for "ce nters of locality", i.e., parts of the system where many conflicts occur. A dynamic shift in locality of the distributed system will be responded to b y automatically creating new DDAs while the obsolete ones terminate. In thi s paper, we also compare the most competitive representative of each class of algorithms suitable for distributed database systems based on a simulati on model, and point out their relative strengths and weaknesses. The extens ive experiments we carried out indicate that our newly proposed deadlock de tection algorithm outperforms the other algorithms in the vast majority of configurations and workloads and, in contrast to all other algorithms, is v ery robust with respect to differing load and access profiles.