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.