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

fYear

1988

fDate

13-17 Jun 1988

Firstpage

224

Lastpage

233

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;

fLanguage

English

Publisher

ieee

Conference_Titel

Distributed Computing Systems, 1988., 8th International Conference on

Conference_Location

San Jose, CA

Print_ISBN

0-8186-0865-X

Type

conf

DOI

10.1109/DCS.1988.12521

Filename

12521