Skip to main content Accessibility help
×
Hostname: page-component-586b7cd67f-2brh9 Total loading time: 0 Render date: 2024-11-26T04:21:46.426Z Has data issue: false hasContentIssue false

15 - Phase-Type Expansion

from Part IV - State-Space Models with Non-Exponential Distributions

Published online by Cambridge University Press:  30 August 2017

Kishor S. Trivedi
Affiliation:
Duke University, North Carolina
Andrea Bobbio
Affiliation:
Università degli Studi del Piemonte Orientale, Italy
Get access

Summary

Image of the first page of this content. For PDF version, please use the ‘Save PDF’ preceeding this image.'
Type
Chapter
Information
Reliability and Availability Engineering
Modeling, Analysis, and Applications
, pp. 551 - 574
Publisher: Cambridge University Press
Print publication year: 2017

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

[1] D., Cox, “A use of complex probabilities in the theory of stochastic processes,Proceedings of the Cambridge Philosophical Society, vol. 51, pp. 313–319, 1955.Google Scholar
[2] D., Cox, “The analysis of non-Markovian stochastic processes by the inclusion of supplementary variables,Proceedings of the Cambridge Philosophical Society, vol. 51, pp. 433–440, 1955.Google Scholar
[3] R., Sahner, K., Trivedi, and A., Puliafito, Performance and Reliability Analysis of Computer Systems: An Example-based Approach Using the SHARPE Software Package. Kluwer Academic Publishers, 1996.
[4] M., Neuts, Matrix Geometric Solutions in Stochastic Models. Johns Hopkins University Press, 1981.
[5] D., Cox and H., Miller, The Theory of Stochastic Processes. Chapman and Hall, 1965.
[6] S., Asmussen, O., Nerman, and M., Olsson, “Fitting phase-type distributions via the EM algorithm,Scandinavian Journal of Statistics, vol. 23, no. 4, pp. 419–441, 1996.Google Scholar
[7] A., Horváth and M., Telek, “PhFit: A general phase-type fitting tool,” in Computer Performance Evaluation: Modelling Techniques and Tools, Lecture Notes in Computer Science, vol. 2324, eds. T., Field, P., Harrison, J., Bradley, and U., Harder. Springer, 2002, pp. 82–91.
[8] H., Okamura, T., Dohi, and K. S., Trivedi, “A refined EM algorithm for PH distributions,Performance Evaluation, vol. 68, no. 10, pp. 938–954, 2011.Google Scholar
[9] G., Horváth and M., Telek, “BuTools 2: a rich toolbox for Markovian performance evaluation,” in Valuetools 2016 - Conf. on Performance Evaluation Methodologies and Tools, 2016.
[10] A., Bobbio, A., Horváth, M., Scarpa, and M., Telek, “Acyclic discrete phase type distributions: Properties and a parameter estimation algorithm,Performance Evaluation, vol. 54, no. 1, pp. 1–32, 2003.Google Scholar
[11] C., O'Cinneide, “Characterization of phase-type distributions,Stochastic Models, vol. 6, no. 1, pp. 1–57, 1990.Google Scholar
[12] C., O'Cinneide, “On non-uniqueness of representations of phase-type distributions,Stochastic Models, vol. 5, pp. 247–259, 1989.Google Scholar
[13] C., Commault and J., Chemla, “On dual and minimal phase-type representations,Stochastic Models, vol. 9, pp. 421–434, 1993.Google Scholar
[14] T., Osogami and M., Harchol-Balter, “Closed form solutions for mapping general distributions to quasi-minimal PH distributions,Performance Evaluation, vol. 63, no. 6, pp. 524–552, 2006.Google Scholar
[15] G., Horváth and M., Telek, “On the canonical representation of phase-type distributions,Performance Evaluation, vol. 66, no. 8, pp. 396–409, 2009.Google Scholar
[16] A., Cumani, “On the canonical representation of homogeneous Markov processes modelling failure-time distributions,Microelectronics and Reliability, vol. 22, pp. 583–602, 1982.Google Scholar
[17] A., Bobbio and A., Cumani, “Markov models: A new class of distributions for the analysis of lifetime data samples,” in Proc. 4th EUREDATA Conf.. Paper 10.3/1–13, 1983.
[18] D., Aldous and L., Shepp, “The least variable phase type distribution is Erlang,Stochastic Models, vol. 3, pp. 467–473, 1987.Google Scholar
[19] D., Assaf and B., Levikson, “Closure of phase type distributions under operations arising in reliability theory,The Annals of Probability, vol. 10, pp. 265–269, 1982.Google Scholar
[20] R., Maier and C., O'Cinneide, “A closure characterisation of phase-type distributions,Journal of Applied Probability, vol. 29, no. 1, pp. 92–103, 1992.Google Scholar
[21] A., Bobbio and K. S., Trivedi, “Computation of the distribution of the completion time when the work requirement is a PH random variable,Stochastic Models, vol. 6, pp. 133–149, 1990.Google Scholar
[22] A., Bobbio and L., Roberti, “Distribution of the minimal completion time of parallel tasks in multi-reward semi-Markov models,Performance Evaluation, vol. 14, pp. 239–256, 1992.Google Scholar
[23] W., Bux and U., Herzog, “The phase concept: Approximation of measured data and performance analysis,” in Computer Performance, eds. K., Chandy and M., Reiser. North-Holland, 1977, pp. 23–38.
[24] C., Singh, R., Billinton, and S., Lee, “The method of stages for non-Markovian models,IEEE Transactions on Reliability, vol. R-26, pp. 135–137, 1977.Google Scholar
[25] M., Johnson and M., Taaffe, “Matching moments to phase distributions: Mixtures of Erlang distribution of common order,Stochastic Models, vol. 5, pp. 711–743, 1989.Google Scholar
[26] L., Schmickler, “MEDA: Mixed Erlang distributions as phase-type representations of empirical distribution functions,Stochastic Models, vol. 8, pp. 131–156, 1992.Google Scholar
[27] A., Bobbio and A., Cumani, “ML estimation of the parameters of a PH distribution in triangular canonical form,” in Computer Performance Evaluation, eds. G., Balbo and G., Serazzi. Elsevier Science Publishers, 1992, pp. 33–46.
[28] A., Bobbio and M., Telek, “A benchmark for PH estimation algorithms: Results for acyclic-PH,Stochastic Models, vol. 10, pp. 661–677, 1994.Google Scholar
[29] A., Bobbio, A., Horváth, and M., Telek, “PhFit: A general phase-type fitting tool,” in Proc. Int. Conf. on Dependable Systems and Networks, 2002, p. 543.Google Scholar
[30] M., Telek, “A tool for fitting distributions of phase type.” [Online]. Available: http://webspn.hit.bme.hu/∼telek/tools.htm
[31] A., Dempster, N., Laird, and D., Rubin, “Maximum likelihood from incomplete data via the EM algorithm,Journal of the Royal Statistical Society, vol. 39, pp. 1–38, 1977.Google Scholar
[32] A., Thumler, P., Buchholz, and M., Telek, “A novel approach for phase-type fitting with the EM algorithm,IEEE Transactions on Dependable and Secure Computing, vol. 3, pp. 245–258, 2006.Google Scholar
[33] M., Faddy, “Phase-type distributions for failure times,Mathematical and Computer Modelling, vol. 22, no. 10–12, pp. 63–70, 1995.Google Scholar
[34] A., Horváth and M., Telek, “Approximating heavy tailed behavior with phase type distributions,” in Proc. 3rd Int. Conf. on Matrix-Analytic Methods in Stochastic Models, MAM3. Notable Publications Inc, 2000, pp. 191–214.
[35] Y., Lu, A., Miller, R., Hoffmann, and C., Johnson, “Towards the automated verification of Weibull distributions for system failure rates,” in Proc. Int.Workshop on Formal Methods for Industrial Critical Systems and Automated Verification of Critical Systems (FMICS-AVoCS 2016), 2016.
[36] S., Distefano, F., Longo, and K. S., Trivedi, “Investigating dynamic reliability and availability through state-space models,Computers and Mathematics with Applications, vol. 64, no. 12, pp. 3701–3716, 2012.Google Scholar
[37] M., Neuts and K., Meier, “On the use of phase type distributions in reliability modelling of systems with two components,OR Spektrum, vol. 2, pp. 227–234, 1981.Google Scholar
[38] A., Bobbio and A., Cumani, “A Markov approach to wear-out modelling,Microelectronics and Reliability, vol. 23, pp. 113–119, 1983.Google Scholar
[39] D., Montoro-Cazorla and R., Pérez-Ocón, “A deteriorating two-system with two repair modes and sojourn times phase-type distributed,Reliability Engineering and System Safety, vol. 91, no. 1, pp. 1–9, 2006.Google Scholar
[40] U., Jensen, “Stochastic models of reliability and maintenance: An overview,” in Reliability and Maintenance of Complex Systems, ed. S., Özekici. NATO ASI Series, Springer, 1996, ch. 1, pp. 3–37.
[41] V., Kulkarni, V., Nicola, and K., Trivedi, “The completion time of a job on a multi-mode system,Advances in Applied Probability, vol. 19, pp. 932–954, 1987.Google Scholar
[42] M., Neuts, “Two further closure properties of PH-distributions,Asia-Pacific Journal of Operational Research, vol. 9, pp. 459–477, 1992.Google Scholar
[43] V., Ramaswami, “Algorithms for the multi-server queue with phase type service,Stochastic Models, vol. 1, no. 3, pp. 339–417, 1985.Google Scholar
[44] B., Sericola, F., Guillemin, and J. Boyer, “Sojourn times in the M/PH/1 processor sharing queue,Queueing Systems, vol. 50, no. 1, pp. 109–130, 2005.Google Scholar
[45] S., Asmussen, Markov Additive Models. Springer, 2003, pp. 302–339.
[46] S., Chakravarthy, Markovian Arrival Processes. John Wiley & Sons, 2010.
[47] D., Gross and C., Harris, Fundamentals of Queuing theory. John Wiley & Sons, 1985.
[48] S., Woolet, “Performance analysis of computer networks,” PhD Thesis, Department of Computer Science, Duke University, 1993.
[49] K., Trivedi, Probability and Statistics with Reliability, Queueing and Computer Science Applications, 2nd edn. John Wiley & Sons, 2001.
[50] A., Bobbio and M., Telek, “Non-exponential stochastic Petri nets: An overview of methods and techniques,Computer Systems: Science and Engineering, vol. 13, no. 6, pp. 339–351, 1998.Google Scholar
[51] J., Zhao, K., Trivedi, M., Grottke, J., Alonso, and Y., Wang, “Ensuring the performance of Apache HTTP server affected by aging,IEEE Transactions on Dependable and Secure Computing, vol. 11, no. 2, pp. 130–141, Mar. 2014.Google Scholar
[52] D., Chen and K. S., Trivedi, “Closed-form analytical results for condition-based maintenance,Reliability Engineering and System Safety, vol. 76, no. 1, pp. 43–51, 2002.Google Scholar
[53] G., Latouche and V., Ramaswami, Introduction to Matrix Analytic Methods in Stochastic Modeling. Society for Industrial and Applied Mathematics, 1999.
[54] B. V., Houdt, “A phase-type representation for the queue length distribution of a semi-Markovian queue,” in Proc. 7th Int. Conf. on Quantitative Evaluation of Systems, Sep 2010, pp. 49–58.Google Scholar
[55] J. E., Ruiz-Castro, R., Pérez-Ocón, and G., Fernández-Villodre, “Modelling a reliability system governed by discrete phase-type distributions,Reliability Engineering and System Safety, vol. 93, no. 11, pp. 1650–1657, 2008.Google Scholar
[56] A., Cumani, “ESP: A package for the evaluation of stochastic Petri nets with phase-type distributed transition times,” in Proc. Int. Workshop on Timed Petri Nets. IEEE Computer Society Press no. 674, 1985, pp. 144–151.
[57] P., Chen, S., Bruell, and G., Balbo, “Alternative methods for incorporating non-exponential distributions into stochastic timed Petri nets,” in Proc. Int. Workshop on Petri Nets and Performance Models (PNPM89). IEEE Computer Society, 1989, pp. 187–197.Google Scholar
[58] S., Haddad, P., Moreaux, and G., Chiola, “Efficient handling of phase-type distributions in generalized stochastic Petri nets,” in Proc. 18th Int. Conf. on Application and Theory of Petri Nets, ICATPN'97, LNCS 1248, eds. P., Azéma and G., Balbo. Springer Verlag, 1997, pp. 175–194.
[59] J., Brewer, “Kronecker products and matrix calculus in system theory,” IEEE Transactions on Circuits and Systems, vol. CAS-25, pp. 772–781, 1978.Google Scholar
[60] M., Davio, “Kronecker products and shuffle algebra,IEEE Transactions on Computers, vol. C-30, pp. 116–125, 1981.Google Scholar
[61] S., Donatelli, S., Haddad, and P., Moreaux, “Structured characterization of the Markov chain of a phase type SPN,” in Proc. 10th Int. Conf. on Modelling Techniques and Tools for Computer Performance Evaluation. Springer, 1998, pp. 243–254.
[62] M., Scarpa and A., Bobbio, “Kronecker representation of stochastic Petri nets with discrete PH distributions,” in Int. Computer Performance and Dependability Symp. (IPDS98). IEEE Computer Society Press, 1998, pp. 52–61.
[63] G., Ciardo and A., Miner, “A data structure for the efficient Kronecker solution of GSPNs,” in Proc. 8th Int. Conf. on Petri Nets and Performance Models (PNPM99). IEEE Computer Society, 1999, pp. 22–31.
[64] P., Buchholz, G., Ciardo, S., Donatelli and P., Kemper, “Complexity of memory-efficient Kronecker operations with applications to the solution of Markov models,INFORMS Journal on Computing, vol. 12, no. 3, pp. 203–222, 2000.Google Scholar
[65] P., Buchholz and P., Kemper, “Kronecker based matrix representations for large Markov chains,” in Validation of Stochastic Systems, LNCS 2925, eds. M. S. B., Haverkort, H., Hermanns. Springer Verlag, 2004, pp. 256–295.

Save book to Kindle

To save this book to your Kindle, first ensure [email protected] is added to your Approved Personal Document E-mail List under your Personal Document Settings on the Manage Your Content and Devices page of your Amazon account. Then enter the ‘name’ part of your Kindle email address below. Find out more about saving to your Kindle.

Note you can select to save to either the @free.kindle.com or @kindle.com variations. ‘@free.kindle.com’ emails are free but can only be saved to your device when it is connected to wi-fi. ‘@kindle.com’ emails can be delivered even when you are not connected to wi-fi, but note that service fees apply.

Find out more about the Kindle Personal Document Service.

Available formats
×

Save book to Dropbox

To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Dropbox.

Available formats
×

Save book to Google Drive

To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Google Drive.

Available formats
×