Markov Model Rewriter: A Discrete Time Markov chain simulation and 

perturbation system. 

The Markov Model Rewriter is a Discrete Time Markov chain (DTMC) simulation tool 

implemented in SLX1 that can be applied to discrete time Markov models for which Transition 

Probability Matrices (TPMs) have been developed. The Markov Model Rewriter uses a piecewise homogenous DTMC to represent different time periods in system evolution in cases where 

the system dynamics evolve over time. In a piece-wise homogenous chain, different time periods 

are represented by TPMs specific to those periods. As system evolution progresses through 

different time periods, different matrices are applied. The Rewriter employs a well-known matrix 

multiplication procedure to evolve the system state at each discrete time step. The tool can model 

system dynamics over a limited period of time such as an 8-hour work day or over an extended 

period of time involving many days or weeks. The process can also be parameterized by the 

number of distinct time periods (with related TPMs) that are modeled and the length of a discrete 

time step. 

The Markov Model Rewriter can be used to perturb a set of TPMs to produce alternative system 

execution paths and to identify scenarios in which system performance changes or in which 

anomalous behaviors occur. This is accomplished by systematically varying TPM elements to 

identify changes to probabilities of system state transitions that in turn produce changes to 

system behavior. The Rewriter also supports extensive parameterization of the TPM perturbation 

process. This includes specification of which rows and columns of the matrix are to be perturbed 

and the bounds of allowable perturbation. The tool outputs values of selected system state 

variables and an evolutionary trace consisting of a series of system state vectors that show the 

evolution of a system over time. 

To date, the Rewriter has been applied to the simulation of large-scale grid computing systems 

[1, 2] where it has been shown to be predictive of how failure to meet quality of service 

guarantees impacts system performance. The Markov Model rewriter is currently being extended 

to allow greater flexibility in the selection of combinations of perturbed rows and columns for 

perturbation in order to model a greater number of changes in system behavior. Of special 

interest are changes that are more likely to produce extreme emergent system behaviors. Another 

important research direction underway is the development of methods for automatically reducing 

the size of the search space so that this tool can be applied to larger TPMs and to cases where 

extensive perturbation is required. In addition, we are seeking additional domains in which to 

apply this technique. 

[1] C. Dabrowski and F. Hunt, Using Markov Chain Analysis to Study Dynamic Behaviour in Large-Scale Grid 

Systems , Proceedings of the 7th Australasian Symposium on Grid Computing and e-Research, Wellington, NZ, 

January 2009. [2] Dabrowski, C. and Hunt F, Markov Chain Analysis for Large-Scale Grid Systems. Draft NIST Technical Report. 

2008. 

                                                           

1 SLX is a commercial simulation system available from Wolverine Software, see: 

http://www.wolverinesoftware.com