An Improved Deadlock Detection and Resolution Algorithm for Distributed Computing Systems

Deadlock is a real problem that can cause expensive, time-dependent hang-ups or failures in distributed computing systems. Some studies have been conducted with deadlock detection and resolution in generalized request computing models, most of these studies are based on the diffusing computation scheme, where forward and backward propagated probe and reply messages respectively are diffused between dependent processes. The replies carry the dependency information between processes for the initiator. Using this dependency information initiator can detect and resolve the deadlock cycle. It has been proven in the literature that a deadlock cycle length distribution is skewed with a large majority of cycles (90%) having length two. Based on this fact an improved algorithm is proposed for handling deadlock detection in distributed computing systems under the distributed request model where each process has several requests at a time. The improved algorithm depends mainly on message propagation and timeout policy. Probe and reply messages are propagated between the initiator and its successors only to detect deadlock cycles between them. Global timeout policy is used to detect potential deadlock cycles with large length distribution. The proposed algorithm can handle concurrent executions. Simulation experiments are performed to see the effectiveness of the improved algorithm. It is found that the improved algorithm compares favorably with other existing algorithms and it shows better results for several performance metrics especially in reducing deadlock latency and execution time.