On the complexity of deadlock recovery

Joseph Y.T. Leung; Burkhard Monien

doi:10.1007/BFb0024010

On the complexity of deadlock recovery

Joseph Y.T. Leung, Burkhard Monien

Research output: Chapter in Book/Report/Conference proceeding › Conference 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 language	English (US)
Title of host publication	STACS 85 - 2nd Annual Symposium on Theoretical Aspects of Computer Science
Editors	K. Mehlhorn
Publisher	Springer Verlag
Pages	208-218
Number of pages	11
ISBN (Print)	9783540139126
DOIs	https://doi.org/10.1007/BFb0024010
State	Published - 1985
Externally published	Yes
Event	2nd Annual Symposium on Theoretical Aspects of Computer Science, STACS 1985 - Saarbrucken, Germany Duration: Jan 3 1985 → Jan 5 1985

Publication series

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

Other

Other	2nd Annual Symposium on Theoretical Aspects of Computer Science, STACS 1985
Country/Territory	Germany
City	Saarbrucken
Period	1/3/85 → 1/5/85

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/BFb0024010

Cite this

Leung, J. Y. T., & Monien, B. (1985). On the complexity of deadlock recovery. In K. Mehlhorn (Ed.), STACS 85 - 2nd Annual Symposium on Theoretical Aspects of Computer Science (pp. 208-218). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 182 LNCS). Springer Verlag. https://doi.org/10.1007/BFb0024010

@inproceedings{591f6b1701994554ae21977149eee047,

title = "On the complexity of deadlock recovery",

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.",

author = "Leung, {Joseph Y.T.} and Burkhard Monien",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 1985.; 2nd Annual Symposium on Theoretical Aspects of Computer Science, STACS 1985 ; Conference date: 03-01-1985 Through 05-01-1985",

year = "1985",

doi = "10.1007/BFb0024010",

language = "English (US)",

isbn = "9783540139126",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "208--218",

editor = "K. Mehlhorn",

booktitle = "STACS 85 - 2nd Annual Symposium on Theoretical Aspects of Computer Science",

address = "Germany",

}

Leung, JYT & Monien, B 1985, On the complexity of deadlock recovery. in K Mehlhorn (ed.), STACS 85 - 2nd Annual Symposium on Theoretical Aspects of Computer Science. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 182 LNCS, Springer Verlag, pp. 208-218, 2nd Annual Symposium on Theoretical Aspects of Computer Science, STACS 1985, Saarbrucken, Germany, 1/3/85. https://doi.org/10.1007/BFb0024010

On the complexity of deadlock recovery. / Leung, Joseph Y.T.; Monien, Burkhard.
STACS 85 - 2nd Annual Symposium on Theoretical Aspects of Computer Science. ed. / K. Mehlhorn. Springer Verlag, 1985. p. 208-218 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 182 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - On the complexity of deadlock recovery

AU - Leung, Joseph Y.T.

AU - Monien, Burkhard

N1 - Publisher Copyright: © Springer-Verlag Berlin Heidelberg 1985.

PY - 1985

Y1 - 1985

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85035340359&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85035340359&partnerID=8YFLogxK

U2 - 10.1007/BFb0024010

DO - 10.1007/BFb0024010

M3 - Conference contribution

AN - SCOPUS:85035340359

SN - 9783540139126

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 208

EP - 218

BT - STACS 85 - 2nd Annual Symposium on Theoretical Aspects of Computer Science

A2 - Mehlhorn, K.

PB - Springer Verlag

T2 - 2nd Annual Symposium on Theoretical Aspects of Computer Science, STACS 1985

Y2 - 3 January 1985 through 5 January 1985

ER -

On the complexity of deadlock recovery

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this