Abstract

Probabilistic model checking mainly concentrates on techniques for reasoning about the probabilities of certain path properties or expected values of certain random variables. For the quantitative system analysis, however, there is also another type of interesting performance measure, namely quantiles. A typical quantile query takes as input a lower probability bound p and a reachability property. The task is then to compute the minimal reward bound r such that with probability at least p the target set will be reached before the accumulated reward exceeds r. Quantiles are well-known from mathematical statistics, but to the best of our knowledge they have not been addressed by the model checking community so far. In this paper, we study the complexity of quantile queries for until properties in discrete-time finite-state Markov decision processes with non-negative rewards on states. We show that qualitative quantile queries can be evaluated in polynomial time and present an exponential algorithm for the evaluation of quantitative quantile queries. For the special case of Markov chains, we show that quantitative quantile queries can be evaluated in time polynomial in the size of the chain and the maximum reward. Document type: Part of book or chapter of book

Abstract

Part 6: Poster Sessions; International audience; The importance of Internet availability is supported by the overwhelming dependence of government services and financial institutions upon said availability. Unfortunately, the Internet is facing different level of undesirable connectivity incidents. So, it is imperative to take serious measures in order to increase Internet connectivity resilience. We consider a scenario where a concerned region is facing an undesirable connectivity incident by its primary Internet Service Provider (ISP) which still advertises reachability to the concerned region. Assuming that connectivity to a secondary ISP is available, software is designed to implement different traffic engineering techniques in order to enhance internet connectivity resilience and send the traffic through the secondary ISP. The work is characterized by the implementation of these traffic engineering techniques in the laboratory through a detailed set of experiments. Document type: Part of book or chapter of book