In: Proceedings of the 24th International Conference on Applications and Theory of Petri Nets (ICATPN 2003), Eindhoven, The Netherlands, June 23-27, 2003, pages 241-255. Volume 2679 of Lecture Notes in Computer Science / Wil M. P. van der Aalst and Eike Best (Eds.) --- Springer-Verlag, June 2003.
Abstract: One of the most interesting developments from, both, a theoretical and a practical perspective, in the emerging theory of resource allocation systems (RAS), is the characterization of the non-liveness of many RAS classes through the Petri net (PN)-based structural object of empty, or more generally, deadly marked siphon. The work presented in this paper seeks to develop a general theory that provides a unifying framework for all the relevant existing results, and reveals the key structures and mechanisms that connect the RAS non-liveness to the concept of deadly marked - and in certain cases, empty - siphon. By taking this generalizing approach, the developed results allow also the extension of the siphon-based characterization of non-liveness to broader RAS classes, and provide a clear and intuitive explanation for the cases where the RAS non-liveness cannot be attributed to such a siphon-based construct.
Keywords: sequential resource allocation systems; deadlock resolution; Petri net structural analysis; siphons.