NDLI: Designing Compact and Maximally Permissive Deadlock Avoidance Policies for Complex Resource Allocation Systems Through Classification Theory: The Linear Case

Content Provider	IEEE Xplore Digital Library
Author	Nazeem, A. Reveliotis, S. Yin Wang Lafortune, S.
Copyright Year	1963
Abstract	Most of the past research on the problem of deadlock avoidance for complex resource allocation systems (RAS) has acknowledged the fact that the computation of the maximally permissive deadlock avoidance policy (DAP) possesses super-polynomial complexity for most RAS classes, and therefore, it has resorted to solutions that trade off maximal permissiveness for computational tractability. In this paper, we distinguish between the off-line and the on-line computation that is required for the effective implementation of the maximally permissive DAP, and we seek to develop representations of this policy that will require minimal on-line computation. The particular representation that we adopt is that of a compact classifier that will effect the underlying dichotomy of the reachable state space into safe and unsafe subspaces. Furthermore, in this first study of the aforementioned problem, we restrict our attention to a particular RAS class that is motivated by an ongoing project of ours called Gadara, and accepts separation of the safe and unsafe subspaces of its instantiations through a set of linear inequalities. Through a series of reductions of the derived classification problem, we are also able to attain extensive reductions in the computational complexity of the off-line task of the construction of the sought classifier. We formally establish completeness and optimality properties for the proposed design procedures. We also offer heuristics that, if necessary, can alleviate the computational effort that is necessary for the construction of the sought classifier. Finally, we demonstrate the efficacy of the developed approaches through a series of computational experiments. To the best of our knowledge, these experiments also establish the ability of the proposed methodology to effectively compute tractable implementations of the maximally permissive DAP for problem instances significantly beyond the capacity of any other approach currently available in the literature.
Sponsorship	IEEE Control Systems Society
Starting Page	1818
Ending Page	1833
Page Count	16
File Size	821429
File Format	PDF
ISSN	00189286
Volume Number	56
Issue Number	8
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2011-08-01
Publisher Place	U.S.A.
Access Restriction	One Nation One Subscription (ONOS)
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Resource management System recovery Context Strontium Safety Equations Electronic mail supervisory control Classification theory deadlock avoidance
Content Type	Text
Resource Type	Article
Subject	Control and Systems Engineering Electrical and Electronic Engineering Computer Science Applications

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Designing Compact and Maximally Permissive Deadlock Avoidance Policies for Complex Resource Allocation Systems Through Classification Theory: The Nonlinear Case

Designing compact and maximally permissive deadlock avoidance policies for complex resource allocation systems through classification theory: the linear case.

Designing maximally permissive deadlock avoidance policies for sequential resource allocation systems through classification theory

Designing compact and maximally permissive deadlock avoidance policies for complex resource allocation systems through classification theory: the non-linear case.

A BDD-Based Approach for Designing Maximally Permissive Deadlock Avoidance Policies for Complex Resource Allocation Systems

A BDD-Based Approach for Designing Maximally Permissive Deadlock Avoidance Policies for Complex Resource Allocation Systems

A BDD-Based Approach for Designing Maximally Permissive Deadlock Avoidance Policies for Complex Resource Allocation Systems

Designing Optimal Deadlock Avoidance Policies for Sequential Resource Allocation Systems Through Classification Theory: Existence Results and Customized Algorithms

Maximally permissive deadlock avoidance for sequential resource allocation systems using disjunctions of linear classifiers

Designing Compact and Maximally Permissive Deadlock Avoidance Policies for Complex Resource Allocation Systems Through Classification Theory: The Linear Case

Similar Documents

Designing Compact and Maximally Permissive Deadlock Avoidance Policies for Complex Resource Allocation Systems Through Classification Theory: The Nonlinear Case

Designing compact and maximally permissive deadlock avoidance policies for complex resource allocation systems through classification theory: the linear case.

Designing maximally permissive deadlock avoidance policies for sequential resource allocation systems through classification theory

Designing compact and maximally permissive deadlock avoidance policies for complex resource allocation systems through classification theory: the non-linear case.

A BDD-Based Approach for Designing Maximally Permissive Deadlock Avoidance Policies for Complex Resource Allocation Systems

A BDD-Based Approach for Designing Maximally Permissive Deadlock Avoidance Policies for Complex Resource Allocation Systems

A BDD-Based Approach for Designing Maximally Permissive Deadlock Avoidance Policies for Complex Resource Allocation Systems

Designing Optimal Deadlock Avoidance Policies for Sequential Resource Allocation Systems Through Classification Theory: Existence Results and Customized Algorithms

Maximally permissive deadlock avoidance for sequential resource allocation systems using disjunctions of linear classifiers

Designing Compact and Maximally Permissive Deadlock Avoidance Policies for Complex Resource Allocation Systems Through Classification Theory: The Linear Case