Abstract
Stochastic Petri Nets are a modelling formalism that can be conveniently used for the analysis of complex models of Discrete Event Dynami Systems (DEDS) and for their performance and reliability evaluation. The automatic construction of the probabilistic models that underly the dynamic behaviours of these nets rely on a set of results that derive from the theory of untimed Petri nets. The paper introduces the basic motivations for modelling DEDS and briefly overviews the basic results of net theory that are useful for the definition of Stochastic Petri Nets and Generalized Stochastic Petri Nets. The different approaches that have been used for introducing the concept of time in these models are discussed in order to provide the basis for the definition of SPNs and GSPNs as well. Details on the solution techniques and on ntheir computational aspects are provided. A brief overview of more advanced material is included at the end of the paper to highlight the state of the art in this field and to give pointers to relevant results published in the literature.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
T. Agerwala. Putting Petri nets to work. IEEE Computer, pages 85–94, December 1979.
M. Ajmone Marsan, G. Balbo, A. Bobbio, G. Chiola, G. Conte, and A. Cumani. The effect of execution policies on the semantics and analysis of stochastic Petri nets. IEEE Transactions on Software Engineering, 15(7):832–846, July 1989.
M. Ajmone Marsan, G. Balbo, G. Chiola, and G. Conte. Generalized stochastic Petri nets revisited: Random switches and priorities. In Proc. Intern. Workshop on Petri Nets and Performance Models, pages 44–53, Madison, WI, USA, August 1987. IEEE-CS Press.
M. Ajmone Marsan, G. Balbo, and G. Conte. A class of generalized stochastic Petri nets for the performance analysis of multiprocessor systems. ACM Transactions on Computer Systems, 2(1), May 1984.
M. Ajmone Marsan, G. Balbo, and G. Conte. Performance Models of Multiprocessor Systems. MIT Press, Cambridge, USA, 1986.
M. Ajmone Marsan, G. Balbo, G. Conte, S. Donatelli, and G. Franceschinis. Modelling with Generalized Stochastic Petri Nets. J. Wiley, 1995.
M. Ajmone Marsan, G. Balbo, and K.S. Trivedi, editors. Proc. Intern. Workshop on Timed Petri Nets, Torino, Italy, July 1985. IEEE-CS Press.
M. Ajmone Marsan and G. Chiola. On Petri nets with deterministic and exponential transition firing times. In Proc. 7 th European Workshop on Application and Theory of Petri Nets, pages 151–165, Oxford, England, June 1986.
H. Alaiwan and G. Memmi. Algorithmes de recherche des solutions entieres positives d’un systeme d’equations lineaires homogeneus en nombres entieres. Revue Technique Thomson-CSF, 14(1):125–135, March 1982. in French.
H. Alaiwan and J.M. Toudic. Research des semiflots, des verrous et des trappes dans le reseaux de Petri. Technique et Science Informatiques, 4(1), February 1985.
H.H. Ammar and S.M. Rezaul Islam. Time scale decomposition of a class of generalized stochastic Petri net models. IEEE Transactions on Software Engineering, 15(6):809–820, June 1989.
G. Balbo, M. Silva, editors. Performance Models for Discrete Event Systems with Synchronizations: Formalisms and Analysis Techniques. KRONOS, Zaragoza, Spain, 1998.
G. Berthelot. Transformations and decompositions of nets. In W. Brauer, W. Reisig, and G. Rozenberg, editors, Advances in Petri Nets’ 86-Part I, volume 254 of LNCS, pages 359–376. Springer Verlag, Bad Honnef, West Germany, February 1987.
E. Best, R. Devillers, and J. Hall. The Petri box calculus: a new causal algebra with multilabel communication. In G. Rozenberg, editor, Advances in Petri Nets, volume 609 of LNCS, pages 21–69. Springer Verlag, 1992.
A. Blakemore. The cost of eliminating vanishing markings from generalized stochastic Petri nets. In Proc. 3 rd Intern. Workshop on Petri Nets and Performance Models, Kyoto, Japan, December 1989. IEEE-CS Press.
A. Blakemore and S.K. Tripathi. Automated time scale decomposition and analysis of stochastic Petri nets. In Proc. 5 th Intern. Workshop on Petri Nets and Performance Models, pages 248–257, Toulouse, France, October 1993. IEEE-CS Press.
R.J. Boucherie. A characterization of independence for competing Markov chains with applications to stochastic Petri nets. In Proc. 5 th Intern. Workshop on Petri Nets and Performance Models, pages 117–126, Toulouse, France, October 1993. IEEE-CS Press.
P. Buchholz. Hierarchical high level Petri nets for complex system analysis. In Proc. 15 th Intern. Conference on Applications and Theory of Petri Nets, number 185 in LNCS, Zaragoza, Spain, 1994. Springer-Verlag.
Moler C. and C. Van Loan. Nineteen doubious ways to compute the exponential of a matrix. SIAM Review, 20(4):801–836, 1978.
P. Chen, S.C. Bruell, and G. Balbo. Alternative methods for incorporating nonexponential distributions into stochastic Petri nets. In Proc. 3 rd Intern. Workshop on Petri Nets and Performance Models, pages 187–197, Kyoto, Japan, December 1989. IEEE-CS Press.
G. Chiola, M. Ajmone Marsan, G. Balbo, and G. Conte. Generalized stochastic Petri nets: A definition at the net level and its implications. IEEE Transactions on Software Engineering, 19(2):89–107, February 1993.
G. Chiola, S. Donatelli, and G. Franceschinis. GSPN versus SPN: what is the actual role of immediate transitions? In Proc. 4 th Intern. Workshop on Petri Nets and Performance Models, pages 20–31, Melbourne, Australia, December 1991. IEEECS Press.
G. Chiola, S. Donatelli, and G. Franceschinis. Priorities, inhibitor arcs, and concurrency in P/T nets. In Proc. 12 th Intern. Conference on Application and Theory of Petri Nets, Aarhus, Denmark, June 1991.
G. Chiola, C. Dutheillet, G. Franceschinis, and S. Haddad. Stochastic Well-Formed coloured nets for symmetric modelling applications. IEEE Transactions on Computers, 42(11), November 1993.
G. Chiola and G. Franceschinis. Colored GSPN models and automatic symmetry detection. In Proc. 3 rd Intern. Workshop on Petri Nets and Performance Models, Kyoto, Japan, December 1989. IEEE-CS Press.
G. Chiola, G. Franceschinis, R. Gaeta, and M. Ribaudo. GreatSPN1.7: GRaphical Editor and Analyzer for Timed and Stochastic Petri Nets. Performance Evaluation, 24, 1995. Special Issues on Performance Modelling Tools.
H. Choi, G. Kulkarni, and K.S. Trivedi. Transient analysis of deterministic and stochastic petri nets. In Proc. 14 th Intern. Conference on Application and Theory of Petri Nets, Chicago, Illinois, June 1993. Springer Verlag.
H. Choi, V.S. Kulkarni, and K.S. Trivedi. Markov regenerative stochastic Petri nets. In Proc. of Performance 93, Rome, Italy, September 1993.
G. Ciardo. Analysis of large Petri net models. PhD thesis, Department of Computer Science, Duke University, Durham, NC, USA, 1989. Ph. D. Thesis.
G. Ciardo, R. German, and C. Lindemann. A characterization of the stochastic process underlying a stochastic Petri net. In Proc. 5 th Intern. Workshop on Petri Nets and Performance Models, pages 170–179, Toulouse, France, October 1993. IEEE-CS Press.
G. Ciardo and C. Lindemann. Analysis of deterministic and stochastic Petri nets. In Proc. 5 th Intern. Workshop on Petri Nets and Performance Models, pages 160–169, Toulouse, France, October 1993. IEEE-CS Press.
J.E. Coolhan and N. Roussopoulos. Timing requirements for time-driven systems using augmented Petri nets. In Proc. Intern. Workshop on Timed Petri Nets, Torino, Italy, July 1985. IEEE-CS Press.
P.J. Courtois. Decomposability: Queueing and Computer Systems Applications. Academic Press, New York, 1977.
S. Donatelli. L’uso delle reti di Petri per la valutazione e la validazione di sistemi di grandi dimensioni. PhD thesis, Dipartimento di Informatica, Università di Torino, Corso Svizzera 185, 10149, Torino, Italy, February 1990. (in Italian).
J.B. Dugan, K.S. Trivedi, R.M. Geist, and V.F. Nicola. Extended stochastic Petri nets: Applications and analysis. In Proc. PERFORMANCE’ 84, Paris, France, December 1984.
C. Dutheillet and S. Haddad. Aggregation and disaggregation of states in colored stochastic Petri nets: Application to a multiprocessor architecture. In Proc. 3 rd> Intern. Workshop on Petri Nets and Performance Models, Kyoto, Japan, December 1989. IEEE-CS Press.
G. Florin and S. Natkin. Les reseaux de Petri stochastiques. Technique et Science Informatiques, 4(1), February 1985.
G. Florin and S. Natkin. Matrix product form solution for closed synchronized queueing networks. In Proc. 3 rd Intern. Workshop on Petri Nets and Performance Models, pages 29–39, Kyoto, Japan, December 1989. IEEE-CS Press.
R. German and C. Lindemann. Analysis of stochastic Petri nets by the method of supplementary variables. In Proc. of Performance 93, Rome, Italy, September 1993.
P.J. Haas and G.S. Shedler. Regenerative stochastic Petri nets. Performance Evaluation, 6(3):189–204, September 1986.
P.J. Haas and G.S. Shedler. Regenerative simulation of stochastic Petri nets. In Proc. Intern. Workshop on Timed Petri Nets, Torino, Italy, July 1985. IEEE-CS Press.
W. Henderson and D. Lucic. Exact results in the aggregation and disaggregation of stochastic Petri nets. In Proc. 4 th Intern. Workshop on Petri Nets and Performance Models, pages 166–175, Melbourne, Australia, December 1991. IEEE-CS Press.
W. Henderson and P.G. Taylor. Aggregation methods in exact performance analysis of stochastic Petri nets. In Proc. 3 rd Intern. Workshop on Petri Nets and Performance Models, pages 12–18, Kyoto, Japan, December 1989. IEEE-CS Press.
M.A. Holliday and M.K. Vernon. A generalized timed Petri net model for performance analysis. In Proc. Intern. Workshop on Timed Petri Nets, Torino, Italy, July 1985. IEEE-CS Press.
K. Lautenbach. Linear algebraic technique for place/transition nets. In W. Brawer, W. Reisig, and G. Rozenberg, editors, Advances on Petri Nets’ 86-Part I, volume 254 of LNCS, pages 142–167. Springer Verlag, Bad Honnef, West Germany, February 1987.
A.A. Lazar and T.G. Robertazzi. Markovian Petri net protocols with product form solution. Performance Evaluation, 12:67–77, 1991.
C. Lin and D.C. Marinescu. On stochastic high level Petri nets. In Proc. Intern. Workshop on Petri Nets and Performance Models, Madison, WI, USA, August 1987. IEEE-CS Press.
V. Mainkar, H. Choi, and K. Trivedi. Sensitivity analysis of Markov regenerative stochastic Petri nets. In Proc. 5 th Intern. Workshop on Petri Nets and Performance Models, Toulouse, France, October 1993. IEEE-CS Press.
J. Martinez and M. Silva. A simple and fast algorithm to obtain all invariants of a generalized Petri net. In Proc. 2 nd European Workshop on Application and Theory of Petri Nets, Bad Honnef, West Germany, September 1981. Springer Verlag.
P.M. Merlin and D.J. Farber. Recoverability of communication protocols: Implications of a theoretical study. IEEE Transactions on Communications, 24(9):1036–1043, September 1976.
J.F. Meyer, A. Movaghar, and W.H. Sanders. Stochastic activity networks: Structure, behavior, and application. In Proc. Intern. Workshop on Timed Petri Nets, pages 106–115, Torino,Italy, July 1985.
R. Milner. Communication and concurrency. Prentice Hall, 1989.
M.K. Molloy. On the Integration of Delay and Throughput Measures in Distributed Processing Models. PhD thesis, UCLA, Los Angeles, CA, 1981. Ph.D. Thesis.
M.K. Molloy, T. Murata, and M.K. Vernon, editors. Proc. Intern. Workshop on Petri Nets and Performance Models, Madison, Wisconsin, August 1987. IEEE-CS Press.
T. Murata. Petri nets: properties, analysis, and applications. Proceedings of the IEEE, 77(4):541–580, April 1989.
S. Natkin. Les Reseaux de Petri Stochastiques et leur Application a l’Evaluation des Systemes Informatiques. PhD thesis, CNAM, Paris, France, 1980. These de Docteur Ingegneur.
M.F. Neuts. Matrix Geometric Solutions in Stochastic Models. Johns Hopkins University Press, Baltimore, MD, 1981.
J.D. Noe and G.J. Nutt. Macro e-nets representation of parallel systems. IEEE Transactions on Computers, 31(9):718–727, August 1973.
J.L. Peterson. Petri Net Theory and the Modeling of Systems. Prentice-Hall, Englewood Cliffs, NJ, 1981.
C.A. Petri. Communication with automata. Technical Report RADC-TR-65-377, Rome Air Dev. Center, New York, NY, 1966.
C.V. Ramamoorthy and G.S. Ho. Performance evaluation of asynchronous concurrent systems using Petri nets. IEEE Transactions on Software Engineering, 6(5):440–449, September 1980.
C. Ramchandani. Analysis of Asynchronous Concurrent Systems by Timed Petri Nets. PhD thesis, MIT, Cambridge, MA, 1974. Ph.D. Thesis.
W. Reisig. Petri Nets: an Introduction. Springer Verlag, 1985.
T.G. Robertazzi. Computer Networks and Systems: Queueing Theory and Performance Evaluation. Springer Verlag, 1991.
J. Sifakis. Petri nets for performance evaluation. In H. Beilner and E. Gelenbe, editors, Proc. 3 rd Intern. Symp. IFIP, pages 75–93, 1978.
H.A. Simon and A. Ando. Aggregation of variables in dynamic systems. Econometrica, 29, 1961.
W.J. Stewart. Introduction to the Numerical Solution of Markov Chains. Princeton University Press, Princeton, New Jersey, USA, 1994.
F.J.W. Symons. Introduction to numerical Petri nets, a general graphical model of concurrent processing systems. Australian Telecommunications Research, 14(1):28–33, January 1980.
R.S. Varga. Matrix Iterative Analysis. Prentice-Hall, Englewood Cliffs, NJ, 1962.
C.Y. Wong, T.S. Dillon, and K.E. Forward. Timed places Petri nets with stochastic representation of place time. In Proc. Intern. Workshop on Timed Petri Nets, Torino, Italy, July 1985. IEEE-CS Press.
W.M. Zuberek. Timed Petri nets and preliminary performance evaluation. In Proc. 7 th Annual Symposium on Computer Architecture, pages 88–96, La Baule, France, May 1980.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2001 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Balbo, G. (2001). Introduction to Stochastic Petri Nets. In: Brinksma, E., Hermanns, H., Katoen, JP. (eds) Lectures on Formal Methods and PerformanceAnalysis. EEF School 2000. Lecture Notes in Computer Science, vol 2090. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44667-2_3
Download citation
DOI: https://doi.org/10.1007/3-540-44667-2_3
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-42479-6
Online ISBN: 978-3-540-44667-5
eBook Packages: Springer Book Archive