Efficient siphon-based deadlock detection in Petri nets

Craig, D.C. and Zuberek, W.M.

3-rd Int. Conf. on Computer Science and Information Systems, Athens, Greece, 23-25 July 2007.

Abstract:

Absence of deadlocks is critical in systems which are required to operate in a continuous way, such as life-support systems, supervisory control systems (e.g., in a nuclear plant), transportation control systems, and so on. Efficient methods of deadlock detection are of primary importance for such systems. A structural approach to deadlock detection in Petri nets, based on a reduced number of minimal and basis siphons, is proposed in this paper.

Keywords:

Petri nets, deadlock detection, structural methods, minimal siphons, basis siphons, linear programming.

References:

• B. Bordbar, K. Okano, "Testing deadlock-freeness in real-time systems: a formal approach"; in Formal Approaches to Software Testing (Lecture Notes in Computer Science 3395) pp.95-109, 2004.
• E.T. Boer, T. Murata, "Generating basis siphons and traps of Petri nets using the sign incidence matrix"; IEEE Trans. on Circuits and Systems, I - Fundamental Theory and Applications, vol.41, no.4, pp.266-271, 1994.
• F. Chu, X. Xie, "Deadlock analysis of Petri nets using siphons and mathematical programming"; IEEE Trans. on Robotics and Automation, vol.13, no.6, pp.793-804, 1997.
• J. Ezpeleta, J.M. Colombo, J. Martinez, "A Petri net based deadlock prevention policy for flexible manufacturing systems"; IEEE Trans. on Robotics and Automation, vol.11, no.2, pp.173-184, 1995.
• D.C. Craig, "Compatibility of software components - modeling and verification"; Ph.D. Thesis, Department of Computer Science, Memorial University, St.John's, Canada A1B 3X5, 2006.
• M. Hack, "Analysis of production schemata by Petri nets"; Project MAC Technical Report TR-94, 1972.
• T. Murata, "Petri nets: properties, analysis, and applications"; Proceedings of the IEEE, vol.77, no.4, pp.541-580, 1989.
• W. Reisig, Petri nets - an introduction (EATCS Monographs on Theoretical Computer Science 4); Springer-Verlag 1985.
• M. Silva, E. Teruel, J. Couvreur, "Linear algebra in and linear programming techniques for the analysis of place/transition net systems"; in Lectures on Petri nets - basic models (Lecture Notes in Computer Science 1491), pp.309-373, Springer-Verlag 1998.
• S. Tanimoto, M. Yamaguchi, T. Watanabe, "Finding minimal siphons in general Petri nets"; IEICE Trans. on Fundamentals in Electronics, Communications, and Computer Science, vol.E79-A, no.11, pp.1817-1824, 1996.

Available in pdf and postscript.