Resolution techniques and complexity results with deadlocks: a classifying and annotated bibliography
Dieter Zöbel, Christoph E. Koch · ACM SIGOPS Operating Systems Review · 1988
Resolution techniques and complexity results with Deadlocks A Classifying and Annotated BibliographyResource sharing was a basic concept of multiprocessing.But this kind of improved utilization of resources introduced the danger of eternal delays.The problem is inherited from the strategy that processes may exclusively hold resources and acquire resources in the sequel of processing.This phenomenon first discovered in operating systems has been named deadlock.For almost twenty years a lot of articles considering deadlocks and related problems have been published.In the meantime the analogous phenomena were discovered and discussed for the resource management in databases, for routing in communication networks and for the safety of communication protocols, that is to say, in the context of distributed systems.In theoretical computer science deadlock situations are analysed for Petri nets, communicating finite-state machines and recently for VLSI-design.The hardness of the problem varies with the underlying models and may range from sublinearity to NP-completeness or even undecidability.A similar variety exists for the host problems where the deadlock problem is mapped to.They can be found in elementary arithmetic, algebra, graph theory, logic etc.This article intends to give a classification of our collected publications.We do not claim that this collection is complete in any sense, but we hope to present the essential articles for nearly all the different topics fitting under the title "Deadlock".This is already our second paper on this theme.The first one was published in 1983 and was primarily oriented to the original environments of the deadlock problem: operating systems and database systems.Meanwhile we could notice a still increasing theortical orientation of the recently published papers