No label defined (Q4727428)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 4001481
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 4001481

      Statements

      1986
      0 references
      deadlock detection
      0 references
      fast parallel algorithms
      0 references
      0 references
      [For the entire collection see Zbl 0596.00021.] When serially reusable multiunit 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 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 P under 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.
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references