- Markov Chains: Modelling and Analysis
- Performance Evaluation of Computer Systems and
- Scientific Computing; Numerical Linear Algebra
Markov Chain Modelling
Much of my current research activity is concerned with various aspects of
building and solving Markov chain models.
In general this entails the use of numerical solution procedures that
are applicable in solving large scale systems of linear and differential
equations. High performance computers, whether parallel or
distributed, are most effective.
Examples of the use of Markov chains may be found
extensively throughout the biological, physical and social sciences as
well as in business and engineering.
For example, they may be used to
determine bottlenecks in communication networks, the effect of
increasing the number of CPUs in multiprocessor systems, the
effect of scheduling algorithms on throughput, etc.;
they are used in
economic models from population forecasting to financial planning,
(Indeed, a recent issue of
Stocks & Commodities
recommends the use of Markov chain models to its readers);
they have been widely used in reliability modelling to
estimate the mean time to failure of components in systems as diverse
as software systems and aerospace systems and to model the performance
of fault tolerant computers. Markov chains have been and continue
to be the method of choice for modelling many other systems.
An Introduction to the Numerical Solution of Markov Chains
Princeton University Press.
This book provides an extensive background to both discrete-time
and continuous-time Markov chains. It examines many different
approaches to computing numerical solutions including direct methods,
single-vector and multiple-vector iterative methods, and
It examines recursive methods often used when the structure of the
Markov chain is upper Hessenberg;
iterative aggregation/disaggregation methods that are particularly
appropriate when it is NCD (nearly-completely-decomposable),
and reduced schemes for cases in which the chain is periodic.
It contains a discussion on stochastic automata networks
and an extensive chapter on methods for computing transient solutions.
The final chapter is devoted to currently available software.
Other books, chapters and selected papers
Follow this link for my edited conference proceedings, chapters in
certain texts and a selection of my publications from various journals.
Marca: Markov Chain Analyzer
I have developed a software package called Marca;
Markov Chain Analyzer,
that is currently licensed by N. Carolina State University.
It is written entirely in Fortran and is designed to facilitate
the generation of large Markov chains and to compute both
transient and stationary probability distributions.
Also, an X-windows based graphical interface for queueing network models
( XMarca) has been developed.
Current research is aimed at
automating the numerical algorithm
selection processes and in examining possibilities for parallel
and distributed implementations.
Also in the works are enhancements to the user interface,
application fields, like telecommunications, in mind.
A Database of Markov Chain Models
I am developing a repository for a test-bed of matrices arising
in Markov chain problems. Later this will be extended
to incorporate sparse matrix manipulation software and numerical solution
algorithms. All will be available by anonymous ftp.
The repository is called MARCA_Models and is a set of subroutines
and associated data files which may be used to
generate the transition rate matrices of a collection of Markov chain models.
The purpose of the MARCA_Models database is twofold.
Currently, the repository contains over 80 matrices taken
from six different models.
Firstly, it provides a collection of matrices on which different
numerical solution methods may be tested and compared.
Secondly, the models may prove to be useful to those engaged in
system modelling, for users can modify the model parameters to obtain
others that more closely correspond to their own requirements.
Software for Stochastic Automata Networks
I am involved in ongoing research at INRIA Rhone-Alpes in the IP
research group of
into the area of SANs (Stochastic
The use of SANs is becoming increasingly
important in performance modelling issues related to parallel and distributed
computer systems. As such models become increasingly complex, so also does the
complexity of the modelling process. Parallel and distributed systems are often
viewed as collections of components that operate more or less independently,
requiring only infrequent interaction such as synchronizing their actions, or
operating at different rates depending on the state of parts of the overall system.
This is exactly the viewpoint adopted by SANs. The components are modelled as
individual stochastic automata that interact with each other. Furthermore, the
state space explosion problem associated with Markov chain models is mitigated
by the fact that the state transition matrix is not stored, nor even generated.
Instead, it is represented by a number of much smaller matrices, one for each of
the stochastic automata that constitute the system, and from these all relevent
information may be determined without explicitly forming the global matrix.
The implication is that a considerable saving in memory is effected by storing the
matrix in this fashion. This saving is reinforced by the use of functions (of the
current global state) as transition rates. The software package PEPS
implements our most recent advances in this area.
Software for Functional and Performance Analysis
TwoTowers 1.0 is a software tool for the functional and performance analysis of
computer, communication and software systems modeled in extended Markovian
process algebra with generative-reactive synchronizations and value passing.
This project is led by
of the University of Torino, Italy.
Since many functional
properties of a system may be examined independently of performance properties
and vice versa, TwoTowers 1.0 uses two existing tools - CWB-NC and a Marca-like
tool - that have been retargeted for the analysis of these two different
types of properties. CWB-NC 1.2 provides a variety of different types of analysis
(e.g., model checking, equivalence checking, preorder checking) of the functional
behavior of systems, while the Marca-like tool conducts steady state and transient
Markov Chain Conferences
In January 1990, I organized the First International
Conference on the Numerical Solution of Markov Chains.
This was the first conference ever on this topic and
was held on the campus of N. Carolina State University.
It was widely acclaimed to have been a
successful meeting and the proceedings which were edited and
published by Marcel Dekker, Inc. have become a
standard reference in the field.
This led to a second
conference that I also organized and which
was held in Raleigh on January 16-18, 1995.
The proceedings were published by Kluwer Academic Publishers.
The third in the series was held in September 1999 in Zaragosa, Spain.
This time the conference was jointly organized with
other meetings of a somewhat related nature.
The fourth was also held jointly and took place at the
University of Illinois, Urbana-Champaign in 2003.
A meeting to celebrate the 150th anniversary of the birth of A.A. Markov
will take place in Charleston, SC in June 2006.
2006 Anniversary Meeting