Automated Rare Event Simulation for Stochastic Petri Nets

Research output: Contribution to conferencePaperAcademic

41 Downloads (Pure)

Abstract

We introduce a method to automatically apply rare event simulation to stochastic Petri nets, which are often used in the stochastic model checking community to model highly reliable systems. Rare event simulation can be much faster than standard simulation by exploiting 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) stochastic Petri net description, without generating the full state space. Essentially, our algorithm reduces the state space of the model to 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. An earlier version of this work has been presented to the model checking commmunity (at QEST 2013). We believe that the described methodology, which has since then been improved through a correctness proof and a more efficient initial state space partitioning, may also be of interest to the RESIM community.
Original languageUndefined
Pages80-81
Number of pages2
Publication statusPublished - Aug 2014

Keywords

  • EWI-25339
  • IR-93883

Cite this

@conference{934dda2422fe42f3a5217ff64f7206c2,
title = "Automated Rare Event Simulation for Stochastic Petri Nets",
abstract = "We introduce a method to automatically apply rare event simulation to stochastic Petri nets, which are often used in the stochastic model checking community to model highly reliable systems. Rare event simulation can be much faster than standard simulation by exploiting 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) stochastic Petri net description, without generating the full state space. Essentially, our algorithm reduces the state space of the model to 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. An earlier version of this work has been presented to the model checking commmunity (at QEST 2013). We believe that the described methodology, which has since then been improved through a correctness proof and a more efficient initial state space partitioning, may also be of interest to the RESIM community.",
keywords = "EWI-25339, IR-93883",
author = "D.P. Reijsbergen and {de Boer}, Pieter-Tjerk and Scheinhardt, {Willem R.W.}",
year = "2014",
month = "8",
language = "Undefined",
pages = "80--81",

}

Automated Rare Event Simulation for Stochastic Petri Nets. / Reijsbergen, D.P.; de Boer, Pieter-Tjerk; Scheinhardt, Willem R.W.

2014. 80-81.

Research output: Contribution to conferencePaperAcademic

TY - CONF

T1 - Automated Rare Event Simulation for Stochastic Petri Nets

AU - Reijsbergen, D.P.

AU - de Boer, Pieter-Tjerk

AU - Scheinhardt, Willem R.W.

PY - 2014/8

Y1 - 2014/8

N2 - We introduce a method to automatically apply rare event simulation to stochastic Petri nets, which are often used in the stochastic model checking community to model highly reliable systems. Rare event simulation can be much faster than standard simulation by exploiting 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) stochastic Petri net description, without generating the full state space. Essentially, our algorithm reduces the state space of the model to 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. An earlier version of this work has been presented to the model checking commmunity (at QEST 2013). We believe that the described methodology, which has since then been improved through a correctness proof and a more efficient initial state space partitioning, may also be of interest to the RESIM community.

AB - We introduce a method to automatically apply rare event simulation to stochastic Petri nets, which are often used in the stochastic model checking community to model highly reliable systems. Rare event simulation can be much faster than standard simulation by exploiting 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) stochastic Petri net description, without generating the full state space. Essentially, our algorithm reduces the state space of the model to 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. An earlier version of this work has been presented to the model checking commmunity (at QEST 2013). We believe that the described methodology, which has since then been improved through a correctness proof and a more efficient initial state space partitioning, may also be of interest to the RESIM community.

KW - EWI-25339

KW - IR-93883

M3 - Paper

SP - 80

EP - 81

ER -