Oxford logo
[CDKM12] T. Chen, M. Diciolla, M. Kwiatkowska and A. Mereacre. Verification of Linear Duration Properties over Continuous-Time Markov Chains. In Proc. 15th International Conference on Hybrid Systems: Computation and Control (HSCC 2012), pages 265-274, ACM. April 2012. [pdf] [bib]
Downloads:  pdf pdf (338 KB)  bib bib
Abstract. Stochastic modeling and algorithmic verification techniques have been proved useful in analyzing and detecting unusual trends in performance and energy usage of systems such as power management controllers and wireless sensor devices. Many important properties are dependent on the cumulated time that the device spends in certain states, possibly intermittently.We study the problem of verifying continuoustime Markov chains (CTMCs) against linear duration properties (LDP), i.e. properties stated as conjunctions of linear constraints over the total duration of time spent in states that satisfy a given property. We identify two classes of LDP properties, eventuality duration properties (EDP) and invariance duration properties (IDP), espectively referring to the reachability of a set of goal states, within a time bound; and the continuous satisfaction of a duration property over an execution path. The central question that we address is how to compute the probability of the set of infinite timed paths of the CTMC that satisfy a given LDP. We present algorithms to approximate these probabilities up to a given precision, stating their complexity and error bounds. The algorithms mainly employ an adaptation of uniformization and the computation of volumes of multi-dimensional integrals under systems of linear constraints, together with different mechanisms to bound the errors.