On generation of state space for timed Petri nets

ABSTRACT

It is shown that the behavior of timed Petri nets with deterministic firing times (D-timed nets) and with exponentially distributed random 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 scarcity 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.

REFERENCES

• 1: T. Agerwala, "Putting Petri nets to work"; IEEE Computer, vol.12, no.12, pp.85-94, 1979.
• 2: Marco Ajmone Marsan , Gianni Conte , Gianfranco Balbo, A class of generalized stochastic Petri nets for the performance evaluation of multiprocessor systems, ACM Transactions on Computer Systems (TOCS), v.2 n.2, p.93-122, May 1984 [doi>10.1145/190.191]
• 3: W. Brauer, W. Reisig, G. Rozenberg (eds.), "Advances in Petri Nets 1986" (vol.l: "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 ~erlag 1987.
• 4: 3.P. Buzen, "Fundamental operational laws of computer system performance"; Acta Information, vol.7, no.2, pp.167-182, 1976.
• 5: Joanne Bechta Dugan , Kishor S. Trivedi , Robert Geist , Victor F. Nicola, Extended Stochastic Petri Nets: Applications and Analysis, Proceedings of the Tenth International Symposium on Computer Performance Modelling, Measurement and Evaluation, p.507-519, December 19-21, 1984
• 6: Joanne Bechta Dugan , Andrea Bobbio , Gianfranco Ciardo , Kishor S. Trivedi, The Design of a Unified Package for the Solution of Stochastic Petri Net Models, International Workshop on Timed Petri Nets, p.6-13, July 01-03, 1985
• 7: Mark A. Holliday , Mary K. Vernon, A Generalized Timed Petri Net Model for Performance Analysis, International Workshop on Timed Petri Nets, p.181-190, July 01-03, 1985
• 8: R Janicki , P E Lauer , M Kounty , R Devillers, Concurrent and maximally concurrent evolution of nonsequential systems, Theoretical Computer Science, v.43 n.2-3, p.213-238, July 1986
• 9: L. Kleinrock, "Queueing systems", vol.l: "Theory", vol.2: "Computer applications"; J. Wiley & Sons 1975, 1976.
• 10: P.M. Merlin, D.J. Farber, "Recoverability of communication protocols- implications of a theoretical study"; IEEE Trans. on Communications, vol.24, no.0, pp.103~-1049, 1976.
• 11: M.K. Molloy, "Performance analysis using stochastic Petri nets"; IEEE Trans. on Computers, vol.31, no.9, pp.913-917, 1982.
• 12: M. T. Ozsu, Modeling and analysis of distributed database concurrency control algorithms using an extended petri net formalism, IEEE Transactions on Software Engineering, v.11 n.10, p.1225-1240, Oct. 1985 [doi>10.1109/TSE.1985.231870]
• 13: James Lyle Peterson, Petri Net Theory and the Modeling of Systems, Prentice Hall PTR, Upper Saddle River, NJ, 1981
• 14: C. Ramchandani, ANALYSIS OF ASYNCHRONOUS CONCURRENT SYSTEMS BY TIMED PETRI NETS, Massachusetts Institute of Technology, Cambridge, MA, 1974
• 15: Rami R. Razouk, The derivation of performance expressions for communication protocols from timed petri net models, ACM SIGCOMM Computer Communication Review, v.14 n.2, p.210-217, June 1984
• 16: Rami R. Razouk , Daniel S. Hirschberg, Tools for efficient analysis of conurrent software systems, Proceedings of the second conference on Software development tools, techniques, and alternatives, p.192-198, December 1985, San Francisco, California, United States
• 17: Wolfgang Reisig, Petri nets: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• 18: G. Rozenberg, Advances in Petri Nets 1984, Springer-Verlag, London, 1985
• 19: Joseph Sifakis, Use of Petri Nets for Performance Evaluation, Proceedings of the Third International Symposium on Measuring, Modelling and Evaluating Computer Systems, p.75-93, October 03-05, 1977
• 20: A.A. Torn, "Simulation nets, a simulation, modelling and validation tool"; Simulation Journal, vo1.45, no.2, pp.71-75~ 1985.
• 21: Wlodzimierz M. Zuberek, M-timed Petri nets, priorities, preemptions, and performance evaluation of Petri nets, Advances in Petri Nets 1985, covers the 6th European Workshop on Applications and Theory in Petri Nets-selected papers, p.478-498, June 01, 1985
• 22: W.M. Zuberek, "Inhibitor D-timed Petri nets and performance analysis of communication protocols"; INFOR Journal, vol.24, no.3, pp.231-249, 1986.
• 23: W.M. Zuberek, "TPNEV, an interactive program for evaluation of timed Petri nets"; Technical Report, Department of Computer Science, Memorial University of Newfoundland, St. John's, Canada AIC 5S7 (in preparation).

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.2 Design Tools and Techniques
          Subjects: Petri nets

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Network problems
  G.3 PROBABILITY AND STATISTICS
      Subjects: Markov processes

General Terms:
Design, Measurement, Performance, Theory