IEEE Transactions on Software Engineering · 2004 · 43 citations · 16 references
ComputingComputer EngineeringComputer ScienceAlgorithmsDistributed SystemsMessage PassingDeadlock AvoidanceDistributed AlgorithmsDistributed ComputingDeadlockDeadlock AnalysisDeadlock DetectionDeadlock HandlingDeadlock ResolutionDistributed Deadlock DetectionDistributed Deadlock ResolutionExecution Time Analysis
In the literature, only a few studies have been performed on the distributed deadlock detection and resolution problem in the generalized request model. Most of the studies are based on the diffusing computation technique where propagation of probes and backward propagation of replies are required to detect deadlock. The replies carry the dependency information between processes for the initiator of the algorithm to determine deadlock. Since fast detection of deadlock is critical, we take a centralized approach that removes the need of backward propagation of replies, but sends the dependency information directly to the initiator of the algorithm. This enables reduction of time cost for deadlock detection to half of that of the existing distributed algorithms. The algorithm is extended to handle concurrent executions in order to further improve deadlock detection time, whereas the current algorithms focus only on a single execution. Simulation experiments are performed to see the effectiveness of this centralized approach as compared to previous distributed algorithms. It is found that our algorithm shows better results in several performance metrics especially in deadlock latency and algorithm execution time.
16
K. Mani Chandy, Leslie Lamport · ACM Transactions on Computer Systems · 1985 · 2.4K citations · Full text
Deadlock detection in distributed systems
M. Singhal · Computer · 1989 · 272 citations
Distributed deadlock detection
Gabriel Bracha, Sam Toueg · Distributed Computing · 1987 · 94 citations
A distributed algorithm for generalized deadlock detection
Gabriel Bracha, Sam Toueg · 1984 · 87 citations