Hostname: page-component-78c5997874-s2hrs Total loading time: 0 Render date: 2024-11-09T14:52:29.318Z Has data issue: false hasContentIssue false

Stochastic Petri Nets: Modeling Power and Limit Theorems

Published online by Cambridge University Press:  27 July 2009

Peter J. Haas
Affiliation:
IBM Research Division Almaden Research Center San Jose, California 95120-6099
Gerald S. Shedler
Affiliation:
IBM Research Division Almaden Research Center San Jose, California 95120-6099

Abstract

Generalized semi-Markov processes and stochastic Petri nets provide building blocks for specification of discrete event system simulations on a finite or countable state space. The two formal systems differ, however, in the event scheduling (clock-setting) mechanism, the state transition mechanism, and the form of the state space. We have shown previously that stochastic Petri nets have at least the modeling power of generalized semi-Markov processes. In this paper we show that stochastic Petri nets and generalized semi-Markov processes, in fact, have the same modeling power. Combining this result with known results for generalized semi-Markov processes, we also obtain conditions for time-average convergence and convergence in distribution along with a central limit theorem for the marking process of a stochastic Petri net.

Type
Articles
Copyright
Copyright © Cambridge University Press 1991

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Ajmone, Marsan M., Conte, G., & Balbo, G. (1984). A class of generalized stochastic Petri nets for the performance evaluation of multiprocessor systems. ACM Transactions on Computer Systems 2: 93122.CrossRefGoogle Scholar
Asmussen, S. (1987). Applied probability and queues. New York: Wiley.Google Scholar
Dugan, J.B., Trivedi, K.S., Geist, R.M., & Nicola, V.F. (1984). Extended stochastic Petri nets: Applications and analysis. Performance 84: 419441.Google Scholar
Glynn, P.W. (1983). On the role of generalized semi-Markov processes in simulation output analysis. Proceedings of the ACM 1983 Winter Simulation Conference, pp. 3942.Google Scholar
Haas, P.J. & Shedler, G.S. (1985). Regenerative simulation methods for local area computer networks. IBM Journal of Research and Development 29: 194205.CrossRefGoogle Scholar
Haas, P.J. & Shedler, G.S. (1987). Regenerative generalized semi-Markov processes. Communications in Statistics: Stochastic Models 3: 409438.Google Scholar
Haas, P.J. & Shedler, G.S. (1988). Modeling power of stochastic Petri nets for simulation. Probability in the Engineering and Informational Sciences 2: 435459.CrossRefGoogle Scholar
Haas, P.J. & Shedler, G.S. (1989). Stochastic Petri net representation of discrete event simulations. IEEE Transactions on Software Engineering 15: 381393.CrossRefGoogle Scholar
Haas, P.J. & Shedler, G.S. (1989). Stochastic Petri nets with timed and immediate transitions. Communications in Statistics: Stochastic Models 5: 563600. (Special issue devoted to Computer-Experimental Methods in Probability.)Google Scholar
Iglehart, D.L. & Shedler, G.S. (1983). Simulation of non-Markovian systems. IBM Journal of Research and Development 27: 472480.CrossRefGoogle Scholar
König, D., Matthes, K., & Nawrotzki, K. (1967). Verallgemeinerungen der Erlangschen und Engsetschen Formeln. Berlin: Akademie-Verlag.Google Scholar
König, D., Matthes, K., & Nawrotzki, K. (1974). Unempfindlichkeitseigenshaften von Bedienungsprozessen. Appendix to B.V. Gnedenko & I.N. Kovalenko, Introduction to queueing theory, German edition. Berlin: Akademie-Verlag.Google Scholar
Matthes, K. (1962). Zur Theorie der Bedienungsprozessen. Transactions of the 3rd Prague Conference on Information Theory and Statistical Decision Functions, Prague, Czechoslovakia.Google Scholar
Molloy, M.K. (1981). On the integration of delay and throughput measures in distributed processing models. Ph.D. dissertation, Department of Computer Science, University of California, Los Angeles.Google Scholar
Molloy, M.K. (1982). Performance analysis using stochastic Petri nets. IEEE Transactions on Computers C-31: 913917.CrossRefGoogle Scholar
Natkin, S. (1980). Les réseaux de Petri stochastiques et leur application à l'evaluation des systemes informatiques. Thèse de Docteur Ingénieur, Conservatoire National des Arts et Metier, Paris.Google Scholar
Orey, S. (1971). Lecture notes on limit theorems for Markov chain transition probabilities. London: Van Nostrand Reinhold.Google Scholar
Shedler, G.S. (1987). Regeneration and networks of queues. New York: Springer-Verlag.CrossRefGoogle Scholar
Sigman, K. (1990). One-dependent regenerative processes and queues in continuous time. Mathematics of Operations Research 15: 175189.CrossRefGoogle Scholar
Whitt, W. (1980). Continuity of generalized semi-Markov processes. Mathematics of Operations Research 5:494501.CrossRefGoogle Scholar