On generation of state space for timed Petri nets

Zuberek, W.M.

Proc. ACM 16-th Annual Computer Science Conference (CSC'88); Atlanta, GA, February 1988, pp.239-248.

Abstract:

It is shown that the behavior of timed Petri nets with deterministic firing (D-timed Petri nets) and nets with exponentially distributed firing times (M-timed nets) can be described within one uniform formalism. Moreover, for both classes of nets the state spaces are homogeneous semi-Markov chains, the stationary probabilities of states and many performance measures can thus be obtained by standard techniques developed for analysis of Markov processes. Because of sparsity of nets as well as corresponding systems of equilibrium equations, list structure representations are proposed, and a general procedure for generation of the state space is outlined to show the required processing of list structures.

Keywords:

Timed Petri nets, state space generation, Markov processes, Markov chains, stationary probabilities.

References:

• T. Agerwala, "Putting Petri nets to work"; IEEE Computer, vol.12, no.12, pp.85-94, 1979.
• M. Ajmone Marsan, G. Conte, G. Balbo, "A class of generalized stochastic Petri nets for the performance evaluation of multiprocessor systems"; ACM Trans. on Computer Systems, vol.2, no.2, pp.93-122, 1984.
• W. Brauer, W. Reisig, G. Rozenberg (eds.), Advances in Petri Nets 1986 (vol.1: "Petri nets - central models and their properties", vol.2: "Petri nets - applications and relationship to other models of concurrency"); Proc. of the Advanced Course, Bad Honnef, 1986; Lecture Notes in Computer Science 254 and 255, Springer-Verlag 1987.
• J.P. Buzen, "Fundamental operational laws of computer system performance"; Acta Informatica, vol.7, no.2, pp.167-182, 1976.
• J.B. Dugan, K.S. Trivedi, R.M. Geist, V.F. Nicola, "Extended stochastic Petri nets - applications and analysis"; Performance'84, E. Gelenbe (ed.), pp.507-519, Elsevier 1984.
• J.B. Dugan, A. Bobbio, G. Ciardo, K. Trivedi, "The design of a unified package for the solution of stochastic Petri net models"; Proc. Int. Workshop on Timed Petri Nets, Torino, Italy, pp.6-13, 1985.
• M.A. Holliday, M.K. Vernon, "A generalized timed Petri net model for performance evaluation"; Proc. Int. Workshop on Timed Petri Nets, Torino, Italy, pp.181-190, 1985.
• R. Janicki, P.E. Lauer, M. Koutny, R. Devillers, "Concurrent and maximally concurrent evolution of nonsequential systems"; Theoretical Computer Science, vol.43, pp.213-238, 1986.
• L. Kleinrock, Queueing systems, vol.1: "Theory", vol.2: "Computer applications"; J. Wiley & Sons 1975, 1976.
• P.M. Merlin, D.J. Farber, "Recoverability of communication protocols - implications of a theoretical study"; IEEE Trans. on Communications, vol.24, no.9, pp.1036-1049, 1976.
• M.K. Molloy, "Performance analysis using stochastic Petri nets"; IEEE Trans. on Computers, vol.31, no.9, pp.913-917, 1982.
M.T. Ozsu, "Modeling and analysis of distributed database concurrency control algorithms using an extended Petri net formalism"; IEEE Trans. Software Engineering, vol.11, no.10, pp.1225-1240, 1985.
• 13. J.L. Peterson, Petri net theory and the modeling of systems; Prentice-Hall 1981.
• C. Ramchandani, "Analysis of asynchronous concurrent systems by timed Petri nets"; Project MAC Technical Report MAC-TR-120, Massachusetts Institute of Technology, Cambridge MA, 1974.
• R.R. Razouk, "The derivation of performance expressions for communication protocols from timed Petri nets"; Computer Communication Review, vol.14, no.2, pp.210-217, 1984.
• R.R. Razouk, D.S. Hirschberg, "Tools for efficient analysis of concurrent software systems"; Proc. SOFTFAIR II - Second Conf. on Software Development Tools, Techniques and Alternatives, San Francisco CA, pp.192-198, 1985.
• W. Reisig, Petri nets - an introduction; Springer-Verlag 1985.
• G. Rozenberg (ed.), Advances in Petri Nets 1987 (Lecture Notes in Computer Science 266); Springer-Verlag 1987.
• J. Sifakis, "Use of Petri nets for performance evaluation"; in Measuring, modelling and evaluating computer systems, pp.75-93, North-Holland 1977.
• A.A. Torn, "Simulation nets, a simulation, modelling and validation tool"; Simulation Journal, vol.45, no.2, pp.71-75, 1985.
• W.M. Zuberek, "M-timed Petri nets, priorities, preemptions, and performance evaluation of systems"; in Advances in Petri Nets 1985 (Lecture Notes in Computer Science 222), G. Rozenberg (ed.), pp.478-498, Springer-Verlag 1986.
• W.M. Zuberek, "Inhibitor D-timed Petri nets and performance analysis of communication protocols"; INFOR Journal, vol.24, no.3, pp.231-249, 1986.

Available in pdf and postscript.