Abstract
We report in the advances on stochastic automata and its use on rare event simulation. We review and introduce an extension of IOSA, an input/output variant of stochastic automata that under mild constraints can be ensured to contain non-determinism only in a spurious manner. That is, the model can be regarded as fully probabilistic and hence amenable for simulation. We also report on our latest work on fully automatizing the technique of rare event simulation. Using the structure of the model given in terms a network of IOSAs allows us to automatically derive the importance function, which is crucial for the importance splitting technique of rare event simulation. We conclude with experimental results that show how promising our technique is.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Alur, R., Dill, D.L.: A theory of timed automata. Theor. Comput. Sci. 126(2), 183–235 (1994). https://doi.org/10.1016/0304-3975(94)90010-8
Bolognesi, T., Brinksma, E.: Introduction to the ISO specification language LOTOS. Comput. Netw. 14, 25–59 (1987). https://doi.org/10.1016/0169-7552(87)90085-7
Budde, C.E.: Automation of importance splitting techniques for rare event simulation. Ph.D. thesis. Universidad Nacional de Córdoba, Argentina (2017)
Budde, C.E., D’Argenio, P.R., Hermanns, H.: Rare event simulation with fully automated importance splitting. In: Beltrán, M., Knottenbelt, W., Bradley, J. (eds.) EPEW 2015. LNCS, vol. 9272, pp. 275–290. Springer, Cham (2015). doi:10.1007/978-3-319-23267-6_18
Budde, C.E., D’Argenio, P.R., Monti, R.E.: Compositional construction of importance functions in fully automated importance splitting. In: Puliafito, A., Trivedi, K.S., Tuffin, B., Scarpa, M., Machida, F., Alonso, J. (eds.) Proceedigns of VALUETOOLS 2016. ACM (2017). https://dx.doi.org/10.4108/eai.25-10-2016.2266501
Cérou, F., Del Moral, P., Furon, T., Guyader, A.: Sequential Monte Carlo for rare event estimation. Stat. Comput. 22(3), 795–808 (2012). https://dx.doi.org/10.1007/s11222-011-9231-6
Cérou, F., Guyader, A.: Adaptive multilevel splitting for rare event analysis. Stoch. Anal. Appl. 25(2), 417–443 (2007)
D’Argenio, P.R.: Algebras and automata for timed and stochastic systems. Ph.D. thesis. University of Twente, Enschede (1999)
D’Argenio, P.R., Katoen, J.P.: A theory of stochastic systems part I: Stochastic automata. Inf. Comput. 203(1), 1–38 (2005)
D’Argenio, P.R., Katoen, J., Brinksma, E.: An algebraic approach to the specification of stochastic systems. In: Gries, D., de Roever, W.P. (eds.) PROCOMET 1998. IFIP Conference Proceedings, vol. 125, pp. 126–147. Chapman & Hall (1998)
D’Argenio, P.R., Katoen, J.P., Brinksma, E.: A compositional approach to generalised semi-Markov processes. In: Proceedings of WODES 1998, pp. 391–387. IEE (1998)
D’Argenio, P.R., Katoen, J., Brinksma, E.: Specification and analysis of soft real-time systems: quantity and quality. In: Proceedings of 20th RTSS, pp. 104–114. IEEE Computer Society (1999). https://doi.org/10.1109/REAL.1999.818832
D’Argenio, P.R., Lee, M.D., Monti, R.E.: Input/output stochastic automata. In: Fränzle, M., Markey, N. (eds.) FORMATS 2016. LNCS, vol. 9884, pp. 53–68. Springer, Cham (2016). doi:10.1007/978-3-319-44878-7_4
D’Argenio, P.R., Sánchez Terraf, P., Wolovick, N.: Bisimulations for non-deterministic labelled Markov processes. Math. Struct. Comput. Sci. 22(1), 43–68 (2012)
Desharnais, J., Edalat, A., Panangaden, P.: Bisimulation for labelled Markov processes. Inf. Comput. 179(2), 163–193 (2002)
Garvels, M.J.J., Van Ommeren, J.K.C.W., Kroese, D.P.: On the importance function in splitting simulation. Eur. Trans. Telecommun. 13(4), 363–371 (2002). https://dx.doi.org/10.1002/ett.4460130408
Giry, M.: A categorical approach to probability theory. In: Banaschewski, B. (ed.) Categorical Aspects of Topology and Analysis. LNM, vol. 915, pp. 68–85. Springer, Heidelberg (1982). doi:10.1007/BFb0092872
van Glabbeek, R.J., Smolka, S.A., Steffen, B.: Reactive, generative and stratified models of probabilistic processes. Inf. Comput. 121(1), 59–80 (1995)
Hahn, E.M., Hartmanns, A., Hermanns, H.: Reachability and reward checking for stochastic timed automata. ECEASST, vol. 70 (2014). http://journal.ub.tu-berlin.de/eceasst/article/view/968
Hermanns, H. (ed.): Interactive Markov Chains. LNCS, vol. 2428. Springer, Heidelberg (2002). doi:10.1007/3-540-45804-2
Jegourel, C., Legay, A., Sedwards, S.: Importance splitting for statistical model checking rare properties. In: Sharygina, N., Veith, H. (eds.) CAV 2013. LNCS, vol. 8044, pp. 576–591. Springer, Heidelberg (2013). doi:10.1007/978-3-642-39799-8_38
Kroese, D.P., Nicola, V.F.: Efficient estimation of overflow probabilities in queues with breakdowns. Performance Eval. 36, 471–484 (1999)
L’Ecuyer, P., Le Gland, F., Lezaud, P., Tuffin, B.: Splitting techniques. In: Rare Event Simulation using Monte Carlo Methods, pp. 39–61. Wiley (2009). http://dx.doi.org/10.1002/9780470745403.ch3
Milner, R.: Communication and Concurrency. Prentice-Hall Inc., Upper Saddle River (1989)
Reijsbergen, D., de Boer, P.-T., Scheinhardt, W., Haverkort, B.: Automated rare event simulation for stochastic petri nets. In: Joshi, K., Siegle, M., Stoelinga, M., D’Argenio, P.R. (eds.) QEST 2013. LNCS, vol. 8054, pp. 372–388. Springer, Heidelberg (2013). doi:10.1007/978-3-642-40196-1_31
Villén-Altamirano, J.: RESTART simulation of networks of queues with Erlang service times. In: Winter Simulation Conference (2009), WSC 2009, pp. 1146–1154 (2009). http://dl.acm.org/citation.cfm?id=1995456.1995616
Villén-Altamirano, J.: RESTART simulation of non-Markov consecutive-k-out-of-n: F repairable systems. Rel. Eng. Sys. Safety 95(3), 247–254 (2010). https://dx.doi.org/10.1016/j.ress.2009.10.005
Villén-Altamirano, M., Martínez-Marrón, A., Gamo, J., Fernández-Cuesta, F.: Enhancement of the accelerated simulation method restart by considering multiple thresholds. In: Proceedings of 14th International Teletraffic Congress, pp. 797–810 (1994)
Villén-Altamirano, M., Villén-Altamirano, J.: RESTART: a method for accelerating rare event simulations. In: Queueing, Performance and Control in ATM (ITC-13), pp. 71–76. Elsevier (1991)
Villén-Altamirano, M., Villén-Altamirano, J.: The rare event simulation method RESTART: efficiency analysis and guidelines for its application. In: Kouvatsos, D.D. (ed.) Network Performance Engineering. LNCS, vol. 5233, pp. 509–547. Springer, Heidelberg (2011). doi:10.1007/978-3-642-02742-0_22
Villén-Altamirano, J.: Asymptotic optimality of RESTART estimators in highly dependable systems. Reliab. Eng. Syst. Saf. 130, 115–124 (2014). www.sciencedirect.com/science/article/pii/S0951832014001227
Wolovick, N.: Continuous probability and nondeterminism in labeled transition systems. Ph.D. thesis. Universidad Nacional de Córdoba, Argentina (2012)
Wu, S., Smolka, S.A., Stark, E.W.: Composition and behaviors of probabilistic I/O automata. Theor. Comput. Sci. 176(1–2), 1–38 (1997)
Xiao, G., Li, Z., Li, T.: Dependability estimation for non-Markov consecutive-k-out-of-n: F repairable systems by fast simulation. Reliab. Eng. Syst. Saf. 92(3), 293–299 (2007). https://dx.doi.org/10.1016/j.ress.2006.04.004
Zimmermann, A., Maciel, P.: Importance function derivation for RESTART simulations of Petri nets. In: RESIM, pp. 8–15 (2012)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this chapter
Cite this chapter
D’Argenio, P.R., Budde, C.E., Lee, M.D., Monti, R.E., Rodríguez, L., Wolovick, N. (2017). The Road from Stochastic Automata to the Simulation of Rare Events. In: Katoen, JP., Langerak, R., Rensink, A. (eds) ModelEd, TestEd, TrustEd. Lecture Notes in Computer Science(), vol 10500. Springer, Cham. https://doi.org/10.1007/978-3-319-68270-9_14
Download citation
DOI: https://doi.org/10.1007/978-3-319-68270-9_14
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-68269-3
Online ISBN: 978-3-319-68270-9
eBook Packages: Computer ScienceComputer Science (R0)