Title :
Towards efficient algorithms for deadlock detection and resolution in distributed systems
Author :
Wang, ShouHan ; Vossen, Gottfried
Author_Institution :
Dept. of Comput. Sci & Eng., California Univ., San Diego, La Jolla, CA, USA
Abstract :
A theoretical framework for wait-for systems is provided, and general characteristics of a correct algorithm for deadlock detection and resolution are presented. It is shown that the computational upper bounds (number of messages) for deadlock detection and resolution are both O(n3) in the worst case when n transactions are involved. This result is better than previous ones, which often are even exponential. Two correct deadlock detection and resolution algorithms are described which both achieve these upper bounds
Keywords :
database theory; distributed databases; fault tolerant computing; system recovery; computational upper bounds; correct algorithm; deadlock detection; deadlock resolution; distributed systems; wait-for systems; Computer science; Detection algorithms; Distributed computing; Distributed databases; Object oriented modeling; Processor scheduling; Proposals; System recovery; Transaction databases; Upper bound;
Conference_Titel :
Data Engineering, 1989. Proceedings. Fifth International Conference on
Conference_Location :
Los Angeles, CA
Print_ISBN :
0-8186-1915-5
DOI :
10.1109/ICDE.1989.47228
