On the optimality of randomized deadlock avoidance policies

DOI10.1023/A:1025675515166MaRDI QIDQ1412282zbMATH OpenOpenAlexFDO

Authors Spyros Reveliotis, Jin Young Choi

Publication date 10 November 2003

Published in Discrete Event Dynamic Systems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1023/a:1025675515166

zbMATH Keywords

controlled Markov chainsdeadlock resolutionrandomized policiessequential resource allocation systems

Mathematics Subject Classification ID

Randomized algorithms (68W20) Discrete location and assignment (90B80) Resource and cost allocation (including fair division, apportionment, etc.) (91B32) Discrete event control/observation systems (93C65) Stochastic systems in control theory (general) (93E03) Optimal stochastic control (93E20)

Review text

The paper revisits the problem of selecting an optimal deadlock resolution strategy when the selection criterion is the maximization of the system throughput and the system is Markovian in terms of its timing and routing characteristics. This problem was addressed in previous work of the authors that (i) provided an analytical formulation for it, (ii) introduced the notion of randomized deadlock avoidance as a generalization of the more traditional approaches of deadlock prevention/avoidance, and detection and recovery, and (iii) provided a methodology for selecting the optimal randomized deadlock avoidance policy for a given resource allocation system (RAS) configuration. An issue that remained open was whether the proposed policy randomization is essential, i.e. whether there exist any RAS configurations for which a randomized deadlock avoidance policy is superior to any other policy that does not employ randomization. The present paper establishes that for the basic problem formulation where the only concern is the (unconstrained) maximization of the system throughput -- or the other typical performance objectives of minimizing the system work-in-process and mean sojourn time -- randomization of the deadlock resolution strategy is not essential. However, it is also shown that, sometimes, it can offer an effective mechanism for accommodating additional operational constraints, like the requirement for production according to a specified product mix.

Recommendations

• scientific article; zbMATH DE number 1836367
• Polynomial-complexity deadlock avoidance policies for sequential resource allocation systems
• Stochastic analysis of distributed deadlock scheduling
• Deadlock avoidance in sequential resource allocation systems with multiple resource acquisitions and flexible routings
• Deadlock-freedom in resource contentions

Cited in

(8)

• Robustness of deadlock avoidance algorithms for sequential processes.
• Optimal linear separation of the safe and unsafe subspaces of sequential resource allocation systems as a set-covering problem: algorithmic procedures and geometric insights
• On the correctness of orphan management algorithms
• Polynomial-complexity deadlock avoidance policies for sequential resource allocation systems
• Correction to the RUN DAP for conjunctive RAS presented in "Polynomial-complexity deadlock avoidance policies for sequential resource allocation systems"
• scientific article; zbMATH DE number 1836367 (Why is no real title available?)
• On the Complexity of Maximally Permissive Deadlock Avoidance in Multi-Vehicle Traffic Systems
• Generalized Algebraic Deadlock Avoidance Policies for Sequential Resource Allocation Systems

This page was built for publication: On the optimality of randomized deadlock avoidance policies

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1412282)