AESOP home

Publications

Reversed processses, product forms, non-product forms and a new proof of the BCMP theorem

Peter G. Harrison

Conference or Workshop Paper
International Conference on the Numerical Solution of Markov Chains (NSMC 2003), Urbana IL, USA, September 2-5 2003
August, 2003
pp.289–304
Abstract

The equilibrium joint state probabilities of interacting Markov processes are obtained in a hierarchical way, by finding the reversed process of the interaction in terms of the reversed processes of the components. From a reversed process, a product-form solution for the joint state probabilities follows directly. The method uses a Markovian process algebra formalism and generalizes the recent Reversed Compound Agent Theorem (RCAT) to solve a diverse class of concurrent systems. This class includes processes with shared, exclusive resources, a customer-oriented specification of a last-come-first-served (LCFS) queue with Coxian service times and an extended PS queue with a non-product form solution. From these results, a new, very short proof of the BCMP theorem ensues. The principal advantage of the methodology is its potential for mechanisation and symbolic implementation. Indeed, many non-standard product-forms have emerged directly from the compositional approach.

PDF of full publication (277.8 kilobytes)
(need help viewing PDF files?)
GZipped Postscript of full publication (197.9 kilobytes)
(need help viewing GZipped Postscript files?)

Information from pubs.doc.ic.ac.uk/rcat2-nsmc.