Automated rare event simulation for stochastic Petri nets

Research output: Chapter in Book/Report/Conference proceedingConference contribution

  • 11 Citations

Abstract

We introduce an automated approach for applying rare event simulation to stochastic Petri net (SPN) models of highly reliable systems. Rare event simulation can be much faster than standard simulation because it is able to exploit information about the typical behaviour of the system. Previously, such information came from heuristics, human insight, or analysis on the full state space. We present a formal algorithm that obtains the required information from the high-level SPN- description, without generating the full state space. Essentially, our algorithm reduces the state space of the model into a (much smaller) graph in which each node represents a set of states for which the most likely path to failure has the same form. We empirically demonstrate the efficiency of the method with two case studies.
LanguageUndefined
Title of host publicationProceedings of the 10th International Conference on Quantitative Evaluation of Systems, QEST 2013
EditorsK. Joshi, M. Siegle, M. Stoelinga, P.R. d' Argenio
Place of PublicationBerlin, Heidelberg
PublisherSpringer
Pages372-388
Number of pages17
ISBN (Print)978-3-642-40195-4
DOIs
StatePublished - 2013
Event10th International Conference on Quantitative Evaluation of Systems, QEST 2013 - University of Buenos Aires, Buenos Aires, Argentina
Duration: 27 Aug 201330 Aug 2013
Conference number: 10
http://www.qest.org/qest2013/

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Verlag
Volume8054
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference10th International Conference on Quantitative Evaluation of Systems, QEST 2013
Abbreviated titleQEST
CountryArgentina
CityBuenos Aires
Period27/08/1330/08/13
Internet address

Keywords

  • EWI-23929
  • IR-87777
  • METIS-300136

Cite this

Reijsbergen, D. P., de Boer, P-T., Scheinhardt, W. R. W., & Haverkort, B. R. H. M. (2013). Automated rare event simulation for stochastic Petri nets. In K. Joshi, M. Siegle, M. Stoelinga, & P. R. d' Argenio (Eds.), Proceedings of the 10th International Conference on Quantitative Evaluation of Systems, QEST 2013 (pp. 372-388). (Lecture Notes in Computer Science; Vol. 8054). Berlin, Heidelberg: Springer. DOI: 10.1007/978-3-642-40196-1_31, 10.1007/978-3-642-40196-1
Reijsbergen, D.P. ; de Boer, Pieter-Tjerk ; Scheinhardt, Willem R.W. ; Haverkort, Boudewijn R.H.M./ Automated rare event simulation for stochastic Petri nets. Proceedings of the 10th International Conference on Quantitative Evaluation of Systems, QEST 2013. editor / K. Joshi ; M. Siegle ; M. Stoelinga ; P.R. d' Argenio. Berlin, Heidelberg : Springer, 2013. pp. 372-388 (Lecture Notes in Computer Science).
@inproceedings{072a68a972ac48f08fe786f8ecc692de,
title = "Automated rare event simulation for stochastic Petri nets",
abstract = "We introduce an automated approach for applying rare event simulation to stochastic Petri net (SPN) models of highly reliable systems. Rare event simulation can be much faster than standard simulation because it is able to exploit information about the typical behaviour of the system. Previously, such information came from heuristics, human insight, or analysis on the full state space. We present a formal algorithm that obtains the required information from the high-level SPN- description, without generating the full state space. Essentially, our algorithm reduces the state space of the model into a (much smaller) graph in which each node represents a set of states for which the most likely path to failure has the same form. We empirically demonstrate the efficiency of the method with two case studies.",
keywords = "EWI-23929, IR-87777, METIS-300136",
author = "D.P. Reijsbergen and {de Boer}, Pieter-Tjerk and Scheinhardt, {Willem R.W.} and Haverkort, {Boudewijn R.H.M.}",
note = "10.1007/978-3-642-40196-1",
year = "2013",
doi = "10.1007/978-3-642-40196-1_31",
language = "Undefined",
isbn = "978-3-642-40195-4",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "372--388",
editor = "K. Joshi and M. Siegle and M. Stoelinga and {d' Argenio}, P.R.",
booktitle = "Proceedings of the 10th International Conference on Quantitative Evaluation of Systems, QEST 2013",

}

