A fast distributed deadlock- detection algorithm for hypercube

Abstract

There have been several distributed algorithms for deadlock detection. These algor­ithms are genera) and detect deadlocks for all topologies. In this paper, we have developed a fast distributed deadlock-detection algorithm for hypercube where a node waits for at most one message ai a time. Non-waiting nodes participate in deadlock detection by assisting in signal passing. For analysis purpose, the algorithm is 3 described for synchronous mode of computation. This algorithm terminates in O(n ³) time with overwhelming probability for a n-dimensional binary cube.

Keywords:

• Algorithm
• complexity analysis
• deadlock
• distributed algorithm
• distributed system
• tree contraction
• parallel algorithm
• synchronous parallel computation

C.R. Categories:

• C2.4
• D4.2
• F2.2