Semantic lock models in object-oriented distributed systems and deadlock resolution
M. Roesler, Walter A. Burkhard · ACM SIGMOD Record · 1988
We propose a distributed algorithm for detection and resolution of resource deadlocks in object-oriented distributed systems. The algorithm proposed is shown to detect and resolve all O(n 1 ) cycles present in the worst case waits-for-graph (WFG) with n vertices by transmitting O(n 3 ) messages of small constant size. Its average time complexity has been shown to be O(ne), where e is the number of edges in the WFG After deadlock resolution, the algorithm leaves information in the system concerning dependence relations of running transactions. This information will preclude the wasteful retransmission of messages and reduce the delay in detecting future deadlocks .