Compositional reversed Markov processes, with applications to G-networks

Stochastic networks defined by a collection of cooperating agents are solved for their equilibrium state probability distribution by a new compositional method. The agents are processes formalised in a Markovian Process Algebra, which enables the reversed stationary Markov process of a cooperation to be determined symbolically under appropriate conditions. From the reversed process, a separable (compositional) solution follows immediately for the equilibrium state probabilities. The well-known solutions for networks of queues (Jackson's theorem) and G-networks (with both positive and negative customers) can be obtained simply by this method. Here, the reversed processes, and hence product-form solutions, are derived for more general cooperations, focussing on G-networks with chains of triggers and generalised resets, which have some quite distinct properties from those proposed recently. The methodology's principal advantage is its potential for mechanisation and symbolic implementation; many equilibrium solutions, both new and derived elsewhere by customised methods, have emerged directly from the compositional approach. As further examples, we consider a known type of fork-join network and a queueing network with batch arrivals. (C) 2004 Elsevier B.V. All rights reserved.