Efficient detection and resolution of generalized distributed deadlocks
- 1 January 1994
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Software Engineering
- Vol. 20 (1) , 43-54
- https://doi.org/10.1109/32.263754
Abstract
We present an efficient one-phase algorithm that consists of two concurrent sweeps of messages to detect generalized distributed deadlocks. In the outward sweep, the algorithm records a snapshot of a distributed wait-for-graph (WFG). In the inward sweep, the algorithm performs reduction of the recorded distributed WFG to check for a deadlock. The two sweeps can overlap in time at a process. We prove the correctness of the algorithm. The algorithm has a worst-case message complexity of 4e/spl minus/2n+2l and a time complexity of 2d hops, where e is the number of edges, n is the number of nodes, l is the number of leaf nodes, and d is the diameter of the WFG. This is a notable improvement over the existing algorithms to detect generalized deadlocks.Keywords
This publication has 10 references indexed in Scilit:
- Detecting termination of distributed computations by external agentsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Deadlock detection in distributed systemsComputer, 1989
- A modified priority based probe algorithm for distributed deadlock detection and resolutionIEEE Transactions on Software Engineering, 1989
- Resolution of deadlocks in object-oriented distributed systemsIEEE Transactions on Computers, 1989
- Deadlock detection in distributed databasesACM Computing Surveys, 1987
- Distributed deadlock detectionDistributed Computing, 1987
- Distributed snapshotsACM Transactions on Computer Systems, 1985
- A Priority Based Distributed Deadlock Detection AlgorithmIEEE Transactions on Software Engineering, 1985
- Time, clocks, and the ordering of events in a distributed systemCommunications of the ACM, 1978
- Some Deadlock Properties of Computer SystemsACM Computing Surveys, 1972