On the complexity of deadlock recovery

Joseph Leung, Burkhard Monien

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We consider the computational complexity of finding an optimal deadlock recovery. It is known that for an arbitrary number of resource types the problem is NP-hard even when the total cost of deadlocked jobs and the total number of resource units are “small” relative to the number of deadlocked jobs. It is also known that for one resource type the problem is NP-hard when the total cost of deadlocked jobs and the total number of resource units are “large” relative to the number of deadlocked jobs. In this paper we show that for one resource type the problem is solvable in polynomial time when the total cost of deadlocked jobs or the total number of resource units is “small” relative to the number of deadlocked jobs. For fixed m ≥ 2 resource types, we show that the problem is solvable in polynomial time when the total number of resource units is “small” relative to the number of deadlocked jobs. On the other hand, when the total number of resource units is “large”, the problem becomes NP-hard even when the total cost of deadlocked jobs is “small” relative to the number of deadlocked jobs. The results in this paper, together with previous known ones, give a complete delineation of the complexity of this problem under various assumptions of the input parameters.

Original languageEnglish (US)
Title of host publicationSTACS 85 - 2nd Annual Symposium on Theoretical Aspects of Computer Science
EditorsK. Mehlhorn
PublisherSpringer Verlag
Pages208-218
Number of pages11
ISBN (Print)9783540139126
DOIs
StatePublished - Jan 1 1985
Event2nd Annual Symposium on Theoretical Aspects of Computer Science, STACS 1985 - Saarbrucken, Germany
Duration: Jan 3 1985Jan 5 1985

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume182 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other2nd Annual Symposium on Theoretical Aspects of Computer Science, STACS 1985
CountryGermany
CitySaarbrucken
Period1/3/851/5/85

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'On the complexity of deadlock recovery'. Together they form a unique fingerprint.

Cite this