ANALYSIS OF GSPN MODELS - Modelling with Generalised Stochastic Petri Nets - page 140

6.4 Reducing GSPNs to SPNs

As we saw in the previous sections, immediate transitions, that have quite a
beneficial impact on the modelling power of GSPNs, unfortunately make the
overall analysis of GSPNs more complex than that of SPNs. Indeed, while
for the latter the reachability graph is isomorphic to the state transition rate
diagram of the CTMC underlying the SPN, such isomorphism does not exist
for GSPNs, but is obtained only after the elimination of vanishing markings.
An analysis procedure different from that described in the previous sections
consists in the elimination of all immediate transitions from a given GSPN
before starting the generation of its reachability set, so as to produce an
SPN whose underlying continuous-time Markov chain is identical to that
corresponding to the GSPN.
This section provides a concise and informal overview of the rules for the
reduction of a GSPN model to an equivalent SPN by eliminating all immedi-
ate transitions. A complete and formal description of these reduction rules
and of the class of GSPNs for which it is possible to compute an equivalent
SPN, can be found in [15, 24] .
The basic idea behind the elimination of immediate transitions is quite sim-
ple and can be easily explained in its simplest form by means of an example.
The model depicted in Fig. 6.12( a) is a free-choice GSPN subnet whose SPN
counterpart is shown in Fig. 6.12( b). The two systems are equivalent as far
as tangible states are concerned.
To understand how we can transform the GSPN into its corresponding SPN,
consider what happens in the GSPN when T a fires: the three immediate
transitions t 1 ,t 2 , and t 3 become enabled, due to the arrival of one token
in place p b ; they are the only transitions that are enabled in the subnet,
and the choice about which one to fire is made according to their associated
weights. The basic behaviour of the subnet in Fig. 6.12( a) is therefore that
of “moving” tokens from place p a to one of the three places p 1 , p 2 , and p 3 .
The net in Fig. 6.12( b) is clearly equivalent to that of Fig. 6.12( a) from the
point of view of the flow of tokens (token flow equivalence was defined in
[ 10] ).
When time is involved, token flow equivalence is not enough to ensure the
possibility of freely interchanging the two types of models. In particular,
the equivalence notion we are interested in must preserve the underlying
stochastic behaviour of the net. We must therefore take into account not
only the possible final states of the subnet, but also the rates at which the
model transits from state to state.
The operations of the GSPN subnet induce a movement of a token from p a
to p k , k = 1, 2, 3, with rate

w a w k

(6.43)

P

j=1,2,3 w j

where w a is the rate of the exponential distribution associated with timed