Computing Publications

Publications Home » Reversed processses, product form...

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
September, 2003

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 (278 kilobytes)
(need help viewing PDF files?)
GZipped Postscript of full publication (198 kilobytes)
(need help viewing GZipped Postscript files?)
BibTEX file for the publication
Conditions for downloading publications from this site. built & maintained by Ashok Argent-Katwala.