The parallel complexity of deadlock detection

AbstractWhen serially re-usable multi-unit resources are shared among many processes, each of which has exclusive control over some resource units, it is possible for deadlocks to happen. The work of Holt (1971) stated the problem of deadlock detection as a directed multigraph problem. In this paper we examine the possibility of existence of fast parallel algorithms for deadlock detection. Although many graph problems have efficient parallel solutions (in parallel polylogarithmic time, by using only a polynomial number of processors), we present strong evidence that this is not the case for the general deadlock detection problem. We show that the problem is complete in Punder log-space reductions and thus probably not efficiently parallelizable. Fortunately, when the problem is restricted (e.g., single-unit requests of processes or single-unit resources), then it falls in NC. We present efficient parallel algorithms for the restricted versions of the deadlock detection problem