Resolution of deadlocks in object-oriented distributed systems

The authors propose and prove a distributed algorithm for detection and resolution of resource deadlocks in object-oriented distributed systems. In particular, the algorithm can be used in conjunction with concurrency control algorithms which are based on the semantic lock model. The algorithm great...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on computers 1989-08, Vol.38 (8), p.1212-1224
Main Authors: Roesler, M., Burkhard, W.A.
Format: Article
Language:English
Subjects:
Brazil Council
Concurrency control
Delay
Detection algorithms
Distributed algorithms
Object oriented modeling
Scheduling
System recovery
Traffic control
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The authors propose and prove a distributed algorithm for detection and resolution of resource deadlocks in object-oriented distributed systems. In particular, the algorithm can be used in conjunction with concurrency control algorithms which are based on the semantic lock model. The algorithm greatly reduces message traffic by properly identifying and eliminating redundant messages. It is shown that both its worst and average time complexities are O(n*e), where n is the number of nodes and e is the number of edges in the waits-for graph. After deadlock resolution, the algorithm leaves information in the system concerning dependence relations of currently running transactions. This information will preclude the wasteful retransmission of messages and reduce the delay in detecting future deadlocks.< >
ISSN:0018-9340
1557-9956
DOI:10.1109/12.30874