AESOP home

Publications

Separable equilibrium state probabilities via time reversal in Markovian process algebra

Peter G. Harrison, Ting Ting Lee

Journal Article
Theoretical Computer Science
Volume 346
Issue 1
pp.161–182
November, 2005
Elsevier
DOI 10.1016/j.tcs.2005.08.007
Abstract

The Reversed Compound Agent Theorem (RCAT) is a compositional result that uses Markovian process algebra (MPA) to derive the reversed process of certain interactions between two continuous time Markov chains at equilibrium. From this reversed process, together with the given, forward process, the joint state probabilities can be expressed as a product-form, although no general algorithm has previously been given. This paper first generalizes RCAT to multiple (more than two) cooperating agents, which removes the need for multiple applications and inductive proofs in cooperations of an arbitrary number of processes. A new result shows a simple stochastic equivalence between cooperating, synchronised processes and corresponding parallel, asynchronous processes. This greatly simplifies the proof of the new, multi-agent theorem, which includes a statement of the desired product-form solution itself as a product of given state-probabilities in the parallel components. The reversed process and product-form thus derived rely on a solution to certain rate equations and it is shown, for the first time, that a unique solution exists under mild conditions - certainly for queueing networks and G-networks.

Notes

Special Issue of QAPL 2004

PDF of full publication (245.9 kilobytes)
(need help viewing PDF files?)
GZipped Postscript of full publication (194.5 kilobytes)
(need help viewing GZipped Postscript files?)

Information from pubs.doc.ic.ac.uk/marcat-ting-ting.