AESOP home


PASTRAMI: Passage Times in Large Markov and Semi-Markov Chains

Prof. Peter Harrison
Prof. William Knottenbelt
Dr Uli Harder
EPSRC project GR/S24961/01
Started in July 2003
Completed in June 2006
Funded value

This proposal is a resubmission of one with (almost) the same name which has been updated in the light of:

  1. the constructive comments of referees;
  2. some well received papers written by the applicants and published at major international conferences;
  3. more emphasis on distr implementation methods. The objectives therefore remain similar.

Note, however, that, in response to one referee's comments, we have not focussed on Markov reward processes per se. This is because the extension over passage time analysis is straightforward and so we have included this component as an 'application' in our work programme. Reduced to key fundamentals, the research proposed will:

  1. Investigate time delay densities in Markov chains, via first passage time analysis;
  2. Develop appropriate distributed algorithms and data partitions, especially via hypergraphs, to compute Laplace transforms;
  3. Devise parallel algorithms for Laplace transform inversion;
  4. Extend the research to semi-Markov chains by considering their kernels and using aggregation techniques;
  5. Apply the results to relevant case studies, including internet subsystems extensively monitored in our project QUAINT (GR/M80826).

PASTRAMI, GR/S24961/01