Research Interests


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.

Publications

Text Book
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 projection methods. 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.


Software

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, keeping particular application fields, like telecommunications, in mind.

A Database of Markov Chain Models
Marca-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.

Software for Stochastic Automata Networks
PEPS

I am involved in ongoing research at INRIA Rhone-Alpes in the IP research group of Brigitte Plateau into the area of SANs (Stochastic Automata Networks). 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
Two Towers

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 Marco Bernardo 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 performance analysis.


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.
1990 Meeting

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. 1995 Meeeting

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. 1999 Meeeting
The fourth was also held jointly and took place at the University of Illinois, Urbana-Champaign in 2003. 2003 Meeeting

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