×

Phase-type distributions in stochastic automata networks. (English) Zbl 1144.90338

Summary: Stochastic automata networks (Sans) are high-level formalisms for modeling very large and complex Markov chains in a compact and structured manner. To date, the exponential distribution has been the only distribution used to model the passage of time in the evolution of the different San components. In this paper we show how phase-type distributions may be incorporated into Sans thereby providing the wherewithal by which arbitrary distributions can be used which in turn leads to an improved ability for more accurately modeling numerous real phenomena.
The approach we develop is to take a San model containing phase-type distributions and to translate it into another, stochastically equivalent, San model having only exponential distributions. In the San formalism, it is the events that are responsible for firing transitions and our procedure is to associate a stochastic automaton with each event having a phase-type distribution. This automaton models the distribution of time until the event occurs. In this way, the size of the elementary matrices remain small, because the size of the automata are small: the automata are either those of the original San, or are those associated with the phase-type events and are of size \(k\), the number of phases in the representation of the distribution.

MSC:

90B18 Communication networks in operations research
60K25 Queueing theory (aspects of probability theory)

Software:

ESP; PEPS
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Ajmone Marsan, M.; Chiola, G., On Petri nets with deterministic and exponentially distributed firing times, (Rozenborg, G., Advances in Petri Nets 1987. Advances in Petri Nets 1987, LNCS, vol. 266 (1987), Springer-Verlag), 132-145
[2] A. Benoit, Méthodes et algorithmes pour l’Évaluation des performances des systèmes informatiques à grand espace d’États. Ph.D. thesis, INPG, Grenoble, France, Juin 2003.; A. Benoit, Méthodes et algorithmes pour l’Évaluation des performances des systèmes informatiques à grand espace d’États. Ph.D. thesis, INPG, Grenoble, France, Juin 2003.
[3] Benoit, A.; Brenner, L.; Fernandes, P.; Plateau, B.; Stewart, W. J., The PEPS Software Tool, (Performance TOOLS 2003, Urbana, Illinois, USA (2003), Springer-Verlag), 98-115
[4] Chen, P.; Bruell, S. C.; Balbo, G., Alternative methods for incorporating non-exponential distributions into stochastic timed Petri nets, (Proceedings of the third International Workshop on Petri Nets and Performance Models, Kyoto, Japan, December 11-13 (1989), IEEE Computer Society Press), 187-197
[5] Ciardo, G.; German, R.; Lindemann, C., A characterization of the stochastic process underlying a stochastic Petri net, (Proceedings of the 5th International Workshop on Petri Nets and Performance Models, Toulouse, France, October 19-22 (1993), IEE Computer Society Press), 170-179
[6] Cumani, A., ESP - a package for the evaluation of stochastic Petri nets with Phase-type distributed transition times, (Proceedings of the International Workshop on Timed Patri Nets, Torino, Italy, July 1-3 (1985), IEEE Computer Society Press), 144-151
[7] Donatelli, S.; Haddad, S.; Moreaux, P., Structured characterization of the Markov chains of phase-type SPN, (Proceedings of the 10th International Conference on Computer Performance Evaluation. Modelling Techniques and Tools (TOOLS’98), Palma de Mallorca, Spain, September 14-18. Proceedings of the 10th International Conference on Computer Performance Evaluation. Modelling Techniques and Tools (TOOLS’98), Palma de Mallorca, Spain, September 14-18, LNCS, vol. 1469 (1998), Springer-Verlag), 243-254
[8] P. Fernandes, Méthodes numériques pour la solution de systèmes Markoviens à grand espace d’États. Ph.D. thesis, INPG, Grenoble, France, 1998.; P. Fernandes, Méthodes numériques pour la solution de systèmes Markoviens à grand espace d’États. Ph.D. thesis, INPG, Grenoble, France, 1998.
[9] Haddad, S.; Moreaux, P.; Chiola, G., Efficient handling of phase-type distributions in generalized stochastic Petri nets, (Proceedings of the 18th International Conference on Application and Theory of Petri Nets, Toulouse, France, June 23-27. Proceedings of the 18th International Conference on Application and Theory of Petri Nets, Toulouse, France, June 23-27, LNCS, vol. 1248 (1997), Springer-Verlag), 175-194 · Zbl 1510.68059
[10] M.K. Molloy, On the integration of delay and throughput in distributed processing models, Ph.D. dissertation, University of California, Los Angeles, CA, USA, September 1981.; M.K. Molloy, On the integration of delay and throughput in distributed processing models, Ph.D. dissertation, University of California, Los Angeles, CA, USA, September 1981.
[11] Neuts, M. F.; Meier, K. S., On the use of phase type distributions in reliability modeling of systems with a small number of components, OR Spectrum, 2, 227-234 (1981) · Zbl 0463.60073
[12] B. Plateau, On the stochastic structure of parallelism and synchronization models for distributed algorithms, in: Proceedings of the SIGMETRICS Conference, Texas, 1985, pp. 147-154.; B. Plateau, On the stochastic structure of parallelism and synchronization models for distributed algorithms, in: Proceedings of the SIGMETRICS Conference, Texas, 1985, pp. 147-154.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.