Markov models have a long tradition in modeling and simulation of dynamic systems. In this paper, we look at certain properties of a discrete time Markov chain including entropy, trace and 2nd largest eigenvalue to better understand their role for time series analysis. We simulate a number of possible input signals, fit a discrete time Markov chain and explore properties with the help of Sobol indices. This research is motivated by recent results in the analysis of cell development for Xenopus laevis in cell biology that relied on the considered entropy measure to distinguish development stages from time series data of Calcium levels in cells.

PDS is a well-recognized, major international forum for researchers and practitioners to present innovative, high-quality results in the analysis and assessment of computer systems and networks in terms of their performance, dependability, and security. As much as the considered systems vary from extremely small embedded devices and hardware components to large scale networked systems and infrastructures, so do the properties of interest with various aspects of performance, dependability, and security and the assessment approaches ranging from empirical and experimental studies to refined mathematical modeling methods. This year, we received 113 submissions (95 regular papers, 11 practical experience reports, and 7 tool descriptions) from 20 countries, covering various facets of research and practice on these topics.

Simulation modeling requires model validation and verification to ensure that computed results are worth being considered. While we cannot expect a magic solution to the general problem, automated techniques for particular aspects of validation and verification are feasible. In this paper, we propose a technique to deduce model properties automatically from simulation runs performed for verification and validation and to use those properties for runtime monitoring during production runs. Properties are represented as formulas in linear temporal logic and are limited to functional properties. We demonstrate the applicability of the approach with using an extended version of a stochastic Botnet model originally developed by Van Ruitenbeek and Sanders.

Any model-based evaluation of the dependability of a system requires validation and verification to justify that its results are meaningful. Modern modeling frameworks enable us to create and evaluate models of great complexity. However, we believe that much more can be done to support a modeler in ensuring that the dynamic behavior of an executable simulation model is consistent with the modeler's understanding. In this paper, we describe a new command line version of Traviando that reads an execution trace of a discrete event simulation and generates a set of HTML formatted Web pages to document properties that it recognizes from its input. Those properties include characteristics of state variables as well as changes to state variables that are performed by events. The point is to highlight the content of a simulation run in a format that is immediately accessible and understandable.

In this paper, we describe a novel technique that helps a modeler gain insight into the dynamic behavior of a complex stochastic discrete event simulation model based on trace analysis. We propose algorithms to distinguish progressive from repetitive behavior in a trace and to extract a minimal progressive fragment of a trace. The implied combinatorial optimization problem for trace reduction is solved in linear time with dynamic programming. We present and compare several approximate and one exact solution method. Information on the reduction operation as well as the reduced trace itself helps a modeler to recognize the presence of certain errors and to identify their cause. We track down a subtle modeling error in a dependability model of a multi-class server system to illustrate the effectiveness of our approach in revealing the cause of an observed effect. The proposed technique has been implemented and integrated in Traviando, a trace analyzer to debug stochastic simulation models.

In general, decision support is one of the main purposes of model-based analysis of systems. Response surface methodology (RSM) is an optimization technique that has been applied frequently in practice, but few automated variants are currently available. In this paper, we show how to combine RSM with numerical analysis methods to optimize continuous time Markov chain models. Among the many known numerical solution methods for large Markov chains, we consider a Gauss-Seidel solver with relaxation that relies on a hierarchical Kronecker representation as implemented in the APNN Toolbox. To effectively apply RSM for optimizing numerical models, we propose three strategies which are shown to reduce the required number of iterations of the numerical solver. With a set of experiments, we evaluate the proposed strategies with a model of a production line and apply them to optimize a class-based queuing system

Continuous-time Markov chains (CTMCs) have been used successfully to model the dependability and performability of many systems. Matrix diagrams (MDs) are known to be a space-efficient, symbolic representation of large CTMCs. In this paper, we identify local conditions for exact and ordinary lumpings that allow us to lump MD representations of Markov models in a compositional manner. We propose a lumping algorithm for CTMCs that are represented as MDs that is based on partition refinement, is applied to each level of an MD directly, and results in an MD representation of the lumped CTMC. Our compositional lumping approach is complementary to other known model-level lumping approaches for matrix diagrams. The approach has been implemented, and we demonstrate its efficiency and benefits by evaluating an example model of a tandem multi-processor system with load balancing and failure and repair operations.

In general, decision support is one of the main purposes of model-based analysis of systems. Response surface methodology (RSM) is an optimization technique that has been applied frequently in practice, but few automated variants are currently available. In this paper, we propose the combination of RSM with numerical analysis methods to solve continuous time Markov chain models of class-based queueing systems (CBQ). We consider first- and second-order models in RSM to identify an optimal parameter configuration for CBQ as part of the differentiated service architecture. Among the many known numerical solution methods for large Markov chains, we consider a Gauss-Seidel solver with relaxation that relies on a hierarchical Kronecker representation as implemented in the APNN Toolbox. To effectively apply the proposed optimization methodology we determine a suitable configuration of RSM and compare the results with previous results for optimizing CBQ.

Multiprocessor architectures with few but powerful processors are gaining more and more popularity. We describe a parallel iterative algorithm to perform randomization for a continuous time Markov chain with a Kronecker representation on a shared memory architecture. The Kronecker representation is modified for a parallel matrix-vector multiplication with a fast multiplication scheme and no write conflicts on iteration vectors. The proposed technique is applied on a model of a workstation cluster for dependability analysis, corresponding computations are performed on two multiprocessor architectures, a Sun enterprise and a SGI Origin 2000 to measure its performance.

We present new algorithms for the solution of large structured Markov models whose infinitesimal generator can be expressed as a Kronecker expression of sparse matrices. We then compare them with the shuffle-based method commonly used in this context and show how our new algorithms can be advantageous in dealing with very sparse matrices and in supporting both Jacobi-style and Gauss-Seidel-style methods with appropriate multiplication algorithms. Our main contribution is to show how solution algorithms based on Kronecker expression can be modified to consider probability vectors of size equal to the “actual” state space instead of the “potential” state space, thus providing space and time savings. The complexity of our algorithms is compared under different sparsity assumptions. A nontrivial example is studied to illustrate the complexity of the implemented algorithms.

The paper considers transient analysis using randomization for superposed generalized stochastic Petri nets (GSPNs). Since state space explosion implies that space is the bottleneck for numerical analysis, superposed GSPNs profit from the structured representation known for its associated Markov chain. This moves the bottleneck for analysis from space for generator matrices to space for iteration vectors. Hence a variation of randomization is presented which allows to reduce space requirements for iteration vectors. An additional and welcome side effect is that during an initial phase, this algorithm avoids useless multiplications involving states with zero probability. Furthermore, it accommodates to adaptive randomization in a natural way. Although the algorithm has been developed for superposed GSPNs, it applies to continuous time Markov chains in a more general setting.

The numerical analysis of various modeling formalisms profits from a structured representation for the generator matrix Q of the underlying continuous-time Markov chain, where Q is described by a sum of tensor (Kronecker) products of much smaller matrices. In this paper, we describe such a representation for the class of superposed generalized stochastic Petri nets (GSPNs), which is less restrictive than in previous work. Furthermore a new iterative analysis algorithm is proposed. It pays special attention to a memory-efficient representation of iteration vectors as well as to a memory-efficient structured representation of Q in consequence the new algorithm is able to solve models which have state spaces with several million states, where other exact numerical methods become impracticable on a common workstation.