Revisiting deadlock prevention: a probabilistic approach

DOI10.1002/NET.21537MaRDI QIDQ4639696zbMATH OpenOpenAlexFDO

Authors Valmir C. Barbosa, Fabiano de S. Oliveira

Publication date 11 May 2018

Published in Networks (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1010.4411

zbMATH Keywords

deadlock preventionpriority digraphsprobabilistic algorithmsrandom graphs

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) Combinatorial probability (60C05)

Abstract: We revisit the deadlock-prevention problem by focusing on priority digraphs instead of the traditional wait-for digraphs. This has allowed us to formulate deadlock prevention in terms of prohibiting the occurrence of directed cycles even in the most general of wait models (the so-called AND-OR model, in which prohibiting wait-for directed cycles is generally overly restrictive). For a particular case in which the priority digraphs are somewhat simplified, we introduce a Las Vegas probabilistic mechanism for resource granting and analyze its key aspects in detail.

Recommendations

• Random Resource Allocation Graphs and the Probability of Deadlock
• Deadlock prevention with collectively occupied resources
• Deadlock-freedom in resource contentions
• scientific article; zbMATH DE number 4045096
• Deadlock resolution in wait-for graphs by vertex/arc deletion

Cited in

(4)

• Robustness of deadlock avoidance algorithms for sequential processes.
• And/or-convexity: a graph convexity based on processes and deadlock models
• Deadlock prevention policy with behavioral optimality or suboptimality achieved by the redundancy identification of constraints and the rearrangement of monitors
• Random Resource Allocation Graphs and the Probability of Deadlock

This page was built for publication: Revisiting deadlock prevention: a probabilistic approach

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