Title :
Efficient deadlock resolution for lock-based concurrency control schemes
Author :
Roesle, Marina ; Burkhard, Walter A. ; Cooper, Kenneth B.
Author_Institution :
Dept. of Comput. Sci. & Eng., California Univ., San Diego, La Jolla, CA, USA
Abstract :
A distributed algorithm is proposed for detection and resolution of resource deadlocks in object-oriented distributed systems. The algorithm can be used in conjunction with concurrency control algorithms that are based on the semantic lock model. To drastically reduce message traffic, the algorithm properly identifies and eliminates redundant messages. It is shown that its worst and average time complexities are O(ne), where e is the number of edges in the waits-for graph and n is the number of vertices
Keywords :
computational complexity; distributed processing; operating systems (computers); system recovery; directed graphs; distributed algorithm; lock-based concurrency control schemes; message traffic; object-oriented distributed systems; redundant messages; semantic lock model; time complexities; waits-for graph; Brazil Council; Computer science; Concurrency control; Control systems; Delay; Detection algorithms; Distributed algorithms; Object oriented modeling; System recovery; Traffic control;
Conference_Titel :
Distributed Computing Systems, 1988., 8th International Conference on
Conference_Location :
San Jose, CA
Print_ISBN :
0-8186-0865-X
DOI :
10.1109/DCS.1988.12521
