The theory of interactive generalized semi-Markov processes.
In this paper we introduce the calculus of interactive generalized semi-Markov processes (IGSMPs), a stochastic process algebra which can express probabilistic timed delays with general distributions and synchronizable actions with zero duration, and where choices may be probabilistic, non-deterministic and prioritized. IGSMP is equipped with a structural operational semantics which generates semantic models in the form of generalized semi-Markov processes (GSMPs), i.e. probabilistic systems with generally distributed time, extended with action transitions representing interaction among system components. This is obtained by expressing the concurrent execution of delays through a variant of ST semantics which is based on dynamic names. The fact that names for delays are generated dynamically by the semantics makes it possible to define a notion of observational congruence for IGSMP (that abstracts from internal actions with zero duration) simply as a combination of standard observational congruence and probabilistic bisimulation. We also present a complete axiomatization for observational congruence over IGSMP. Finally, we show how to derive a GSMP from a given IGSMP specification in order to evaluate the system performance and we present a case study.
Introduction
Stochastically timed process algebras (see e.g. [20,12,1,6,10,16,28,5,11,17,22])
are formal specication languages which describe concurrent systems both
from the viewpoint of interaction and from the viewpoint of performance. They
extend the expressiveness of classical process algebras by introducing a notion
of time in the form of delays with probabilistic duration. The advantages of integrating
the description of interaction with the description of performance are
Preprint submitted to Elsevier Preprint 26 June 2000
several. First of all we can specify and analyze systems for combined behavioral
and performance properties, e.g. via a notion of integrated equivalence, that
relates terms with the same behavioral and performance characteristics. In
doing this we can take advantage of the feature of compositionality oered by
process algebras, which describe a concurrent system in term of the behavior
of its composing processes. Secondly, we can analyze behavioral and performance
properties of a system, separately on two projected semantic models
(a standard transition system labeled with actions and a stochastic process
with some kind of Markov property), which are automatically derived from the
initial integrated specication. This has the advantage that such models are
guaranteed to be consistent, since they are formally derived from the same
initial integrated specication.
A lot of work has been previously done in the eld of Markovian process algebras
(see e.g. [20,6,17] and the references therein). They are stochastically
timed process algebras, where the probabilistic distribution of a delay is assumed
to be exponential. This causes the passage of time to be \memoryless"
and has the consequence that the system behavior can be described (via interleaving
operational semantics) by expressing the execution of a time delay
as an atomic transition without explicitly representing durations for delays.
Moreover the limitation to exponential distributions allows a straightforward
transformation of the semantic model of a system into a Continuous Time
Markov Chain (CTMC ). The limitation imposed over durations is very strong
from a modeling viewpoint because, e.g., not even deterministic (xed) durations
can be expressed. The capability of expressing general probabilistic
distributions would give the possibility of producing much more realistic spec-
ications of systems. Even system activities which have an uncertain duration
could be represented probabilistically by more adequate distributions than
exponential ones (e.g. Gaussian distributions or experimentally determined
distributions).
Some previous eorts have been done in order to try to extend the expressiveness
of Markovian process algebras to probabilistic time with general distribution
[12,1,10,16,28,5,11,22]. The main point in doing this is to understand
how to dene semantic models and semantic reasoning, e.g. the denition of
an adequate notion of bisimulation based equivalence. In probability theory
systems capable of executing parallel activities with generally distributed durations
are represented by Generalized Semi-Markov Processes (GSMPs) [24].
Previously [5] we have studied how to develop an adequate operational semantics
for a process algebra with general distributions which generates semantic
models in the form of GSMPs. In [5] we have shown that the problem of representing
time delays in semantic models is basically the same as describing
the behavior of a system via ST semantics [13,4,9,7]. According to ST seman-
tics, the evolution of a delay is represented in semantic models, similarly as
in GSMPs , as a combination of the two events of delay start and delay ter-
mination, where the termination of a delay is uniquely related to its start by,
e.g., identifying each delay with a unique name. As we will see this approach is
very natural for expressing time delays, especially when a duration is expressed
through general probability distributions. Moreover the use of ST semantics
leads to a notion of choice among delays which is based on preselection policy.
A choice among alternative delays is resolved by rst performing a probabilistic
choice among the possible delays, and then executing the selected delay.
Therefore the choice of a delay is naturally represented in semantic models as
a probabilistic choice among transitions representing delay starts. As we also
show in [5] this method of solving choices, compared to the race policy used in
Markovian process algebras, is very adequate and simple when dealing with
generally distributed durations. On the other hand this adheres to the fact
that, while in CTMC probabilistic choices are implicitly expressed through a
\race" of exponential distributions, in GSMPs they are explicitly expressed
via a probabilistic selection mechanism. From the semantic model of a system,
derived in this way, it is easy to derive a performance model in the form of a
GSMP . A GSMP can then be analyzed through well established mathematical
or simulative techniques in order to obtain performance measures of the
system (see e.g. [14]).
In this paper we consider a variant of the algebra of [5] that allows us to dene
a notion of observational congruence which abstracts from internal computations
which are not visible from an external observer ( actions). This
is desirable because it may lead to a tremendous state space reduction of
semantic models. Technically this is obtained by restricting the possible durations
of synchronizable actions to zero durations only. More precisely, following
an approach which is quite usual in real-time process algebras (see e.g. [27])
and which has been imported in the stochastic process algebra community
in [19,17], we distinguish between actions f representing a delay whose duration
is given by the probability distribution f (itself) and standard actions of
CCS/CSP [25,21] (including internal  actions) with zero duration. In analogy
to [17] we call the resulting algebra: calculus of Interactive Generalized Semi-Markov
Processes. The name re
ects the separated orthogonal treatment of
delays and standard actions.
Following the ideas of [5], we dene the operational semantics of a delay f
in IGSMP through ST semantics. Hence a delay is represented in semantic
models as a combination of the event of start of the delay f + and the event of
termination of the delay f . Moreover we assign names (consisting of indexes
i) to delays so that the execution of a delay is represented by the two events
i and f i and no confusion arises (in the connection between delay starts
and delay terminations) when multiple delays with the same distribution f
are concurrently executed.
In this paper we employ the new technique for expressing ST semantics that
we have introduced in [7] which is based on dynamic names. As opposed to
the technique employed in [5], which is based on static names, the technique
we use here allows us to establish equivalence of systems via the standard
notion of bisimulation (so that existing results and tools can be exploited),
nevertheless preserving the possibility of obtaining nite ST semantic models
even in the case of recursive systems. By exploiting the fact that this technique
is also compositional, we dene ST semantics through Structural Operational
Semantics (SOS) and we produce a complete axiomatization for ST bisimulation
over nite state processes.
As in [5], we resolve choices among several delays by means of preselection
policy. We associate with each delay a weight w: in a choice a delay is selected
with probability proportional to its weight. For instance <f; w>:0+<g;w 0 >:0
represents a system which performs a delay of distribution f with probability
a delay of distribution g with probability w
are expressed in semantic models by associating weights to transitions f
representing the start of a delay.
The semantics of standard actions a (including internal actions ) in IGSMP
is just the standard interleaving semantics. This re
ects the fact that these
actions have zero duration and can be considered as being executed atomically.
As in [19,17] the choice among standard actions is just non-deterministic. We
can express external choices (e.g. a + b) which are based on the behavior
of other system components, but also non-deterministic internal choices (e.g.
which cannot be resolved through interaction. This can be seen as
an expressive feature, since it allows for an underspecication of the system
performance, but has the drawback that it makes sometimes impossible to
derive a purely probabilistic model of the system (see Sect. 4). We assume
the so-called maximal progress [27]:  actions have priority over delays, thus
expressing that the system cannot wait if it has something internal to do, i.e.
We present a formal procedure for transforming the semantic model obtained
from a suitable specication of a system (see Sect. 4) into a GSMP . Such a
procedure just turns each delay of the system into a dierent element of the
GSMP and system weighted choices into probabilistic choices of a GSMP .
Finally, as an example of modular IGSMP specication, we consider Queueing
Systems G=G=1=q, i.e. queuing systems with one server and a FIFO queue
with q-1 seats, where interarrival time and service time are generally dis-
tributed. Moreover we show how to derive the performance model of such
queuing systems (a GSMP) by applying the formal procedure above.
Summing up, the contribution of this work is a weak semantics for a language
expressing generally distributed durations, probabilistic choices (preselection
policy), non-determinism and priority. The use of the technique of [7] for
expressing ST bisimulation allows us to dene observational congruence for
IGSMP simply as a combination of the standard notion of observational congruence
and probabilistic bisimulation [23] and to produce a complete axiomatization
for this equivalence. Moreover we show how to automatically derive
GSMPs from IGSMP specications and we present the example of Queueing
Systems G=G=1=q.
The paper is structured as follows. In Sect. 2 we present the calculus of Interactive
GSMPs and its operational semantics. In Sect. 3 we present the notion
of observational congruence and its complete axiomatization. In Sect. 4 we
present the formal procedure for deriving a GSMP from a complete system
specication. In Sect. 5 we present the example of Queueing Systems G=G=1=q.
Finally, in Sect. 6 we report some concluding remarks including comparison
with related work and directions for future research.
2 The Calculus of Interactive GSMPs
2.1 Syntax of Terms and Informal Semantics of Operators
The calculus of interactive GSMPs is an extension of a standard process algebra
with operators of CCS/CSP [25,21], which allows us to express priority,
probabilistic choices and probabilistic delays with arbitrary distributions. This
is done by including into the calculus, in addition to standard actions, a special
kind of actions representing delays. Delays are represented as <f; w> and
are characterized by a weight w and a duration distribution f . The weight
w determines the probability of choosing the delay in a choice among several
delays. The set of weights is R
I ranged over by w; w :. The duration distribution
f denotes the probability distribution function of the delay duration.
The set of duration probability distribution functions is i.e. the set
of probability distribution functions f such that ranged
over by f , g, h. The possibility of expressing priority derives from the inter-relation
of delays and standard  actions. In particular we make the maximal
progress assumption: the system cannot wait if it has something internal to
do. Therefore we assume that, in a choice,  actions have priority over delays,
behaves as :P .
Let Act be the set of action types containing a distinguished type  representing
an internal computation. Act is ranged over by a; b;
I be the set of delays. 1 Let Var be a set of
1 In the following we consider f to be a shorthand for <f; 1> when this is clear
process variables ranged over by X; Y; Z. Let ARFun
Act fgg be a set of action relabeling functions,
ranged over by '.
Denition 2.1 We dene the language IGSMP as the set of terms generated
by the following syntax
where fg. An IGSMP process is a closed term of IGSMP . We
denote by IGSMP g the set of strongly guarded terms of IGSMP . 2
\0" denotes a process that cannot move. The operators \:" and \+" are the
CCS prex and choice. The choice among delays is carried out through the
preselection policy by giving each of them a probability proportional to its
weight. Note that alternative delays are not executed concurrently, rst one
of them is chosen probabilistically and then the selected delay is executed.
Moreover  actions have priority over delays in a choice. \=L" is the hiding
operator which turns into  the actions in L, \[']" is the relabeling operator
which relabels visible actions according to '. \k S " is the CSP parallel operator,
where synchronization over actions in S is required. Finally \recX" denotes
recursion in the usual way.
2.2 Operational Semantics
As we will formally see in Sect. 4.3, a Generalized Semi-Markov Process
(GSMP) represents the behavior of a system by employing a set of elements,
which are similar to the clocks of a timed automata [3]. Each element has
an associated duration distribution (element lifetime) and its execution in a
GSMP is characterized by the two events of start (when the element is born)
and termination (when the element dies).
Since IGSMPs extend GSMPs with the capability of interacting via standard
actions, the semantic model of an IGSMP process is a labeled transition sys-
tem, where a transition represents a basic event: the execution of a standard
action, the start of a delay or the termination of a delay.
Similarly as in GSMPs , the execution of a delay is represented in semantic
models by the two events of delay start and delay termination and enough
information is provided (delays are given unique element names) in order to
ensure that each event of delay termination is uniquely related to the corresponding
event of delay start. This corresponds to representing the execution
from the context.
2 We consider the delay <f; w> as being a guard in the denition of strong
guardedness.
of delays with ST semantics [13,4,9,7]. As we also show in [5] this semantics
is just what we need for representing durational actions, if the duration is
expressed with general probability distributions. On the other hand, by employing
a realization of ST semantics based on the identication of delays
with names, the eect of applying ST semantics to an IGSMP process is to
generate the names for elements of the underlying GSMP .
While in [5] ST semantics is expressed by assigning static names to delays
according to their syntactical position in the system, here we employ a new
technique for generating ST semantic models, that we have introduced in [7],
which is based on dynamic names, i.e. names computed dynamically while
the system evolves. The advantage of this technique is that it allows us to
establish ST bisimulation of systems via the standard notion of observational
congruence [25] and to preserve the niteness of ST semantic models even
in the presence of recursion. On the contrary a technique for establishing
ST bisimulation of two processes based on static names must employ a more
complex denition of bisimulation which associates the names of the delays
of one process with the names of the corresponding delays used by the other
one [4,5].
In IGSMP the technique of [7] is employed for giving semantics to delays.
The \type" of a delay is simply its duration distribution and what we observe
of a system is its ability of performing delays of certain types f 2 PDF
The problem of preserving the relationship between starts and terminations
of delays arises, like in the ST semantics of standard process algebras, when
several delays of the same type f are being executed in parallel. When a delay
f terminates (event f ) we need some information for establishing which event
of delay start (f refers to. The technique introduced in [7] is based on the
idea of dynamically assigning, during the evolution of the system, a new name
to each delay that starts execution, on the basis of the names assigned to the
delays already started. Names consist of indexes that distinguish delays with
the same duration distribution. In particular the event of a delay start <f; w>
is represented in semantic models by a transition labeled by <f
is the minimum index not already used by the other delays with distribution
f that have started but not yet terminated. This rule for computing indexes
guarantees that names are reused and that nite models can be obtained also
in the presence of recursion. The termination of the delay is simply represented
by a transition labeled by f i , where the \identier" i uniquely determines
which delay f is terminating. Since the method to compute the index for
a starting delay is xed, it turns out that delays of processes that perform
the same execution traces of delays get the same names. As a consequence,
contrary to [4,5], ST bisimilarity can simply be checked by applying standard
bisimilarity to the semantic models of processes.
Moreover the technique introduced in [7] allows us to dynamically assign
names to delays, according to the rule formerly described, via SOS semantics
(hence in a compositional way) through the idea of levelwise renaming. In
order to obtain structural compositionality it is necessary to determine, e.g.
in the case of the parallel composition operator, the computations of P k Q
from the computations of P and Q. This is done by parameterizing in state
terms each parallel operator with a mapping M . For every delay f started
by records the association between the name f i , generated according
to the xed rule above for identifying f at the level of P k S;M Q, and
the name f j (which in general is dierent from f i ), generated according to
the same rule for identifying the same delay f inside P (or Q). In this way
when, afterwards, such a delay f terminates in P (or Q) the name f j can be
re-mapped to the correct name f i at the level of P k S;M Q, by exploiting the
information included in M . In M the delay f of P k S;M Q which gets index
i is uniquely identied by expressing the unique name j it gets in P or in Q
and the \location" of the process that executes it: left if P , right if Q. Such an
association is represented inside M by the triple (f;
indices
I location loc 2 stands for left and
\r" for right. In the following we use f : (i; loc j ) to stand for (f;
The weight w associated with the start of a delay determines, as already
explained, the probability that the delay is chosen in spite of other delays
and, therefore, the probability that the delay starts.
As it is natural in the context of a stochastic process algebra, we assume delay
starts to be urgent. Therefore we have that, if a system state can perform a
delay start, it does not let time pass, so possible delays in execution cannot
terminate in that state. This causes another form of priority in our language:
the priority of delay starts over delay terminations, i.e. <f
Summing up, we have two forms of priority in our semantic models: the priority
of  actions over delays (starts or terminations) and the priority of delay starts
over delay terminations. As opposed to [17], where a similar notion of priority
is captured in the denition of equivalence among systems, we prefer to express
priority by cutting transitions which cannot be performed directly in semantic
models (a solution also hinted in [18]). This allows us to have smaller semantic
models and to dene the notion of equivalence more simply, without having
to discard any transitions when establishing bisimulation.
In order to dene the operational semantics for the processes of IGSMP ,
we need a richer syntax to represent states. Let TAct
I be the set of delay starts, where <f
a:P
a
a
a
P a
a
P a
a 2 L
P a
'(a)
P a
a
2S Q a
a
P a
a
a
PfrecX:P=Xg a
recX:P a
Fig. 1. Standard Rules
represents the beginning of the delay <f; w> identied by i. 3 Besides let
I be the set of delay terminations,
represents the termination of the delay with duration distribution
f identied by i.  ranges over Act [ TAct [ TAct We denote
an index association, whose elements are associations (i; loc j ), with iassoc
which ranges over the set IAssoc of partial bijections from N
I + to Loc  N
I
Finally a mapping M is a relation from PDF + to N
I
is a set including an independent index
association for each dierent duration distribution.
The set IGSMP s of state terms of IGSMP is generated by the following syntax:
We denote by IGSMP sg the set of strongly guarded terms of IGSMP s . We
consider the operators \k S " occurring in a IGSMP term P as being \k S;; "
when P is regarded as a state.
The semantics of state terms produces a transition system labeled over Act [
3 In the following we consider f
i to be a shorthand for <f
when this is clear
from the context.
4 Given a relation M from A to B, we denote with M a the set fb Mg.
;w>
Fig. 2. Rules for Start Moves
;w>
PfrecX:P=Xg
recX:P
Fig. 3. Rules for Termination Moves
TAct [TAct , ranged over by
:. The transition relation is dened by
the standard operational rules of Fig. 1 and by the two operational rules in
the rst part of Fig. 2 and Fig. 3.
The rule of Fig. 2 denes the transitions representing the start of a delay, by
taking into account the priority of \" actions over delays and by employing
the function SM . SM (P ) evaluates the multiset of start moves leaving state
represented as pairs (<f
are the derivatives of
the moves. We use multisets so that we take into account several occurrences
of the same weight w. SM (P ) is dened by structural induction as the least
element of Mu fin (TAct satisfying the rules in the second
part of Fig. 2. The meaning of the rule for P k S;M Q is the following. When P
performs
i then a new index n(M f ) is determined for identifying the delay
f at the level of \k S;M " and the new association added to
M . The function
I computes the new index to be used for
identifying the delay f that is starting execution by choosing the minimum
index not used by the other delays f already in execution:
dom(iassoc)g. A symmetric mechanism takes place for a move f
i of Q.
The function melt : Mu fin (TAct
dened in the third part of Fig. 2, merges the start moves with the same label
and the same derivative state by summing their weights.
The rule of Fig. 3 denes the transitions representing the termination of a
delay, by taking into account the priority of \" actions over delays and the
priority of delay starts over delay terminations, and by employing the auxiliary
transition > !. The transition relation > !, labeled over TAct , is
dened in the second part of Fig. 3. The meaning of the operational rules
for \P k S;M Q" is the following. When P performs f i the delay f with index
j associated to l i in M terminates at the level of the parallel operator. A
symmetric mechanism takes place for a move f i of Q.
Note that even if the two rules in the rst part of Fig. 2 and Fig. 3 include
negative premises, the operational semantics is nevertheless correct [15].
This because negative premises are not in the rules which induce on the term
structure, but only in \top-level" rules. Moreover the denition of delay start
transitions of Fig. 2 is based on the denition of standard action transitions
of Fig. 1 only, and the denition of delay termination transitions of Fig. 3 is
based on the denition of standard action transitions of Fig. 1 and of delay
start transitions of Fig. 2.
We are now in a position to dene the integrated (representing both interaction
and performance) semantic model of a process.
5 We denote by Mu fin (S) the set of nite multiset over S, we use fj and jg as
multiset parentheses, and we use  to denote multiset union.
O/
O/ O/-
-f .recX.f.X O/
O/
O/
f
f
recX.f.X
recX.f.X
recX.f.X
{ f:(2,l )
Fig. 4. Example of recursive system
Denition 2.2 The integrated semantic model I[[P is the
labeled transition system (LTS) dened by:
where:
is the least subset of IGSMP sg such that:
TAct is the set of labels.
is the restriction of ! to S P  L  S P .
Example 2.3 In Fig. 4 we depict the integrated semantic model of
In the following theorem, where we consider \P=L", \P [']", and \P k S P" to
be static operators [25], we show that nite semantic models are obtained for
a wide class of recursive systems.
Theorem 2.4 Let P be a IGSMP g process such that for each subterm recX:Q
of P , X does not occur free in Q in the context of a static operator. Then P
is a nite state process.
Proof The proof of this theorem derives from the fact that the number of
states of the semantics of P which dier only for the contents of mappings
parameterizing parallel operators, are always nite, because the maximum
index a delay may assume is bounded by the maximum number of processes
that may run in parallel in a state.
Note that the class of processes considered in this corollary includes strictly
the class of nets of automata, i.e. terms where no static operator occurs in the
scope of any recursion.
3 Observational Congruence for IGSMP
The notion of observational congruence for IGSMP is dened, similarly as
in [19,17], as a combination of the classical notion of observational congruence
[25] and the notion of probabilistic bisimulation of [23].
In our context we express cumulative probabilities by aggregating weights.
Denition 3.1 The function
I
which computes the aggregated weight that a state P 2 IGSMP sg reaches a
set of states C 2 P(IGSMP sg ) by starting a delay with duration distribution
is dened as:
;w>
We are now in a position to dene the notion of strong bisimilarity for terms
of IGSMP sg . Let NPAct TAct , the set of non-probabilistic actions,
be ranged over by .
Denition 3.2 An equivalence relation  over closed terms of IGSMP sg is a
strong bisimulation i P  Q implies
for every  2 NPAct ,
for every f 2 PDF + and equivalence class C of ,
Two closed terms are strongly bisimilar, written P  Q, i
is included in some strong bisimulation.
We consider  as being dened also on the open terms of IGSMP sg by extending
strong bisimilarity with the standard approach of [25].
The denition of weak bisimilarity is an adaptation of that presented in [19,17]
to our context.
Let
a sequence of transitions including
a single  transition and any number of  transitions. Moreover we dene
possibly empty sequence of
6 The summation of an empty multiset is assumed to yield 0. Since the method for
computing the new index of a delay f that starts in a state P is xed, we have that
several transitions f leaving P have all the same index i.
transitions. Moreover we let C  denote the set of processes that may silently
evolve into an element of C, i.e. C
Qg.
Denition 3.3 An equivalence relation  over closed terms of IGSMP sg is a
for every  2 NPAct ,
equivalence class C of ,
Two closed terms are weakly bisimilar, written P  Q, i
is included in some weak bisimulation.
Dierently from [19,17] we do not need to express conditions about the stability
of bisimilar processes because we consider only strongly guarded processes.
As a consequence there is no process of IGSMP sg that is forced in a  loop
and we do not have to recognize this situation. A justication for the fact that
we do not consider processes with weakly guarded recursion is the following
one. A process that is forced in a  loop can be seen as a Zeno process, i.e. a
processes which performs innite computations without going beyond a certain
point in time. Discarding weakly guarded processes allows us to avoid the
technical complications deriving from the treatment of Zenoness (see [8]) and
on the other hand seems not to be so restrictive.
Similarly as in [19,17] it is possible to reformulate weak bisimilarity in the
following way, which is simpler but less intuitive.
Lemma 3.4 An equivalence relation  over closed terms of IGSMP sg is a
for every  2 NPAct ,
equivalence class
C of ,
The proof that this reformulation is correct derives from that given in [17],
simply by substituting rates of exponential distributions with weights.
The denition of observational congruence, where again we discard the requirement
about stability, is the following one.
Denition 3.5 Two closed terms are observational congru-
f
< , >Fig. 5. Minimal semantic model
for every  2 NPAct ,
for every  2 NPAct ,
for every f 2 PDF + and equivalence class C of ,
Again we consider ' as being dened also on the open terms of IGSMP sg by
extending observational congruence with the standard approach of [25].
Theorem 3.6 ' is a congruence w.r.t. all the operators of IGSMP , including
recursion.
Proof The proof of this theorem follows the lines of the similar proof in [25]
that is adapted to our setting. The only relevant case is that of parallel composition
operator. It su-ces to show that f(P 1 k S;M Q;
is a (weak) bisimulation.
Example 3.7 In Fig. 5 we depict the minimum semantic model for the recursive
system of Fig. 4, which is obtained by merging bisimilar states. The
weight 2 of the initial transition derives from the aggregation of the weights of
the two initial transitions in the model of Fig. 4. However since in the initial
state there is no alternative to such a transition, its weight is not relevant for
the actual behavior (in isolation) of the system.
3.1 Axiomatization
In this section we present an axiom system which is complete for ' on nite
state IGSMP sg terms.
The axiom system A IGSMP for ' on IGSMP sg terms is formed by the axioms
presented in Fig. 6. In this gure \bb" and \j" denote, respectively, the left
merge and synchronization merge operators (see e.g. [2]). Moreover  ranges
We recall from Sect. 2.2 that
The axioms (P ri1) and (P ri2) express the two kinds of priorities of IGSMP ,
respectively, priority of  actions over (semi-)delays and priority of delay starts
over delay terminations. The axiom (Par) is the standard one except that
when the position of processes P and Q is exchanged we must invert left and
right inside M . The inverse M of a mapping M is dened by
Mg. Axioms (LM4) and (LM5) just
re
ect the operational rules of the parallel operator for a delay move of the
left-hand process. The axioms (Rec1 strongly guarded recursion
in the standard way [26].
If we consider the obvious operational rules for \bb S;M " and \j S;M " that derive
from those we presented for the parallel operator 7 then the axioms of A IGSMP
are sound.
A sequential state is dened to be one which includes \0", \X" and operators
\:", \+", \recX" only; leading to the following theorem.
Theorem 3.8 If an IGSMP sg process P is nite state, then 9P
Proof Let s be the states of the operational semantics of P , s n  P .
It can be easily seen that for each exist J i and  i;j , k i;j with
where
0. Then for each
i, from 1 to n, we do the following. If i is such that 9j 2
by applying (Rec3), that s
Then we replace each subterm s i occurring in the equations for s
its equivalent term. When, in the equation for s n  P , we have replaced s n 1 ,
we are done.
For sequential states the axioms of A IGSMP involved are just the standard
axioms of [26], and the axioms for priority and probabilistic choice. From
Theorem 3.8 and by resorting to arguments similar to those presented in [26]
and [17] we derive the completeness of A IGSMP .
Theorem 3.9 A IGSMP is complete for ' over nite state IGSMP sg processes.
Proof The proof of this theorem follows the lines of the proof of [26]. In
particular weights are treated as rates of exponential distributions in the proof
of [17].
7 The denition of the operational rule for \j S;M " must allow for actions \" to be
skipped [2], as re
ected by axiom (SM4).
Y is not free in recX:P
strongly guarded in P
Fig. 6. Axiomatization for IGSMP
Example 3.10 Let us consider the system recX:f:X k ; recX:f:X of the previous
example. In the following we show how this process can be turned
into a sequential process by applying the procedure presented in the proof
of Theorem 3.8. In the following we
stand for <f
and we abbreviate
A IGSMP '
Initially we note that
by applying (Rec2) and (TAct). We start the procedure of the proof of Theorem
3.8 with the initial state P k ;;; P . We have:
by applying (Par), (LM4) and (SM3). From this equation we derive:
by applying (P rob). Then, we have:
by applying (Par), (LM4), (LM5), (SM3) and (P ri2). Then, we have:
by applying (Par), (LM5) and (SM3). From this equation we derive:
by applying (Par), (A1) and (SM1) to P k ;;ff:(1;r 1 )g P 0 . Finally we have:
by applying (Par), (LM4), (LM5), (SM3) and (P ri2). Now we perform the
second part of the procedure where we generate recursive processes and we
substitute states with equivalent terms. We start with
the state does not occur in its equivalent term we do not have to generate any
recursion. Substituting the state with its equivalent term in the other equations
generates the new equation:
Then we consider the state P 0 k ;;ff:(1;l 1 );f:(2;r 1 )g P 0 . We change its equation by
generating a recursion as follows:
Substituting the state with its equivalent term in the remaining equations
generates the new equation:
Now we consider the state P 0 k ;;ff:(1;l 1 )g P . We change its equation by generating
a recursion as follows:
Substituting the state with its equivalent term in the remaining equations
generates the new equation:
Therefore we have turned our initial system recX:f:X k ; recX:f:X into the
recursive sequential process <f
that the operational semantics of this process generates the labelled transition
system of Fig. 5.
4 Deriving the Performance Model
In this section we show how to formally derive a GSMP from a system speci-
cation. In particular this transformation is possible only if the specication
of the system is complete both from the interaction and from the performance
point of view.
A specication is complete from the interaction viewpoint if the system spec-
ied is not a part of a larger system which may in
uence its behavior, hence
when every standard action appearing in its semantic model is an internal
action. Note that the states of the semantic model of such a system can be
classied as follows:
choice states: states whose outgoing transitions are all (weighted) delay
starts
timed states: states whose outgoing transitions are all delay terminations
silent states: states whose outgoing transitions are all  actions
A specication is complete from the performance viewpoint if all the choices in
which the specied system may engage are quantied probabilistically. This
means that the semantic model must not include silent states with a non-deterministic
choice among dierent future behaviors. In other words a silent
state either must have only one outgoing  transition, or all its outgoing
transitions must lead to equivalent behaviors. This notion can be formally
dened as follows: A semantic model is complete w.r.t. performance if it can
be reduced, by aggregating weakly bisimilar states (see Sect. 3), to a model
without silent states.
Provided that a system P 2 IGSMP g satises these two conditions, we now
present a formal procedure for deriving the GSMP representing the performance
behavior of P from its integrated semantic model I[[P
4.1 Elimination of  Actions
The rst phase is to minimize the state space S P by aggregating states that
are equivalent according to the notion of weak bisimulation dened in Sect. 3.
Since we supposed that the system P satises the two conditions above, a side
eect of this minimization is that all  actions disappear from I[[P ]].
We denote the resulting LTS with (S P;m stands
for \minimal". We have [TAct , hence S P;m includes only choice
states and timed states.
4.2 Solution of Choice Trees
The second phase is the transformation of every choice tree present in the
semantic model into a single probabilistic choice. A choice tree is formed by
the possible choice paths that go from a given choice state (the root of the
tree) to a timed state (a leaf of the tree). Note that such trees cannot include
loops composed of one or more transitions, because after each delay start the
number of delays in execution strictly increases. To be precise, such trees are
directed acyclic graphs (DAGs) with root, since a node may have multiple
incoming arcs. The choice trees are
attened into a single choice that goes
directly from the root to the leaves of the tree, with the following inductive
procedure.
Initially (at step 0) we transform our semantic model by turning all weights
into the corresponding probability values. We denote the resulting LTS with
stands for \probabilistic", dened by:
I [0;1] [ TAct , where positive real numbers represent probabilities
;w>
where:
;w>
Hence now we have a semantic model with delay termination transitions and
probabilistic transitions labeled by a probability prob. Note that delay start
events are removed from transition labels. The occurrence of such events becomes
implicit in the representation of system behavior similarly as in GSMPs .
At the k-th step, beginning from the LTS (S P;p;k
eliminate a node in a choice tree, thus reducing its size. This is done by considering
a choice state s 2 S P;p;k 1 with incoming probabilistic transitions. Such
transitions are removed and replaced by a new set of probabilistic transitions
which are determined in the following way. Each incoming probabilistic transition
is divided into multiple transitions, one for each probabilistic transition
that leaves the state s. Its probability is distributed among the new transitions
in parts that are proportional to the probabilities of the transitions that
leave s. Moreover, if s has no incoming delay termination transitions, then s
is eliminated together with its outcoming probabilistic transitions. Therefore
the resulting LTS (S P;p;k ; L
where:
s
The algorithm terminates when we reach k for which
choice state with incoming probabilistic transitions. Since at every step we
eliminate a node in a choice tree of the initial semantic model, thus reducing
its size, we are guaranteed that this will eventually happen. Let t be such k.
The LTS that results from this second phase is denoted by (S
If the nodes of a choice tree are eliminated by following a breadth-rst visit
from the root, it can be easily seen that the time complexity of the algorithm
above is just linear in the number of probabilistic transitions forming the tree
(the DAG). This because by following this elimination ordering, each node to
be eliminated has one ingoing probabilistic transition only.
4.3 Derivation of the GSMP
Now we show how to derive a generalized semi-Markov processes from the
semantic model obtained at the end of the previous phase.
A generalized semi-Markov process (GSMP) [24] is a stochastic process dened
on a set of states fs j s 2 Sg as follows. In each state s there is a set of
active elements ElSt(s) taken from a set El, that decay at the rate C(e; s),
El. The set El is partitioned into two sets El 0 and El  with
El  . If e 2 El 0 the element e has an exponentially distributed lifetime, if
instead e 2 El  it has a generally distributed lifetime. Whenever in a state
s an advancing element e dies, the process moves to the state s 0 2 S with
probability
A GSMP can be represented by a tuple:
where:
S is the set of the states of the GSMP .
El is the set of the elements of the GSMP .
is a function that associates with each element the
distribution of its lifetime.
El is a function that associates with each state the set of its
active elements.
I + is a partial function that associates a decay rate with
each active element of each state. C is partial because for each s 2 S it is
dened only for the (e; s) such that e 2 ElSt(s).
a relation that represents the transitions between
the states of the GSMP . They are labeled by the element e 2 El that
terminates. We include only transitions for which P r(s;
P r is a function that associates a (non zero) probability with each transition
of the GSMP (relation !). The meaning of P r is: if in s an element e
terminates, with probability P r(s; e; s 0 ) the process moves into state s 0 . For
what we said in the previous item, P r is never zero over its domain, whilst
it is considered as zero outside.
I [0;1] is a function that associates with each state the probability
that it is the initial state.
Note that, given a tuple dening a GSMP , the sets El 0 and El  are derived in
the following way (where Exp() is the exponential distribution with rate
With respect to the general denition of a GSMP given above, we have that in
an IGSMP all elements (delays) decay at rate 1, i.e. they all advance uniformly
with time at the same speed.
The performance semantic model P[[P is derived from the
The elements of the GSMP are the \identied" delays f i labeling the transitions
of ! P;p . The states of the GSMP are the timed states of S P;p .
A transition leaving a state of the GSMP is derived beginning from a delay
termination transition leaving the corresponding timed state of S P;p and, in
the case this transition leads to a choice state, from a probabilistic transition
leaving this state. The timed state of S P;p reached in this way is the state of
the GSMP the derived transition leads to. Note that we are certain to reach
a timed state because all choice trees have been solved and, consequently (see
Sect. 4.2) choice states cannot have incoming probabilistic transitions. Each
transition of the GSMP is labeled by the element f i terminating in the corresponding
termination transition. The probability associated with a transition
of the GSMP (function P r) is the probability of the corresponding probabilistic
transition (or probability 1 if the transition is derived from a delay
termination transition leading directly to a timed state).
The performance semantics of an IGSMP process P is dened as follows.
Denition 4.1 The performance semantics P[[P of a process P 2 IGSMP g
is a GSMP represented by the tuple:
where:
We let
be the unique prob such that:
P init is dened as follows:
8 The transition relations ! 1 and ! 2 are disjoint. This because the only
transition in ! P;p that leaves state s and is labeled by a given element f i , leads
either to a choice state or to a timed state.
Example 4.2 In Fig. 7 we show the GSMP derived, by applying the formal
translation we have presented, from the integrated semantic model of Fig. 4. In
particular the GSMP is obtained, as described above, from the minimal model
of Fig. 5. Since such model does not include standard action transitions the
system considered is complete both from the interactive and the performance
viewpoints. In the GSMP of Fig. 7 the states are labeled by the active elements
and the transitions with the terminating elements. The probability P r
associated to each transition of the GSMP that is shown in the picture is 1.
Moreover P init is 1 for the unique state of the GSMP (it is pointed by the
arrow to outline the fact that it is the initial state). The elements
represent the delays f 1 and f 2 respectively, and the probability distribution
function of both is given by function f .
Fig. 7. Derived GSMP
5 Example: Queueing Systems G/G/1/q
In this section we present an example of specication with IGSMP . In particular
we concentrate on Queuing Systems (QSs) G=G=1=q, i.e. QSs which
have one server and a FIFO queue with q-1 seats and serve a population of
unboundedly many customers. In particular the QS has an interarrival time
which is generally distributed with distribution f and a service time which is
generally distributed with distribution g.
Such a system can be modeled with IGSMP as follows. Let a be the action
representing the fact that a new customer arrives at the queue of the service
center, d be the action representing that a customer is delivered by the queue
to the server. The process algebra specication is the following one: 9
9 In the specication we use process constants, instead of the operator \recX", to
denote recursion. The reason being that the use of constants is suitable for doing
QS G=G=1=q
Arrivals
Queue h
d:Queue h-1
Queue q-1
d:Queue q-2
Server
d:g:Server
We have specied the whole system as the composition of the arrival process,
the queue and the server which communicate via action types a and d. Then
we have separately modeled the arrival process, the queue, and the server. As a
consequence if we want to modify the description by changing the interarrival
time distribution f or the service time distribution g , only component Arrivals
or Server needs to be modied while component Queue is not aected. Note
that the role of actions a and d is dening interactions among the dierent
system components. Such actions have zero duration and they are neglected
from the performance viewpoint.
In Fig. 8 we show I[[QS G=G=1=q ]]. In this picture A stands for Arrivals, A 0 stands
for f :a:Arrivals, A 00 stands for a:Arrivals. Similarly, S stands for Server , S 0
stands for g:Server , S 00 stands for g :Server . Moreover, Q h stands for Queue h ,
for any h. We omit parallel composition operators in terms, so, e.g., AQ h S
stands for Arrivals k fag (Queue h
In order to derive the performance model of the system QS G=G=1=q we have to
make sure that it is complete both from the interaction and the performance
viewpoints. In Fig. 8 we have visible actions a and d, therefore the behavior
of the system can be in
uenced by interaction with the environment and is
not complete. We make it complete by considering QS G=G=1=q =fa; dg so that
every action in the semantic model of Fig. 8 becomes a  action.
As far as completeness w.r.t. performance is concerned, we present in Fig. 9
the minimal version of I[[QS G=G=1=q =fa; dg]], obtained by aggregating weakly
bisimilar states (see Sect. 3). Since in the minimal model there are no longer
internal  actions, we have that our system is complete also w.r.t. performance.
By applying the formal procedure dened in Sect. 4, hence by solving choice
trees in the minimal model of Fig. 9, we nally obtain the GSMP of Fig. 10.
The probability P r associated to each transition of the GSMP is 1. P init is 1
for the state pointed by the arrow and 0 for all the other states. The elements
e 1 and e 2 represent the delays f and g.
specications, while the use of operator \recX" is preferable when dealing with
axiomatizations. The two constructs are shown to be completely equivalent in [25].
f
f
f
a
d
a
d
a
d
a
f
a
d
a
d-2 d-2
d-2 A'Q S'
d-2
d-2
a
d
Fig. 8. Integrated Semantic Model
f
f
f
f
f
d-2 A'Q S'
d-2 AQ S"
d-2
Fig. 9. Minimal Semantic Model
6 Conclusion
In this section we present some related work and we outline some open problems
left for future research.
Fig. 10. Derived GSMP
6.1 Related work
Several algebraic languages which express generally distributed durations like
IGSMP have been previously developed. We start from the languages that
follow a completely dierent approach in representing the behavior of systems.
In [10] a truly concurrent approach to modeling systems is proposed which
employs general distributions. From a term of the algebra presented in [10]
a truly concurrent semantic model (a stochastic extension of a bundle event
structure) is derived that represents statically the concurrency of the system by
expressing the components of the system and the causal relationships among
them. Therefore the behavior of the system is not described by representing
explicitly all possible global system states as it happens in labeled transition
systems. In this way a very concise semantic model is obtained where duration
distributions can be statically associated with durational actions. The
drawback of this approach is that the semantic models produced must nevertheless
be translated to a transition system form before their performance can
be evaluated. This because in GSMPs the evolution of a stochastic process is
represented in such a form. Another algebraic approach to modeling systems
with general distributions is the discrete event simulation approach [16,11].
For example in [16] an algebra is developed that extends CCS with temporal
and probabilistic operators in order to formally describe discrete event simu-
lations. Such algebra employs actions with null duration (events) and delays
similarly as in IGSMP . The states produced by the operational semantics include
explicitly the residual durations of delays (as real numbers), hence the
semantic models of systems are not nite. This approach excludes a priori the
possibility of making mathematical analysis of such models by means of established
theoretical results such as analytical solution methods for (insensitive)
GSMPs [24].
Other languages have been previously developed, that are more similar to
IGSMP , in that they represent the behavior of specied systems via labeled
transition systems which are (in many cases) nite. According to these approaches
[12,28,22] the execution of durational actions is represented in an
abstract way, as in IGSMP , without including explicitly their residual durations
(as real numbers) in states. In [12] the technique of \start reference"
is employed in order to have a pointer to the system state where an action
begins its execution. In [28], instead, information about causality relations
among actions is exploited in order to establish the starting point of actions.
In a recent work [22] a methodology for obtaining nite semantic models from
the algebra of [16] is dened, which is based on symbolic operational seman-
tics. Such semantics generates symbolical transition systems which abstract
from time values by representing operations on values as symbolic expres-
sions. The drawback of these approaches is that the structure of the semantic
models generated is very dierent from that of GSMPs. It is therefore not always
clear how to derive a performance model for a specied system and [22]
only provides a (quite involved) procedure for deriving a GSMP from systems
belonging to a certain class.
The languages that are closest to IGSMP , in that they produce semantic models
which represent probabilistic durations as in GSMPs are those of [1,5,11].
In particular such semantic models represent the performance behavior of systems
by means of (some kind of) clocks with probabilistic duration which
can be easily seen as the elements of a GSMP . With the language of [1],
performance models are derived from terms specifying systems by applying
to them a preliminary procedure that gives a dierent name to each durational
action of the term. In this way, each name represents a dierent clock
in the semantic model of the system. In the approach of [1] the events of
action starts are not explicitly expressed in the semantic models and choices
are resolved via the race policy (alternative actions are executed in parallel
and the rst action that terminates wins) instead of the preselection policy
as in IGSMP . The language of [11] is endowed with an abstract semantics
which may generate nite intermediate semantic models (from these models it
is then possible to derive the innite models which are used for discrete event
simulation). With this language clock names must be explicitly expressed in
the term that specify the system and the fact that a dierent name is used
for each clock is ensured by imposing syntactical restrictions in terms. As in
IGSMP the execution of a clock is represented by the events of clock start
and clock termination, but here these two events must be explicitly expressed
in the term specifying a system and they are not automatically generated by
the operational semantics. Unfortunately the language of [11] can only express
choices between events of clock terminations (which are resolved through race
policy) and cannot express probabilistic choices which are a basic ingredient
of GSMPs . With the language we have previously developed in [5], clock
names and events of start and termination are automatically generated, as in
IGSMP , by the operational semantics. In this way system specications can
simply express general distributed delays as probability distribution functions
and we do not have to worry about clock names and events. A drawback of
the approaches of [1,5,11] w.r.t. IGSMP is that there is no easy way to decide
equivalence of systems (hence to minimize their state space). This is because
in order to establish the equivalence of two systems it is necessary to associate
in some way the names of the clocks used by one system with the names of
the corresponding clocks used by the other one. Trying to extend the notion
of bisimulation in this way turns out to be rather complex especially in the
presence of probabilistic choices (see [5]). In IGSMP , instead, names of clocks
are dynamically generated by the operational semantics with a xed rule. In
this way equivalent systems get the same names for clocks and there is no need
to associate names of clocks for establishing equivalence. We can, therefore,
rely on standard (probabilistic) bisimulation and we have the opportunity to
reuse existing results and tools.
6.2 Future research
As far as future work is concerned we are trying to extend our approach in
two main directions.
The capability of IGSMP to express general distributions should allow us to
extend the notion of observational congruence as follows. The idea is that
we could be \weak" also on delays. A delay could be seen as a \timed "
and we could equate a sequence of timed  with a single timed  provided
that distribution of durations are in the correct relationship. For example a
sequence (or a more complex pattern) of exponential  could be equated by a
phase-type distributed  . The solution of this problem seems quite involved.
Moreover we are investigating the possibility of introducing in IGSMP an
operator for delay interruption. This requires the introduction of a special
event in semantic models representing \delay interruption" instead of \delay
termination". An interruption operator would greatly enhance the expressive
power of IGSMP , since a preemption mechanism is needed to model many
real systems.

Acknowledgements

We thank the anonymous referees for their helpful comments. This research
has been partially funded by MURST progetto TOSCA.



--R




























--TR
Communicating sequential processes
Petri net models for algebraic theories of concurrency
Communication and concurrency
A complete axiomatisation for observational congruence of finite-state behaviours
Bisimulation through probabilistic testing
Transition system specifications with negative premises
Model-checking in dense real-time
On "Axiomatising Finite Concurrent Processes"
A LOTOS extension for the performance analysis of distributed systems
Adding action refinement to a finite process algebra
A compositional approach to performance modelling
A tutorial on EMPA
A Complete Axiomatization for Observational Congruence of Prioritized Finite-State Behaviors
Towards Performance Evaluation with General Distributions in Process Algebras
Axiomatising ST-Bisimulation Equivalence
An algebraic approach to the specification of stochastic systems
An Overview and Synthesis on Timed Process Algebras
Deciding and Axiomatizing ST Bisimulation for a Process Algebra with Recursion and Action Refinement

--CTR
Pedro R. D'Argenio , Joost-Pieter Katoen, A theory of stochastic systems: part I: Stochastic automata, Information and Computation, v.203 n.1, p.1-38, November 25, 2005
Mario Bravetti , Roberto Gorrieri, Deciding and axiomatizing weak ST bisimulation for a process algebra with recursion and action refinement, ACM Transactions on Computational Logic (TOCL), v.3 n.4, p.465-520, October 2002
Pedro R. D'Argenio , Joost-Pieter Katoen, A theory of stochastic systems: part II: process algebra, Information and Computation, v.203 n.1, p.39-74, November 25, 2005
G. Clark , J. Hillston, Product form solution for an insensitive stochastic process algebra structure, Performance Evaluation, v.50 n.2-3, p.129-151, November 2002
Joost-Pieter Katoen , Pedro R. D'Argenio, General distributions in process algebra, Lectures on formal methods and performance analysis: first EEF/Euro summer school on trends in computer science, Springer-Verlag New York, Inc., New York, NY, 2002
stochastic process algebras;probabilistic bisimulation;generalized semi-Markov processes;observational congruence