## Towards a Product Form Solution for Stochastic Process Algebras

### Matteo Sereno

Dipartimento di Informatica, Universit`a degli Studi di Torino, Corso Svizzera 185, 10149 Torino, Italy

**We examine product form equilibrium distributions for stochastic process algebra**
**models, finding conditions that guarantee the existence of a solution for the traffic**
**equations. These equations are a set of linear equations, which are the basis of exact**
**analysis of product form models like queueing networks, stochastic Petri nets, as**
**well as stochastic process algebras.** **This paper illustrates how the equilibrium**
**distribution can be expressed as a product for a certain class of stochastic process**
**algebra models that satisfy certain conditions. Although the product form criterion**
**derived in this paper is developed in the context of Performance Evaluation Process**
**Algebra (PEPA), the results can be easily generalised to any of the other stochastic**
**process algebras.**

**1.** **INTRODUCTION**

The advantages of having structured modelling
paradigms have been pointed out by several authors
in recent years. Many efforts have been devoted to the
study of modelling techniques in which compositionality
plays a fundamental role. One outcome of the last years
is the definition of new paradigms for performance mod-
elling based on classical process algebras (CCS, CSP)
*which are known as Stochastic Process Algebras (SPAs).*

These include PEPA (Gilmore & Hillston, 1994; Hill-
*ston, 1994), MTIPP (Gotz et al., 1994; Hermanns &*

Rettelbach, 1994), Buchholz’s MPA (Buchholz, 1994)
*and Bernardo et al.’s MPA (Bernardo et al., 1994).*

A major drawback of these languages is the need to work at the state space level. Even for relatively small models the size of the state space is huge and this prevents the use of these formalisms for comput- ing performance measures of many interesting systems.

To overcome this problem solutions based on aggrega- tion techniques that avoid the construction of the entire state space of the model have been proposed (Hillston, 1995b; Ribaudo, 1995).

In this paper we approach the state space explosion
problem using different arguments by characterising
*SPA models that exhibit Product Form (PF) equilib-*
rium distribution.

The PF criterion for SPAs presented here is derived
*from the PF for SPNs derived by Henderson et al. and*
presented in several papers, see for instance (Boucherie

*& Sereno, 1994; Henderson et al., 1989; Henderson &*

Taylor, 1991).

Our goal is to import the results derived for SPNs into the stochastic process algebra environment. This would be the starting point for further investigations.

The availability of a PF criterion for SPAs could be combined with the typical features of SPAs (for in- stance compositionality) to obtain efficient computa- tional methods for the computation of performance measures.

Although the product form criterion derived in this paper is developed in the context of PEPA (Hillston, 1994), the results can be easily generalised to any of the other stochastic process algebras.

The paper is organised as follows. In Section 2 we first introduce some notation. Sections 3 and 4 contain the main results while some examples are given in Section 5.

Finally, Section 6 concludes the paper outlining possible future work on this topic.

**2.** **INTRODUCTORY DEFINITIONS**

Performance Evaluation Process Algebra (PEPA) is an algebraic description technique based on a classical pro- cess algebra (Hoare, 1985; Milner, 1989) and enhanced with timing information. This extension allows one to compute performance measures as well as to deduce qualitative properties of the modelled systems. In this section we briefly introduce PEPA. More detailed in- formation can be found in (Gilmore & Hillston, 1994;

Hillston, 1994).

Process algebras are mathematical theories which
model concurrent systems by their algebra and provide
a tool for reasoning about the structure and behaviour
of the model. Systems are viewed as collections of
*agents who execute actions. In PEPA actions take time*
and exponentially distributed random variables repre-
*senting their duration are associated with them.*

*An activity a ∈ Act is described as a pair (α, r),*
*where α ∈ A is the type of the activity and r ∈ IR*^{+} is

the parameter of the negative exponential distribution associated with the action. Activities may be passive and in this case the rate is unspecified and it is denoted by>.

*Systems are described as interactions of components*
that perform a set of activities and the syntax for de-
scribing such components is the following

P ::= (α, r).P | P + Q | P

### ><

_{L}Q | P/L | A Prefixing is the basic mechanism to build the be- haviour of components: (α, r).P carries out the activity (α, r) and then behaves like P .

The component P + Q enables activities of P and Q.

*A race condition governs the dynamic behaviour of a*
model whenever more than one activity is enabled. This
means that we may think of all the activities attempting
*to proceed, but only the fastest succeeding. The first*
activity to complete in P + Q determines its behaviour.

The component P

### ><

_{L}Q represents a system where processes P and Q work together to perform some activ-

*ities. The set L is called the cooperation set and defines*the action types on which the components must syn-

*chronise or cooperate. P and Q proceed independently*with any activities whose types do not occur in the co- operation set L. However, activities with action types in the set L are assumed to require the simultaneous involvement of both components.

When the set L is empty,

### ><

_{L}has the effect of par- allel composition, allowing components to proceed con- currently without any interaction between them. In this case the concise notation P ||Q is usually used.

The component P/L behaves as the component P
except that any activities of types within the set L are
*hidden, meaning that their type is not visible. Instead*
they appear as the unknown type τ and can be regarded
as an internal delay by the component. The rate of
the activity is unaffected by hiding. When a type has
been hidden within a component the component cannot
participate in a cooperation on that type.

*It is assumed that there is a countable set of con-*
*stants. Constants are components whose meaning is*
given by defining equation such as A^{def}= P which gives
the constant A the behaviour of P .

Definition 1. *If P* ^{(a,r)}−→ P^{0}*, then P*^{0}*is a (one-step)*
*derivative of P . In general, P*^{0} *is a derivative of P if*
P ^{(a}−→ · · ·^{1}^{,r}^{1}^{)} ^{(a}−→ P^{n}^{,r}^{n}^{)} ^{0}*.*

These derivatives are the states of the labelled multi- transition system. For any PEPA component the set of derivatives which can evolve from the component can be defined recursively.

Definition 2. *The derivative set of a PEPA com-*
*ponent Sys is denoted ds(Sys) and it can be defined as*
*the smallest set of components such that:*

### •

^{if Sys}^{def}

^{= Sys}

^{0}

^{then Sys}^{0}

^{∈ ds(Sys);}### •

^{if Sys}^{i}

*∈ ds(Sys) and there exists a ∈ Act(Sys*i)

*such that Sys*i−→ Sysa j

*, then Sys*j

*∈ ds(Sys).*

Thus derivative set is the set of components which
capture reachable states of the system. These form the
nodes of the transition diagram representing the possi-
ble behaviours of the system, this graph is called the
*derivation graph.*

The Markov process underlying any finite PEPA com- ponent can be obtained directly from the derivation graph. A state of the Markov process is associated with each node of the graph and the transitions be- tween states are defined by the arcs of the graph. Since all activity durations are exponentially distributed, the total transition rate between two states will be the sum of the activity rates labelling arcs connecting the corre- sponding nodes in the derivation graph.

To ensure that the underlying Markov process is er- godic, the derivation graph of a PEPA model must be strongly connected. Some necessary conditions for er- godicity, at the syntactic level of a PEPA model, have been defined in (Hillston, 1994).

From the necessary condition for ergodicity it follows
that we can define the syntax of PEPA expressions in
*terms of sequential components S and model components*
P (Hillston, 1995a):

P ::= S | P

### ><

_{L}P | P/L S ::= (α, r).S | S + S | A

In the following we will consider only PEPA models with a structure such that the underlying Markov chain is ir- reducible with finite state space and positive-recurrent states. It follows that all PEPA models that are de- scribed in this paper represent systems with steady state behaviour.

The states of a PEPA model are syntactic terms, or derivatives. A model component consists of one or more cooperating sequential components, and these cooper- ating components will be apparent in every derivative of the model. The sequential components involved in the model and the cooperation sets remain static through- out the evolution of the model. Only the particular derivative exhibited by each of the sequential compo- nents may change. This allows one to obtain a more compact and useful representation of any state. The next two definitions allow us to formalise this compact representation of the states of a PEPA model (Hillston, 1995a).

Definition 3. *Let Sys be a model component com-*
*prised of sequential components S*1, S2, . . . , SK*. Then*
*a state vector of the model component Sys as deriva-*
*tive Sys*i *is the vector (S*1i, S2i, . . . , SKi*) where S*hi*,*
1*≤ h ≤ K is the current derivative of S*h *in Sys*i*.*

Definition 4. *A sequential component S*k *is said*
*to be redundant within the state vector representation of*
*a model component Sys if S*k *is a sequential component*
*of Sys and for all derivatives Sys*i *∈ ds(Sys) given*

(P

1

;P

1

;Q

1 )

(P

2

;P

1

;Q

1

) (P

1

;P

2

;Q

1 ) (a

1

;r

1 )

(P

2

;P

2

;Q

1 ) (P

3

;P

1

;Q

2

) (P

1

;P

3

;Q

2 )

(P

3

;P

2

;Q

2 ) (P

2

;P

3

;Q

2 ) (a

1

;r

1 )

(a

1

;r

1 ) (a

1

;r

1 ) (a

3

;r

3 )

(a

3

;r

3 )

(a

3

;r

3

) (a

3

;r

3 ) (a

2

;r

2

) (a

2

;r

2 )

(a

2

;r

2

) (a

2

;r

2 )

**FIGURE 1. Derivation graph of the PEPA model of Example 1**

*the current derivatives of the sequential components S*ji*,*
*j 6= k, the current derivative of S*k*, S*ki *can be inferred.*

If a sequential component is redundant within a state
*vector, a reduced state vector may be obtained in which*
the derivatives of this component have been eliminated.

Example 1. Consider a system defined as P1 def

= (a1, r1).P2

P2

def= (a2, r2).P3

P3 def

= (a3, r3).P1

Q1 def

= (a1, >).Q1+ (a2, >).Q2

Q2

def= (a3, >).Q1

Sys ^{def}= (P1||P1)

### ><

{a1,a2,a3}(Q1)

Figure 1 shows the derivation graph of this PEPA model. In this figure the derivatives are represented as state vectors.

From the previous figure we can observe it is possi-
*ble to group the derivatives in strong equivalence classes*
(Hillston, 1995b). This equivalence relation groups to-
gether all the states that can be obtained by permu-
tation of the sequential components inside cooperat-
ing components. For instance the partition into strong
equivalence classes of the derivative set of the previous
PEPA model is

### {

^{{(P}

^{1}

^{, P}

^{1}

^{, Q}

^{1}

^{)}

^{} ,}

{(P2, P1, Q1), (P1, P2, Q1)} , {(P2, P2, Q1)} ,

{(P_{3}, P1, Q2), (P1, P3, Q2)} ,
{(P_{3}, P2, Q2), (P2, P3, Q2)}

### }

^{.}

It is easy to see that this partitioning satisfies the lumpability conditions, see (Hillston, 1995b).

Using this equivalence notion we can derive an use- ful representation of the state vector of a given strong equivalence class.

Definition 5. *Let Sys be a model component com-*
*prising sequential components S*1, S2, . . . , SK *and N the*
*number of distinct sequential derivatives that can be ex-*
*hibited in Sys. If Sys*i*∈ ds(Sys) then the strong equiv-*
*alence class to which the state vector (S*1i, S2i, . . . , SKi)
*belongs can be represented as the equivalence vector*
**m = (m**1i, m2i, . . . , mNi*), where m*li *(for l = 1, . . . , N )*
*records the instances of S*li *exhibited in Sys*i*.*

In the PEPA model of Example 1 there are only two sequential components (P and Q) but there are five distinct sequential derivatives (P1, P2, P3, Q1, Q2).

Figure 2 shows the aggregation of the derivation graph presented in Figure 1.

(2;0;0;1;0)

(1;1;0;1;0)

(0;2;0;1;0) (a

1

;2r

1 )

(a

1

;r

1 )

(a

2

;r

2 )

(1;0;1;0;1)

(a

2

;2r

2 )

(0;1;1;0;1)

(a

3

;r

3 )

(a

3

;r

3 )

**FIGURE 2. Aggregate representation of the derivation graph**
of the PEPA model of Example 1

In the following we call the set of all the equiva-
*lence vectors the aggregate derivation set (denoted by*

ads(Sys)).

Let us introduce two definitions that will be used to derive the PF-criterion. Let Sys be a model compo- nent comprising sequential components S1, S2, . . . , SK. WithAct(Sys) we denote the set of actions of Sys.

*For any action a ∈ Act(Sys) we define the pre-set*
of a (P re(a)) as the set of components that enable the
*action a. In an analogous way we define the post-set of*
a as the set of components which might result from the
completion of the action a.

The pre- and the post-sets of the actions of the PEPA model of Example 1 are

action pre-set post-set a1 {P1, Q1} {P2, Q1} a2 {P2, Q1} {P3, Q2} a3 {P3, Q2} {P1, Q1}

In general the syntax of the language allows one to have the same action occurring in different instances within the same component (perhaps with different rates), but for the purposes of this paper we need an additional restriction due to the fact that an action can- not have more than one pre-set. To achieve this goal we assume that the actions of any sequential compo- nent must have different names. Moreover, actions of the same name belonging to distinct sequential compo- nents must occur in cooperation (synchronisation). The impact of this assumption on the language is an issue that has yet to be addressed.

The next examples show situations that are not al- lowed.

Example 2. Consider a system defined as P1 def

= (a1, r1).P2

P2 def

= (a2, r2).P3

P3

def= (a1, r3).P1

Sys ^{def}= P1||P1||P1

the pre- and the post-sets of the actions of Sys are action pre-set post-set

a1 {P1} , {P3} {P2, P1} a2 {P2} {P3}

Action a1 does not satisfy the previous assumption because it has two distinct pre-sets.

Example 3.

P1

def= (a1, r1).P2

P2 def

= (a2, r2).P3

P3

def= (a3, r3).P1

Q1 def

= (a1, >).Q2

Q2 def

= (a3, r4).Q1

Sys ^{def}= P1

### ><

{a1}Q1

the pre- and the post-sets of the actions of Sys are action pre-set post-set

a1 {P_{1}, Q1} {P_{2}, Q2}

a2 {P_{2}} {P_{3}}

a3 {P3} , {Q2} {P1} , {Q1}

The previous assumption is not satisfied by action a3; it is satisfied by a1 because this action belongs to the cooperation set.

In an analogous way to the equivalence vector rep-
**resentation for the state vector, we denote by P re(a)**
**and P ost(a) the equivalence vector representation of**
the pre- and post-set of the action a. Using this nota-
tion an action a enabled in one of the derivatives rep-
**resented by the equivalence vector m can be seen as a**
transformation

**n + P re(a)** **−→ n + P ost(a),**^{a}

**where n is the equivalence vector representation of the**
**states obtained from any vector represented by m by**
removing the set of components of the pre-set of a.

**2.1.** **Markov chain model**

Assume that the finite PEPA model Sys^{def}= Sys0com-
prising sequential processes S1, S2, . . . , SK can be rep-
resented by a stable regular, continuous-time Markov
**chain X =**{X(t), t ≥ 0}, such that X(t) = {Sysi} in-
dicates that the system, at time t, behaves as one of
the components in the strong equivalence class to which
Sysi belongs. The state space of this Markov chain is
**ads(Sys). A state m represents a strong equivalence**
class. The rate at which an action a is executed in
**state m is**

**q(P re(a), P ost(a); m − P re(a)) =**
µ(a)**Φ(m−P re(a))**

**Φ(m)** **p(P re(a),P ost(a)),** (1)
**with m and m− P re(a) + P ost(a) ∈ ads(Sys). We**
have added the *state* *depending* function
**Φ(m− P re(a))/Φ(m) in the transition rates to ac-**
count for the state-dependent service rate in the ag-
gregate CTMC.

The transition rate from state **m to state**
**m**^{0} **= m− P re(a) + P ost(a) in the Markov chain X**
is

**q(m, m**^{0}) = X

n + Pre(a)=m, n + Post(a)=m’

**q(P re(a), P ost(a), n).** (2)

**A collection of positive numbers, w = (w(m),**
**m ∈ ads(Sys)), is called an invariant measure for the****Markov chain X, if it satisfies the following equations**

X

m’ ∈ ads(Sys)

### {

^{w(m)q(m, m}^{0}

^{)}

^{− w(m}^{0}

^{)q(m}^{0}

^{, m)}### }

^{= 0, (3)}

**for all m** ∈ ads(Sys). The previous equations are
**called the global balance equations for X. When w is***a proper distribution over ads(Sys) it is called equi-*
*librium distribution, in this case it will be denoted by*
**π = (π(m), m ∈ ads(Sys)).**

In the literature several more restrictive forms of bal-
ance exist (see (van Dijk, 1993) for details). In par-
*ticular, it is well known that a form of local balance is*
the common feature for all performance models with
*product form equilibrium distribution.* In this paper
*we will use the group-local-balance property (Boucherie*

& van Dijk, 1991) to prove that the proposed prod-
uct form distribution is an equilibrium distribution. A
measure w satisfies the group-local-balance property
**for the Markov chain X if for all g, g**^{0}**, n such that**
**n + g ∈ ads(Sys)**

X

**g**06=**g**

### {

**w(n + g)q(g, g**

^{0}

**; n) +**

**−w(n + g**^{0}**)q(g**^{0}**, g; n)**

### }

^{= 0,}

^{(4)}

**where g and g**^{0} represent the equivalence vector of the
pre- and the post-sets of actions. If we sum the group-
**local-balance equations over all g, n such that n+g = m**
we obtain the global balance equations.

**2.2.** **The role of the function Φ(·)**

The aim of this section is to clarify the role played by the function Φ(·).

Example 4. Consider a system defined as C1 def

= (a1, r1).C2

C2 def

= (a2, r2).C1

Sys ^{def}= C1||C_{1}||C_{1}

the pre- and the post-sets of the actions of Sys are action pre-set post-set

a1 {C_{1}} {C_{2}}
a2 {C_{2}} {C_{1}}

Figure 3 shows the derivation graph of this PEPA model. In this figure the derivatives are represented as state vectors.

The partition into strong equivalence classes of the derivative set of the previous PEPA model is

### {

^{{(C}1, C1, C1)} ,

{(C2, C1, C1), (C1, C2, C1), (C1, C1, C2)} ,
{(C_{2}, C2, C1), (C2, C1, C2), (C1, C2, C2)} ,
{(C2, C2, C2)}

### }

^{.}

Figure 4 shows the aggregation of the derivation graph presented in Figure 3.

To compute the rate at which an action a is executed
**in state m = n + P re(a) we must count the num-**
ber of transitions in the derivation graph that bring

(3;0)

(2;1)

(1;2)

(0;3) (a

1

;3r

1

) (a

2

;r

2 )

(a

1

;2r

1 )

(a

2

;2r

2 )

(a

1

;r

1 )

(a

2

;3r

2 )

**FIGURE 4. Aggregate representation of the derivation graph**
of the PEPA model of Example 4

the PEPA system from one of the derivatives repre-
**sented by n + P re(a) to one of the derivatives rep-**
**resented by n + P ost(a). Let us consider the effect of**
action a on the i-th (for i = 1, . . . , N ) component of the
**equivalence vector m. We know from Definition 5 that**
mi = ni + P rei(a) records the number of sequential
components that behave as Si. The action a trans-
forms P rei(a) of the mi components. The number of
transitions in the derivation graph that are represented
by the transition of the aggregate derivation graph

ni+ P rei(a)−→ n^{a} i+ P osti(a)

is equal to the number of different combinations of P rei(a) objects chosen between a set of ni+ P rei(a) and can be obtained by

(P rei(a))!

ni+ P rei(a) P rei(a)

= (ni+ P rei(a))!

ni! .
Note that we restricted our attention to the i-th compo-
**nent of the vector m. Let us denote by D(m, P re(a))**
the number of transitions in the derivation graph that
are represented by the transition

**n + P re(a)−→ n + P ost(a)**^{a}

in the aggregated derivation graph. Using the previous reasoning we can obtain that

**D(m, P re(a)) =**

(m1)!(m2)! . . . (m*N*)!

(m1*−P re*1(a))!(m2*−P re*2(a))! . . . (m*N**−P re**N*(a))!. (5)
If the function Φ(·) is defined as

**Φ(m) =** 1

(m1)!(m2)! . . . (mN)! (6) we obtain that

**Φ(m−P re(a))**

**Φ(m)** =

(m1)!(m2)! . . . (m*N*)!

(m1*− P re*1(a))!(m2*− P re*2(a))! . . . (m*N**− P re**N*(a))!

a

1

(C

1

;C

1

;C

1 )

a

2

(C

2

;C

1

;C

1 )

(C

2

;C

2

;C

1 )

(C

1

;C

2

;C

1

) (C

1

;C

1

;C

2 )

(C

2

;C

1

;C

2

) (C

1

;C

2

;C

2 ) a

2 a

1

a

1

a

2

a

1 a

2 a

1 a

2

a

1 a

2

a

1 a

2 a

1 a

2

a

2

(C

2

;C

2

;C

2 ) a

1

a

1 a

2

a

1

a

2

**FIGURE 3. Derivation graph of the PEPA model of Example 4**

**= D(m, P re(a)).**

The previous reasoning gives an interpretation for the function Φ(·) that has been introduced in the expression of the rates in the aggregated derivation graph (Equa- tion 1).

In the PEPA model of Example 4 we can see that the rates between states in the aggregated derivation graph can be computed as shown in the table below (note that 0! = 1).

Transition Rate

[3, 0]−→ [2, 1]^{a}^{1} _{(3−1)!}^{3!} r1 = 3r1

[2, 1]−→ [1, 2]^{a}^{1} _{(2−1)!·1!}^{2!·1!} r1= 2r1

[1, 2]−→ [0, 3]^{a}^{1} _{(1−1)!·2!}^{1!·2!} r1= r1

[0, 3]−→ [1, 2]^{a}^{2} _{(3−1)!}^{3!} r2 = 3r2

[1, 2]−→ [2, 1]^{a}^{2} _{1!·(2−1)!}^{1!·2!} r2= 2r2

[2, 1]−→ [3, 0]^{a}^{2} _{2!·(1−1)!}^{2!·1!} r2= r2

**3.** **THE ROUTING PROCESS**

The central feature of this PF-criterion is to consider
the actions of the PEPA model to be themselves states
*in a Markov chain, which we call the routing process.*

This is achieved by considering the pre- and post-sets of the PEPA system to be states of this Markov chain.

Using the equivalence vector of pre- and the post-sets we define the setR as

R = [

a∈Act(Sys)

**P re(a) ∪** [

a∈Act(Sys)

**P ost(a).**

The set R contains all the equivalence vectors of the pre- and the post-sets of actions of Sys.

Define single step transition probabilities of the set R as

**p(b, b**^{0}**) = P rob(P re(a), a, P ost(a))**

**whenever there exists an action a with b = P re(a),**
**b**^{0} **= P ost(a). Otherwise let p(b, b**^{0}) = 0.

Note that the requirement that no action can have more that one pre-set means that these probabilities are well defined.

*Define the routing chain as a Markov chain*
**y = (y(τ), τ ≥ 0)**

whose state space isR with transition rates
qy**(b, b**^{0}**) = µ(a)p(b, b**^{0}),

**where b = P re(a), b**^{0} **= P ost(a), and µ(a) is the rate**
*of the action a. The global balance equations for the*
**routing chain y are**

X

a^{0}∈Act(Sys)

### {

**f (P re(a)) · µ(a) · p(P re(a), P re(a**

^{0})) +

**−f(P re(a**^{0})) µ(a^{0}**) p(P re(a**^{0}**), P re(a))**

### }

^{= 0,}

^{(7)}

for all a ∈ Act(Sys). These equations represent the pro-
*cess algebra equivalent of the well-known traffic equa-*
*tions for queueing networks and stochastic Petri nets.*

This set of linear equations are the basis of the anal- ysis of PF-QNs, PF-SPNs, and Product Form Process Algebras as well.

**Remark (Traffic Equations)** In queueing network
literature the traffic equations are usually denoted by
ci =P_{N}

j=1cjpji (for i = 1, . . . , N ), where the ci-s are
the solutions of these equations and pji is the routing
probability from station j to station i. If we substitute
ci **= f (P re(i)) · µ(i) and p**ji **= p(P re(j), P re(i)) we**
can see that Equations (7) are equivalent to the stan-
dard traffic equations of queueing networks.

The next step is to establish the constraints that a PEPA model must satisfy to have an invariant measure

for the routing chain. The following definition and as- sumption are essential to this aim.

Definition 6. *For A ⊆ Act(Sys) define K(A), the*
*set of equivalence vectors of the pre-sets and post-sets*
*of actions in A, as*

K(A) = [

a∈A

**P re(a) ∪** [

a∈A

**P ost(a).**

*The subset of actions A is said to be closed if for any*
**l ∈ K(A) there exists a**^{0}, a^{00}**∈ A such that l = P re(a**^{0}*),*
**as well as l = P ost(a**^{00}*); that is, each post-set is also a*
*pre-set for an action in A, and vice-versa each pre-set*
*is also a post-set.*

The following assumption is the key to identify those PA components for which there exists a positive solution for the traffic equations.

Assumption 1. *Assume* *that* *all* *the* *actions*
*a ∈ Act(Sys) belong to at least one closed set, i.e.,*
*assume that for all a ∈ Act(Sys) there exists a subset*
*A ⊆ Act(Sys) such that a ∈ A and A is a closed set.*

Let ClA = {A1, A2, . . . , Ah} be the set of closed sets.

On this set we define an equivalence relation as fol-
lows. Let Ai, Aj ∈ ClA, we say that Ai, Aj *are in com-*
*mon pre-set relation (notation A*i P R Aj) if there exists
a ∈ Ai, b ∈ Aj **such that P re(a) = P re(b). The rela-**
tion P R^{∗} is the transitive closure of P R.

The relation P R^{∗} induces a partition of the set of
actions of the system into strong equivalence classes.

From the relation P R^{∗} we can also derive a partition
of the states of the routing chain. Define S(A) ⊆ S to
**be the set of states of y corresponding to the strong**
equivalence class to which the set A belongs.

The next theorem shows that the partition of ClA
into strong equivalence classes {P R^{∗}(A)}_{A ∈ ClA} ob-
tained from the relation P R^{∗} induces a partition
{S(A)}_{A ∈ ClA} of the set of states of the routing chain
if and only if Assumption 1 is satisfied.

Theorem 1. *Assumption 1 is necessary and suffi-*
*cient for the existence of an invariant measure of the*
*routing chain.*

**Proof We have to observe that the routing chain has**
an invariant measure if and only if the state space S
contains only irreducible sets. Therefore it is sufficient
to prove that Assumption 1 is a necessary and sufficient
condition for the partitioning of S into irreducible sets
{S(A)}_{A ∈ ClA}.

For any Ai, Aj∈ ClA if Ai P R^{∗} Ajthen by definition
of the sets S(·) we have that S(Ai) = S(Aj). If there
are two subsets A^{0}, A^{00}of the S and S(A^{0})∩ S(A^{00})6= ∅
then ∃ a ∈ Act such that a ∈ S(A^{0})∩ S(A^{00}) and a
belongs to both the strong equivalence classes P R^{∗}(A^{0})
and P R^{∗}(A^{00}), and hence P R^{∗}(A^{0}) = P R^{∗}(A^{00}). Hence
this shows that S(Ai) = S(Aj) if Ai P R^{∗} Aj.

We can see by Assumption 1 that P R^{∗} induces a
partition of S into irreducible sets. From the Perron-
Frobenius theorem (cf. Seneta (Seneta, 1981)) it follows

that there exists an invariant measure for the routing chain.

Conversely, assume that an invariant measure exists
for the routing chain. This implies that S is partitioned
in irreducible sets. Let Vi, i = 1, . . . v, denote the irre-
**ducible sets of y. Let a ∈ Act be an action and V**j be
**an irreducible set of states of y such that a ∈ V**j. Since
Vj is an irreducible set we have that for all v ∈ Vj there
exist two sequences of actions σ = ai1ai2. . . aip and
σ^{0} = aj1aj2. . . ajq with the following properties. Let
P, P^{0} be two components belonging to the derivative
set of Sys such that in the component P the ac-
tion a is enabled (i.e., P = (. . . , P re(a), . . .)), and
in the component P^{0} the action v is enabled (i.e.,
P^{0} = (. . . , P re(v), . . .)), then from the irreducibil-
ity of the set Vj it follows that P −→ · · ·^{a}^{i1} −→ P^{a}^{ip} ^{0}
and P^{0} −→ · · ·^{a}^{j1} −→ P . Thus the set of actions^{a}^{jq}

ai1, ai2, . . . , aip, aj1, aj2, . . . , ajq

is a closed set. Sim- ilarly, from the irreducibility we may conclude that all subsets of actions contained in Vjbelong to a closed set.

The traffic equations for the PEPA model are closely
**related to the global balance equations for y. The traffic**
equations are

X

a^{0}∈Act(Sys)

**f (P re(a)) · µ(a) · p(P re(a), P re(a**^{0})) =
X

a^{0}∈Act(Sys)

**f (P re(a**^{0})) µ(a^{0}**) p(P re(a**^{0}**), P re(a)).** (8)

The traffic equations balance the average rate at which
the the equivalence vector of the pre-set of an action a
**P re(a) is “absorbed” with the average rate at which**
**P re(a) is “formed”. We have to point out that this**
form of balance requires that P re(a) is the post-set of
some action a^{0} if P re(a) is the pre-set for an action a.

**4.** **CLOSED FORM SOLUTION**

Theorem 2. *Let Sys be a model component com-*
*prising sequential components S*1, S2, . . . , Sk*.* *With*
*Act(Sys) and ads(Sys) we denote the respectively*
*the set of actions and aggregate derivative set of*
*Sys.* *Assume that there exists an invariant mea-*
*sure f (·) for the traffic equations, and a function*
πf (·): ads(Sys) −→ IR^{+} *which have the property that,*
**for all a ∈ Act(Sys) and n + P re(a) in the aggregate***derivative set,*

πf**(n + P re(a))**

πf**(n + P re(b))** = **f (P re(a))**

**f (P re(b))**. (9)
**whenever p(P re(a), P re(b)) > 0.**

*Then the equilibrium distribution of Sys is given by*
**π(m) =** 1

G**Φ(m) π**f**(m), ∀ m ∈ ads(Sys),** (10)
*where G is a normalisation constant.*

**Proof To prove this theorem we have to show that the**
**measure Φ(m)π**f**(m) satisfies the group-local-balance**

X

a 0

6=a

f(

### m

^{)}

^{}

^{f}

^{(}

### m

^{)}

^{q}

^{(}

### Pre

^{(a);}

### Pre

^{(a}

^{0}

^{);}

### m Pre

^{(a))}

^{+}

(

### m Pre

^{(a)+}

### Pre

^{(a}

^{0}

^{))}

^{}

^{f}

^{(}

### m Pre

^{(a)+}

### Pre

^{(a}

^{0}

^{))}

^{q}

^{(}

### Pre

^{(a}

^{0}

^{);}

### Pre

^{(a);}

### m Pre

^{(a))}

^{g}

^{=}

Eq.(1)

= X

a 0

6=a

f(

### m

^{)}

^{}

^{f}

^{(}

### m

^{)(a)}

^{(}

### m Pre

^{(a))}

(

### m

^{)}

^{p}

^{(}

### Pre

^{(a);}

### Pre

^{(a}

^{0}

^{))}

^{+}

(

### m Pre

^{(a)+}

### Pre

^{(a}

^{0}

^{))}

^{}

^{f}

^{(}

### m Pre

^{(a)+}

### Pre

^{(a}

^{0}

^{))}

^{(a}

^{0}

^{)}

^{(}

### m Pre

^{(a))}

(

### m Pre

^{(a)+}

### Pre

^{(a}

^{0}

^{))}

^{p}

^{(}

### Pre

^{(a}

^{0}

^{);}

### Pre

^{(a))}

^{g}

= (

### m Pre

^{(a))}

^{X}

a 0

6=a f

f

(

### m

^{)}

^{(a)p}

^{(}

### Pre

^{(a);}

### Pre

^{(a}

^{0}

^{))}

^{}

^{f}

^{(}

### m Pre

^{(a)+}

### Pre

^{(a}

^{0}

^{))}

^{p}

^{(}

### Pre

^{(a}

^{0}

^{);}

### Pre

^{(a))}

^{g}

= (

### m Pre

^{(a))}

^{}

^{f}

^{(}

### m

^{)}

f

(

### m

^{)}

^{a}

^{X}

^{0}

^{6=a}

^{f}

^{f}

^{(}

### m

^{)}

^{(a)p}

^{(}

### Pre

^{(a);}

### Pre

^{(a}

^{0}

^{))}

^{}

^{f}

^{(}

### m Pre

^{(a)+}

### Pre

^{(a}

^{0}

^{))}

^{p}

^{(}

### Pre

^{(a}

^{0}

^{);}

### Pre

^{(a))}

^{g}

= (

### m Pre

^{(a))}

^{}

^{f}

^{(}

### m

^{)}

^{X}

a 0

6=a

f(a)p(

### Pre

^{(a);}

### Pre

^{(a}

^{0}

^{))}

^{}

^{f}

^{(}

### m Pre

^{(a)+}

### Pre

^{(a}

^{0}

^{))}

f

(

### m

^{)}

^{p}

^{(}

### Pre

^{(a}

^{0}

^{);}

### Pre

^{(a))}

^{g}

Eq.(7)

= (

### m Pre

^{(a))}

^{X}

a 0

6=a

f(a)p(

### Pre

^{(a);}

### Pre

^{(a}

^{0}

^{))}

^{f}

^{(}

### Pre

^{(a}

^{0}

^{))}

f(

### Pre

^{(a))}

^{p}

^{(}

### Pre

^{(a}

^{0}

^{);}

### Pre

^{(a))}

^{g}

= (

### m Pre

^{(a))}

^{f}

^{(}

### Pre

^{(a))}

f(

### Pre

^{(a))}

^{a}

^{X}

^{0}

^{6=a}

^{f(a)p}

^{(}

### Pre

^{(a);}

### Pre

^{(a}

^{0}

^{))}

^{f}

^{(}

### Pre

^{(a}

^{0}

^{))}

f(

### Pre

^{(a))}

^{p}

^{(}

### Pre

^{(a}

^{0}

^{);}

### Pre

^{(a))}

^{g}

= (

### m Pre

^{(a))}

^{X}

a 0

6=a

ff(

### Pre

^{(a))}

^{(a)p}

^{(}

### Pre

^{(a);}

### Pre

^{(a}

^{0}

^{))}

^{f}

^{(}

### Pre

^{(a}

^{0}

^{))}

^{p}

^{(}

### Pre

^{(a}

^{0}

^{);}

### Pre

^{(a))}

^{g}

Eq.(6)

= 0:

**FIGURE 5. Derivations of Theorem 2**

property (Equations (4)). The substitution of Φ(·)πf(·) and the expression of the rates (1) into the group-local- balance equations yields the derivations that are shown in Figure 5. This proves the theorem.

Conventionally “product form” has been associated with the equilibrium solution of Jackson queueing net- works which involves a product over the nodes of the queueing network. In the following it is shown how Jackson networks and their solution can be derived as a special case of the above results. Theorem 2 also gives a product form solution. The product in this case is

“hidden” in the function πf. This function is usually difficult to obtain from Equation (9). In the following we present some examples where this function is derived by analysing the “structure” of the PEPA system.

**5.** **EXAMPLES**

Example 5. Simple Jackson network (with ran- dom order service policy and infinite server semantics).

Consider the Jackson network depicted in Figure 6, where α, 1 − α denote the routing probabilities that a customer goes from station 1 to station 2 and from station 1 to station 3, respectively. A PEPA compo- nent that models the behaviour of a customer inside this queueing network is

Q1

def= (a^{0}_{1}, r^{0}_{1}).Q2+ (a^{00}_{1}, r^{00}_{1}).Q3,
Q2 def

= (a2, r2).Q1, Q3 def

= (a3, r3).Q1,

where aiis the action representing the service at station
i, r^{0}_{1}+ r_{1}^{00}= µ1, _{r}_{0}^{r}^{1}^{0}

1+r^{00}_{1} = α, _{r}0^{r}^{00}^{1}

1+r^{00}_{1} = 1− α, r2= µ2, and
r3 = µ3. If in the network there are N customers the
PEPA system can be defined as

QN^{def}= Q|1||Q_{1}{z|| . . . ||Q_{1}}

N times .

The equivalence vector of the model compo-
nent QN corresponding to one of the derivatives
of the strong equivalence class {QNi} is a triple
**m**_{i} = (m1i, m2i, m3i), where mhi, with 1 ≤ h ≤ 3,
is the number of derivatives in {QNi} that behave as
Qh. For instance if the state vector of the derivative
QNiis (Q1i, Q2i, . . . , QNi), such that Qki = Q1, for any
1 ≤ k ≤ N, then the equivalence vector representation
**of this state is m**_{i}= (N, 0, 0).

The pre- and the post-sets of the actions of this ex- ample are summarised in the table below.

action pre-set post-set
a^{0}_{1} {Q_{1}} {Q_{2}}
a^{00}_{1} {Q_{1}} {Q_{3}}
a2 {Q_{2}} {Q_{1}}
a3 {Q3} {Q1}

Note that since P re(a^{0}_{1}) = P re(a^{00}_{1}) we use P re(a1)
to denote pre-set of a^{0}_{1} and a^{00}_{1}.

It is easy to see that the PEPA component QN satis- fies Assumption 1 and hence there is a positive solution for the traffic equations (8). A solution to these equa- tions must satisfy the following equations

**f (P re(a**1))(r^{0}1+ r^{00}1**) = f (P re(a**2))r2**+f (P re(a**3))r3,
**f (P re(a**2))r2 **= f (P re(a**^{0}_{1}))r^{0}_{1},

**f (P re(a**3))r3 **= f (P re(a**^{00}_{1}))r_{1}^{00}.

**We can easily verify that f (P re(a))(r**^{0}_{1} + r_{1}^{00}) = 1,
**f (P re(a**2))r2 **= α, and f (P re(a**3))r3 = 1− α is a
solution to these equations. A function πf given by

πf**(m) =**
Y3
i=1

**f (P re(a**i))^{m}^{i}

**satisfies Equation (10) for all m**∈ ads(QN) and hence
the equilibrium distribution for the PEPA system is

**π(m) =** 1
G**Φ(m)**

Y3 i=1

**f (P re(a**i))^{m}^{i}.

1

**1**

**2** **3**

1

2

3

**FIGURE 6. Jackson queueing network**

Example 6. Queueing network with finite buffer capacity (with random order service policy and infinite server semantic).

Consider the queueing network depicted in Figure 7.

In this network station 3 has a buffer with finite capac- ity. It is well known that, in general, blocking prevents product form solution as it destroys the local balance property. It is worth noting that there are particu- lar blocking situations that preserve local balance and hence the product form solution (see (van Dijk, 1993) for details). In the network of Figure 7, if the cus- tomers are blocked when the buffer of station 3 is full, the network has product form solution. A PEPA com- ponent that models the behaviour of a customer inside

**1** **2**

2

**3**

3

1

**FIGURE 7. Queueing network with a finite capacity buffer**

the queueing network of Figure 7 is Q1 def

= (a1, r1).Q2, Q2

def= (a2, r2).Q3

Q3 def

= (a3, r3).Q1,

while the PEPA component that models a position in the buffer is

Buf^{0} ^{def}= (a1, >).Buf^{0}+ (a2, >).Buf^{00},
Buf^{00} ^{def}= (a3, >).Buf^{0}.

If in the queueing network there are N customers and the buffer of station 3 can contain up to M customers then the PEPA system that models the queueing net- work of Figure 7 (with random order service policy) is

BL^{def}= (Q1||Q_{1}|| . . . ||Q_{1})

| {z }

N times

### ><

{a1,a2,a3}

(Buf^{0}||Buf^{0}|| . . . ||Buf^{0})

| {z }

M times

.

The state vector of BL as derivative BLi is the vector (Q1i, . . . , QNi, Buf1i, . . . BufMi). Given the current derivative of the component Qh, i.e., Qhi

(1 ≤ h ≤ N) the current derivatives of the compo- nents Bufk (1 ≤ k ≤ M) can be inferred. Hence the sequential components Bufk are redundant (see Def- inition 4) and the state vector can be represented as (Q1i, . . . , QNi).

For this PEPA system we have that action pre-set post-set

a1 {Q_{1}, Buf^{0}} {Q_{2}, Buf^{0}}
a2 {Q_{2}, Buf^{0}} {Q_{3}, Buf^{00}}
a3 {Q_{3}, Buf^{00}} {Q_{1}, Buf^{0}}

Thus the system satisfies Assumption 1 and hence
there is a positive solution for the traffic equations. It
**is easy to check that f (P re(a**i))ri= 1, from which we
**can derive that f (P re(a**i)) = 1/ri, for 1≤ i ≤ 3.

The equivalence vector representation is
**m**_{i} = (m1i, m2i, m3i), where mhi (1 ≤ h ≤ 3) is the
number of derivatives in {BL_{i}} that behave as Q_{h}. A
function πf given by

πf**(m) =**
Y3
i=1

**f (P re(a**i))^{m}^{i}

**satisfies Equation (10) for all m**∈ ads(QN) and hence
the equilibrium distribution for the PEPA system is

**π(m) =** 1
G**Φ(m)**

Y3 i=1

**f (P re(a**i))^{m}^{i}.

Example 7. The taxi station system.

**market**
**garden**

**taxi station**

**customer**

**taxi**

**walk**

**taxi run**
**FIGURE 8. Taxi station system**

Consider the system depicted in Figure 8. In this system there are a given number of customers and a another one of taxis. If there is an available taxi in the taxi station a customer has two possibilities. He/she can take a taxi to go to the market. The taxi waits for the customer to complete the visit to the market and then it brings the customer back to the taxi station, becoming therefore available to other people. In Figure 8 this pos- sibility is represented by the right cycle. The customer can also choose to walk through the garden and then to go back to the taxi station (left cycle of Figure 8).

If there are no taxis in the taxi station a customer can only walk.

A PEPA component that models the behaviour of a customer inside the system depicted in Figure 8 is

C1

def= (a1, r1).C2+ (a3, r3).C3, C2

def= (a2, r2).C1

C3 def

= (a4, r4).C1,

while the PEPA component that models the behaviour of a taxi is

T1

def= (a3, >).T2, T2 def

= (a4, >).T1.

A taxi station system in which there are two customers and one taxi is modelled by

T S ^{def}= (C1||C1)

### ><

{a3,a4}(T1) .

The state vector of the model component T S as derivative T Si is the vector (C1i, C2i, T1i). The

equivalence vector representation is a five-tuple
**m**_{i} = (m1i, m2i, m3i, m4i, m5i), where the meaning of
the components can be resumed by the following table

component number of components
**m**_{i} in T Si that behave thus

m1i C1

m2i C2

m3i C3

m4i T1

m5i T2

From the structure of T S we can observe that the last
**component of the vector m**_{i} is redundant.

The pre- and the post-sets of the actions of T S are action pre-set post-set

a1 {C1} {C2} a2 {C2} {C1} a3 {C1, T1} {C3, T2} a4 {C3, T2} {C1, T1}

It is possible to see that the PEPA component T S sat- isfies Assumption 1 and hence there is a positive so- lution to the traffic equations. We can observe that the routing chain contains two irreducible sets of states

### {

**1**

^{{P re(a}**), P re(a**2)

**} , {P re(a**3

**), P re(a**4)}

### }

^{. A so-}

lution to the traffic equations must satisfy
**f (P re(a**1))r1 = **f (P re(a**2))r2,
**f (P re(a**2))r2 = **f (P re(a**1))r1,
**f (P re(a**3))r3 = **f (P re(a**4))r4,
**f (P re(a**4))r4 = **f (P re(a**3))r3.

**We can easily verify that f (P re(a**i))ri= 1 is a solution
**to these equations and hence f (P re(a**i)) = 1/ri, for
1≤ i ≤ 4. A function π_{f} given by

πf**(m)=**

**f (P re(a**1))
**f (P re(a**3))

_{m}_{1}

**f (P re(a**2))
**f (P re(a**4))

**f (P re(a**1))
**f (P re(a**3))

_{m}_{4}

=

r3

r1

_{m}_{1}
r4

r2

r3

r1

_{m}_{4}

**satisfies Equation (10) for all m** ∈ ads(T S) and hence
the equilibrium distribution for the the PEPA system
is

**π(m) =** 1
G**Φ(m)**

r3

r1

_{m}_{1}
r4

r2

r3

r1

_{m}_{4}
.

**6.** **CONCLUSIONS AND FURTHER WORK**
We have introduced some basic ideas for finding equi-
librium distributions based on “syntactic” analysis of a
SPA model rather than on state space analysis. Sev-
eral issues have yet to be addressed. We need for in-
stance to find a method to compute the function πf(·)
(Equation 9) as well as to derive efficient algorithms to
compute the normalisation constant (Equation 10).

The solution of these problems will provide a way to compute performance measure for a class of SPA models without analysing the state space.