Reijsbergen, DP, de Boer, P-T, Scheinhardt, WRW & Haverkort, BRHM 2013, Automated rare event simulation for stochastic Petri nets. in K Joshi, M Siegle, M Stoelinga & PR d' Argenio (eds), Proceedings of the 10th International Conference on Quantitative Evaluation of Systems, QEST 2013. Lecture Notes in Computer Science, vol. 8054, Springer, Berlin, Heidelberg, pp. 372-388, 10th International Conference on Quantitative Evaluation of Systems, QEST 2013, Buenos Aires, Argentina, 27/08/13. DOI: 10.1007/978-3-642-40196-1_31, 10.1007/978-3-642-40196-1

Automated rare event simulation for stochastic Petri nets. / Reijsbergen, D.P.; de Boer, Pieter-Tjerk; Scheinhardt, Willem R.W.; Haverkort, Boudewijn R.H.M.

Proceedings of the 10th International Conference on Quantitative Evaluation of Systems, QEST 2013. ed. / K. Joshi; M. Siegle; M. Stoelinga; P.R. d' Argenio. Berlin, Heidelberg : Springer, 2013. p. 372-388 (Lecture Notes in Computer Science; Vol. 8054).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

TY - GEN

T1 - Automated rare event simulation for stochastic Petri nets

AU - Reijsbergen,D.P.

AU - de Boer,Pieter-Tjerk

AU - Scheinhardt,Willem R.W.

AU - Haverkort,Boudewijn R.H.M.

N1 - 10.1007/978-3-642-40196-1

PY - 2013

Y1 - 2013

N2 - We introduce an automated approach for applying rare event simulation to stochastic Petri net (SPN) models of highly reliable systems. Rare event simulation can be much faster than standard simulation because it is able to exploit information about the typical behaviour of the system. Previously, such information came from heuristics, human insight, or analysis on the full state space. We present a formal algorithm that obtains the required information from the high-level SPN- description, without generating the full state space. Essentially, our algorithm reduces the state space of the model into a (much smaller) graph in which each node represents a set of states for which the most likely path to failure has the same form. We empirically demonstrate the efficiency of the method with two case studies.

AB - We introduce an automated approach for applying rare event simulation to stochastic Petri net (SPN) models of highly reliable systems. Rare event simulation can be much faster than standard simulation because it is able to exploit information about the typical behaviour of the system. Previously, such information came from heuristics, human insight, or analysis on the full state space. We present a formal algorithm that obtains the required information from the high-level SPN- description, without generating the full state space. Essentially, our algorithm reduces the state space of the model into a (much smaller) graph in which each node represents a set of states for which the most likely path to failure has the same form. We empirically demonstrate the efficiency of the method with two case studies.

KW - EWI-23929

KW - IR-87777

KW - METIS-300136

U2 - 10.1007/978-3-642-40196-1_31

DO - 10.1007/978-3-642-40196-1_31

M3 - Conference contribution

SN - 978-3-642-40195-4

T3 - Lecture Notes in Computer Science

SP - 372

EP - 388

BT - Proceedings of the 10th International Conference on Quantitative Evaluation of Systems, QEST 2013

PB - Springer

CY - Berlin, Heidelberg

ER -

Reijsbergen DP, de Boer P-T, Scheinhardt WRW, Haverkort BRHM. Automated rare event simulation for stochastic Petri nets. In Joshi K, Siegle M, Stoelinga M, d' Argenio PR, editors, Proceedings of the 10th International Conference on Quantitative Evaluation of Systems, QEST 2013. Berlin, Heidelberg: Springer. 2013. p. 372-388. (Lecture Notes in Computer Science). Available from, DOI: 10.1007/978-3-642-40196-1_31, 10.1007/978-3-642-40196-1