Separable equilibrium state probabilities via time reversal in Markovian process algebra
File(s)marcat-ting-ting.ps.gz (194.52 KB)
Submitted version
Author(s)
Harrison, P
Lee, T
Type
Journal Article
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.
Date Issued
2005-11
Citation
Theoretical Computer Science, 2005, 346 (1), pp.161-182
ISSN
0304-3975
Publisher
Elsevier
Start Page
161
End Page
182
Journal / Book Title
Theoretical Computer Science
Volume
346
Issue
1
Copyright Statement
© 2005 Elsevier B.V. All rights reserved. NOTICE: this is the author’s version of a work that was submitted for publication in Theoretical Computer Science. Changes resulting from the publishing process, such as peer review, editing, corrections, structural formatting, and other quality control mechanisms may not be reflected in this document. Changes may have been made to this work since it was submitted for publication. A definitive version was subsequently published in THEORETICAL COMPUTER SCIENCE, VOL:346, ISSUE:1, (2005) DOI: 10.1016/j.tcs.2005.08.007
Source Volume Number
346