A Characterization of the Stochastic Process Underlying a Stochastic Petri Net.
Stochastic Petri nets (SPN's) with generally distributed firing times can model a large class of systems, but simulation is the only feasible approach for their solution. We explore a hierarchy of SPN classes where modeling power is reduced in exchange for an increasingly efficient solution. Generalized stochastic Petri nets (GSPN's), deterministic and stochastic Petri nets (DSPN's), semi-Markovian stochastic Petri nets (SM-SPN's), timed Petri nets (TPN's), and generalized timed Petri nets (GTPN's) are particular entries in our hierarchy. Additional classes of SPN's for which we show how to compute an analytical solution are obtained by the method of the embedded Markov chain (DSPN's are just one example in this class) and state discretization, which we apply not only to the continuous-time case (PH-type distributions), but also to the discrete case.
Introduction
A BOUT one decade ago, Molloy [1], Natkin [2], and
Symons [3] independently proposed associating exponentially
distributed firing delays to the transitions of a
Petri net. Generalized stochastic Petri nets (GSPNs), introduced
by Ajmone Marsan, Balbo, and Conte in [4], relax
this condition by allowing "immediate" transitions, with a
constant zero firing time. In GSPNs, firings of immediate
transitions have priority over firings of timed transitions.
Each immediate transition has associated a weight which
determines the firing probability in case of conflicting immediate
transitions. Stochastic activity networks (SANs)
[5] and stochastic reward nets (SRNs) [6] are two other
classes of Petri nets where transition firing is either exponentially
distributed or constant zero. GSPNs, SANs, and
SRNs can be automatically transformed into continuous-time
Markov chains (CTMCs) or Markov reward processes.
The need for non-exponentially distributed transition
firing times in SPNs has been observed by several au-
thors. Bechta, Geist, Nicola, and Trivedi defined extended
stochastic Petri nets (ESPNs) [7], where the firing delay
of timed transitions may have arbitrary distribution. The
G. Ciardo is with the Department of Computer Science, College of
William and Mary, P.O. Box 8795, Williamsburg, VA 23187, USA.
E-mail: ciardo@cs.wm.edu. His work was supported in part by the
German Academic Exchange Office (DAAD), while he was a Visiting
Professor at the Technische Universit?t Berlin, and by NASA under
grant NAG-1-1132.
R. German is with the Institut f?r Technische Informatik, Technische
Universit?t Berlin, 10587 Berlin, Germany. E-mail: rge@cs.tu-
berlin.de. His work was supported by Siemens Corporate Research &
Development.
C. Lindemann is with Gesellschaft fur Mathematik und Daten-
verarbeitung, Forschungsstelle fur Innovative Rechnersysteme und
Germany. E-mail:
lind@first.gmd.de. His work was supported by the Federal Ministry
for Research and Development of Germany (BMFT) under grant ITR
9003.
numerical solution for ESPNs is applicable when the underlying
stochastic behavior is a semi-Markov process. Ciardo
proposed several extensions to ESPNs and called this modeling
formalism semi-Markov SPNs (SM-SPNs) [8]. Deterministic
and stochastic Petri nets (DSPNs), introduced by
Ajmone Marsan and Chiola [9] as an extension to GSPNs,
include exponentially distributed and constant timing. If
at most one deterministic transition is enabled in a mark-
ing, the steady-state solution can be computed using an
embedded Markov chain. Timed Petri nets (see [10] for a
recent survey paper) and generalized timed Petri nets [11]
employ a discrete time-scale for their underlying Markov
process. Timed transition in TPNs and GTPNs fire in
three phases and the next transition to fire is preselected
according to a probability distribution.
Recently, the class of extended DSPNs has been introduced
[12]. In extended DSPNs, transitions with arbitrary
distributed firing times are allowed under the restriction
that at most one transition with non-exponentially distributed
firing time is enabled in each marking. General
formulas for the steady-state solution of extended DSPNs
were derived using the method of supplementary variables.
In case the non-exponential distributions are piecewise
specified by polynomials, an efficient numerical solution is
possible. Furthermore, Choi, Kulkarni, and Trivedi introduced
the class of Markov regenerative SPNs (MR-SPN)
in [13], [14] which is equivalent to the class of extended
DSPNs. The authors observed that the stochastic process
underlying a MR-SPN is a Markov regenerative process and
derived general formulas for the transient and steady-state
solution. The transient solution method employs inversion
of matrices containing expressions of Laplace-Stieltjes
transforms and the inversion of Laplace transforms.
More general classes of SPNs have been considered by
Haas and Shedler. They introduced regenerative SPNs and
showed how this class of SPN can be analyzed by means of
regenerative simulation [15]. They showed that, for each
generalized semi-Markov process (GSMP) [16], there exists
an equivalent SPN with generally distributed firing times
[17] and proposed to analyze them by discrete-event simulation

In this paper, we explore various subclasses of SPNs,
obtained by imposing restrictions on the combinations of
firing distributions types allowed or on the effect of a transition
firing on the other enabled transitions. This leads to
a hierarchy of SPN classes where modeling power is reduced
in exchange for an increasingly efficient solution. GSPNs,
DSPNs, SM-SPNs, TPNs, and GTPNs are particular entries
in our hierarchy. Furthermore, we show that state
discretization can be applied to both the continuous-time
CIARDO ET AL., A CHARACTERIZATION OF THE STOCHASTIC PROCESS UNDERLYING A STOCHASTIC PETRI NET 507
and the discrete-time case. The class of Discrete-time SPNs
introduced by Molloy [18] is then extended by allowing arbitrary
discrete firing time distributions rather than only
the geometric distribution.
We introduce the semi-regenerative SPNs (SR-SPNs) for
which we show how to compute the steady state solution
by embedding a Markov chain at appropriately defined re-generation
points. The evolution of a SR-SPN between
regeneration points is not restricted to be a CTMC, as for
MR-SPNs and extended DSPNs. Thus, we relax the restriction
that in any marking at most one timed transition
with non-exponentially distributed firing delay is enabled.
In Section IV, we present a SR-SPNs of a transmission
line, where two deterministic transitions are concurrently
enabled. In particular, we consider SR-SPNs where all
transition firing distributions can be piecewise defined by
polynomials multiplied by exponential expressions. This
class of probability distribution is referred to as expolyno-
mial distributions and includes the exponential as well as
the constant distribution as special cases.
The paper is organized as follows. Section II defines
SPNs and describes their behavior. A hierarchical classification
of SPNs according to the underlying stochastic process
is presented in Section III and the feasibility of their
numerical solution is discussed. To illustrate the numerical
solution method of SR-SPNs, a SR-SPN of a simple transmission
line is analyzed in Section IV. Finally, concluding
remarks are given.
II. Stochastic Petri nets
A Petri net is a directed bipartite graph in which the first
set of vertices corresponds to places (drawn as circles) and
the other set of vertices corresponds to transitions (drawn
as bars). Places contain tokens which are drawn as dots.
The set of arcs is divided into input, output and inhibitor
arcs (drawn with an arrowhead on their destination, inhibitor
arcs have a small circle), with each arc is associated
a multiplicity. A marking of a Petri net is given by
a vector which contains as entries the number of tokens in
each place. A transition is said to be enabled in a marking
if all of its input places contain at least as many tokens
as the multiplicity of the corresponding input arc and all
of its inhibitor places contain fewer tokens than the multiplicity
of the corresponding inhibitor arc. A transition
fires by removing tokens from the input places and adding
tokens to the output places according to the arc multiplic-
ities. The reachability set is defined to be the set of all
marking reachable by firings of transitions from the initial
marking.
Throughout this paper, we adopt the common formalism
introduced for Petri nets in which transition firings is
augmented with time [6]. We consider stochastic Petri nets
(SPN) where the firing of a transition is an atomic operation
and two types of transitions exist: immediate tran-
sitions, which fire without delay, and timed transitions,
which fire after a random firing delay. The firing of immediate
transitions has priority over the firing of timed
transitions. Each immediate transition has associated a
weight which determines its firing probability in case this
transition is conflicting with some other immediate transi-
tion. The firing delay of each timed transition is specified
by a probability distribution function. As a consequence,
the reachability set of a SPN can be divided into vanishing
and tangible markings depending on whether an immediate
transition is enabled or not. The tangible markings of
a SPN correspond to the states of an underlying stochastic
process, the marking process. Firing weights of immediate
transitions, average firing delays of timed transitions, and
arc multiplicities may be marking-dependent. Each quantity
is evaluated in the marking before determining which
transitions are enabled and what effect they have when
they fire.
A timed transition is denoted by t, the set of all timed
transitions by T . A tangible marking is denoted by -, the
tangible reachability set by S. E(-) is the set of transitions
enabled in marking - and S E(-)g is the
set of markings where t 2 T is enabled. F t (-; \Delta) is the
probability distribution function for the firing time of t in
-. If this distribution is not marking dependent, we write
Particularly important for continuous-time SPNs is the
case where the firing time distributions may depend on the
marking only through a "scaling factor" [19]. Define the
average firing time of transition t in marking - as:
Then, we require that
F t (\Delta) is the "normalized firing time distribution" of
t, which has average one and is not a marking-dependent
quantity.
To specify the influence of the firing of a transition on
the firing process of other transitions enabled in the current
marking, execution policies have been introduced in
[19]. We allow different execution policies for timed transitions
in a SPN which may also depend on the marking
[20]. Define e t;s (-) 2 fR; Cg to be the execution policy to
be used for transition s when transition t fires in marking -.
If e t;s new random
delay from the associated distribution); if e t;s
it "Continues".
A. Stochastic behavior
The tangible marking - of the SPN as a function of the
time ' is described by a continuous-time stochastic process,
the marking process: f-f'g; ' - 0g or by a discrete-time bi-variate
stochastic process [6]: f('
' [n] is the instant of time when a timed transition fires and
- [n] is marking reached after this firing. ' [0] is zero and - [0]
is the initial marking.
Consider now the remaining firing time (RFT) of each
timed transition after a change of the marking. The RFT
508 IEEE TRANSACTIONS ON SOFTWARE ENGINEERING, VOL. 20, NO. 7, JULY 1994
of transition t enabled in marking - [n] , - [n]
t , specifies the
time to be spent in markings enabling t before transition
t can fire. The transition t with the minimum RFT enabled
in - [n] fires at time '
t . If the firing
time distributions of two or more transitions enabled in
a marking have jumps at the same instants of time, the
probability of them having the same RFT is positive. We
do not consider this case, although weights can be used to
define a probability mass function over these transitions.
At time ' [0] , the RFT of each timed transition enabled
in the initial marking is given by a random sample,
\Delta)), from the firing time distribution associated
with this transition (all other RFTs are undefined).
If transition t 2 E(- [n] ) has the minimum RFT, at time
' [n] , the RFT - [n+1]
s of any other transition s 2 E(- [n+1] )
at time '
is:
(- [n]
if e t;s (- [n]
Using the terminology of [19], this behavior corresponds to
a "race policy", since the minimum RFT determines the
next transition to fire. After the firing of a timed transi-
tion, the next tangible marking is reached either directly or
after the firing of immediate transitions. The probability of
branching to marking - after the firing of timed transition
t in marking - is
- .
Furthermore, the definition of e allows to choose between
"age memory", "enabling memory", and "resampling" [19]
in a marking-dependent way: after the firing of transition
t, a transition s might either restart, e
firing time.
The following firing time distributions are important in
practical applications:
oe
c , where oe is the length of
the unit step. The constant distribution is a special
case: Const(c) is equivalent to Geom(1; c).
ffl discrete: X - Discr , the distribution function of X
is obtained as a weighted sum of a (finite or countably
infinite) number of constant distributions. The geometric
distribution is a special case. It is possible to
approximate any distribution arbitrarily well by using
a sufficiently large number of elements in the weighted
sum.
This distribution approaches Const(0) as -
increases.
b. This distribution approaches Const(b) as a
approaches b.
Poly , the distribution function of
X is piecewise defined by polynomials in ' (expressions
of the form
IR) and has finite support
The finite discrete and uniform distributions
are special cases. It is possible to approximate
any distribution arbitrarily well by using either a sufficiently
large number of polynomials of small degree
(e.g., constants, as for the discrete distributions) or by
using a single polynomial of sufficiently large degree.
Expoly , the distribution function
of X is piecewise defined by expolynomials in '
(expressions of the form
+1)). The polynomial and exponential
distributions are special cases.
III. SPNs with efficient solution
In this section, we describe several types of behavior
which might render the solution analytically tractable.
This leads to a hierarchy of SPN classes where modeling
power is reduced in exchange for an increasingly efficient
solution. The classes are defined by the underlying stochastic
process.
A. Markov SPNs
The main obstacle to an analytical solution is the presence
of the RFT in the state description. If the firing time
distribution of t is memoryless, the RFT of t in - has the
same distribution as the entire firing time, F t (-; \Delta), hence,
there is no need to include it in the state description. Ac-
cordingly, two classes of SPNs were defined: we call them
"CTMC-SPNs", where all distributions are exponential [1],
[2], and "DTMC-SPNs", where all distributions are geometric
[18], since the marking process f- 0g is a
continuous-time Markov chain (CTMC) or a discrete-time
Markov chain (DTMC), respectively.
As the geometric distribution is memoryless only at discrete
time instants multiple of the "time step" oe, exponential
and geometric distributions cannot be freely mixed. A
special case of memoryless distribution is the constant zero,
the distribution of the immediate transitions.
GSPNs [4] are a special case of CTMC-SPNs where the
mass at zero is either zero or one. By using state-expansion,
any phase-type distribution with any mass at zero still results
in an underlying CTMC [19].
The "discrete-time SPNs" defined in [18] allow only geometric
distributions with the same step oe, possibly with
parameter one, that is, the constant oe, since Const(oe) is
equivalent to Geom(1; oe). A discretization analogous to
the one used to expand a phase-type distribution can be
applied to the discrete-time case [8]. First, a geometric distribution
with unit step ioe can be discretized as shown in

Figure

1, where t 1 has step 3 and t 2 has step 1. Weights are
needed to decide whether transition t 1 or t 2 will fire, given
that both attempt to fire, an event which has probability pq
when the underlying DTMC is in state (100c). This allows
more generality than in [18], since the timing of a transition
(i.e., F t 1
its ability to fire when competing
with other transitions (i.e., w t 1
are described
by different quantities. Then, Const(ioe) is equivalent to
hence TPNs are also reducible to a DTMC
CIARDO ET AL., A CHARACTERIZATION OF THE STOCHASTIC PROCESS UNDERLYING A STOCHASTIC PETRI NET 509
100a
100b
Fig. 1. Discretizing two Geom distributions.
with unit step oe, if all constant firing times are a multiple
of oe. The process described by a TPN is probabilistic even
if its firing times are not random variables since, whenever
two transitions have the minimum RFT, the conflict must
be resolved probabilistically using the weight information.
Finally, since any discrete distribution can be obtained as
a weighted combination of constants, any SPN whose firing
distributions have as support a subset of fioe
be reduced to a DTMC with unit step oe.
For both CTMC-SPNs and DTMC-SPNs, steady-state
and transient analysis can be performed using standard
numerical techniques [6]. Assume that the state space of
the process is S and the initial probability distribution is
-(0). The steady-state probability vector - of a CTMC
described by the infinitesimal generator Q, or of a DTMC
described by the one-step transition probability matrix P,
is the solution of
subject to
assuming that S contains only one recurrent class of states
(if this is not the case, S can be partitioned into a transient
class and two or more recurrent classes, which can be
solved independently). Sparsity-preserving iterative methods
such as Gauss-Seidel or Successive Over-Relaxation can
be effectively used for the solution. For transient analysis
of the continuous case, the transient probability vector at
time ' is the solution of
d'
and can be computed using Jensen's method, also called
Uniformization or Randomization [21]. For the discrete
case, the Power method can be used:
starting from -(0)
(the iterations halt when ioe - '). Ergodicity is not required
for transient analysis.
B. Semi-Markov SPNs
If the firing of a transition t in marking - [n] causes transition
s to restart its firing in - [n+1] , e t;s (- [n] the RFT
of s must be resampled in - [n+1] . If all transition pairs
behave this way, the marking process is a semi-Markov
process (SMP), that is, it enjoys absence of memory immediately
after every state change [19], [7]. If s has an
exponential distribution, the choice between Restart and
Continue is irrelevant and we assume e t;s = R in this case.
The time instants ' [n] are called regeneration points
[22].
For transient and steady-state analysis of a SMP, the evolution
of the process during the regeneration points must be
studied. Equation (1) describes the kernel
of a SMP. Since the future of the marking process after a
regeneration point becomes a probabilistic replica of the
future of the process after time zero, if started in the same
state, the kernel is also given by Equation (2).
Equation (3) describes the vector holding
time distributions in the states of the SMP, which can be
reduced to Equation (4).
The matrix \Pi(') of transient solutions of a SMP is given
by the following system of integral equations:
where diag(h(')) represents a square matrix having the
elements of h(') on the main diagonal and zeros elsewhere.
For steady-state analysis, an embedded Markov chain
(EMC) can be defined. The one-step transition probability
matrix P of the EMC is computed by studying the
evolution of the SMP between regeneration points. Having
obtained the matrix P, the steady-state solution of the
EMC can be derived by solving the linear system of global
balance equations. Subsequently, the vector c of conversion
factors is computed. The entries of c represent the
expected holding times in the states of the SMP between
two regeneration points. The solution vector of the EMC
is multiplied by the vector c and normalized to obtain the
steady-state probability vector of the SMP.
The one-step transition probability matrix P of the EMC
is derived from the kernel: and the vector
c of conversion factors is given by
The steady-state solution fl of the EMC can be obtained
by solving:
subject to
and the steady-state solution of the SMP is given by:
510 IEEE TRANSACTIONS ON SOFTWARE ENGINEERING, VOL. 20, NO. 7, JULY 1994
For a SM-SPN, the entries of kernel and the vector of
holding times are given by (for simplicity, we assume that
simultaneous firings have zero probability):
Z 'Y
Y
Equation (5) can be solved directly or by employing
Laplace-Stieltjes transforms as recently proposed in [13],
[14]. This solution method may cause numerical difficulties
and its computational cost is significant for large models.
However, when all firing time distributions are expolyno-
mial distributions, the entries of P and c can be obtained
by symbolic integration, and the steady-state solution can
then be obtained by solving (6) and (7).
C. regenerative SPNs
If there is a marking - and two transitions t; s 2 E(-)
such that e t;s before s, and s does not
have an exponential distribution, the marking process is
not semi-Markov. However, under certain conditions, it
might be possible to find regeneration points, at which the
process enjoys absence of memory. This process is called
a semi regenerative process (SRP) in [22], so we call semi
regenerative SPN (SR-SPN) a SPN whose marking process
is a SRP. For the transient and steady-state analysis, the
evolution of the process between the regeneration points
must be studied. Since this can be a GSMP with arbitrarily
distributed holding time in each state, the marking process
of a SR-SPN is more general than in a MR-SPNs [13] or
an extended DSPN [12]. The set of regeneration points of
a SR-SPN can be expressed as
where each regeneration point ' [nk ] must satisfy the condition
that, when the SPN enters marking - [nk ] at time
firing transition t, any transition enabled in - [nk
restarts its firing process.
In the following, we concentrate on steady-state analysis.
As for SMP, an EMC is defined at regeneration points of
a SRP. For the one-step transition probability matrix P of
the EMC, the evolution of the SRP between the regeneration
points must be studied. The steady-state solution of
the EMC can be computed as in the case of SMPs, but the
conversion factors constitute a matrix rather than a vector.
The steady-state probability vector of the SRP is derived
by multiplying the steady-state probability vector of the
EMC by the matrix of conversion factors and normalizing
according to Equations (6) and (8).
The one-step transition probability matrix of
the EMC and the matrix of conversion factors
are defined by:
during [' [nk
=Eftime in j during [0; ' [n 1
The steady-state solution of the EMC can still be obtained
by solving the linear system of equations (6). The
solution of the EMC, fl, is converted to that of the SRP, -,
by multiplying by the conversion factors and normalizing:
For a constructive definition of SR-SPNs, the sets SE ,
TR , are introduced [23]. SE is the set of all markings
in which only exponential transitions are enabled. TG
is the set of all general (non-exponential) transitions of the
SPN. TR ' TG is a set which contains regenerative transi-
tions. A transition t 2 TG is called regenerative, if all other
transitions of the SPN restart when t becomes enabled,
fires, or becomes disabled. Note that TR is not required to
contain all general transitions.
SPN is a SR-SPN, if a set TR
of regenerative transitions can be found, such that SE and
TR constitute a partition of S.
The definition of the regeneration points of a SR-SPN
depends on whether a regenerative transition is enabled or
not. For states - [nk the next regeneration point is
chosen to be the instant of time after the transition with
the minimum firing delay has fired: ' [nk+1 . For
states TR , the next regeneration point is
chosen to be the instant of time after t has fired or has
become disabled.
The possible evolution of the SR-SPN during the enabling
period of a regenerative transition t is described
by the subordinated (stochastic) process of t 2 TR . The
matrix of transient state probabilities for this process is
state i at time 0g:
Based on \Pi('), P and C can be defined row-wise. For
all regenerative transitions t 2 TR the rows corresponding
to states i 2 S t are defined by:
ae / t
where u i is the i-th row unity vector,
\Theta
is the
matrix of branching probabilities after a firing of t, and
\Theta
and
\Theta
are the transient probabilities
and the expected holding times of the states of the subordinate

process:\Omega
CIARDO ET AL., A CHARACTERIZATION OF THE STOCHASTIC PROCESS UNDERLYING A STOCHASTIC PETRI NET 511
The entries of P and C for rows corresponding to states
are given by
is the rate leading from state i to state j and - i
is the sum of all outgoing rates for state i.
If a regenerative transition t is never enabled together
with other transitions, the steady-state solution of a SR-
SPN is insensitive to the distribution of t, since Equations
(11) and (12) reduce to:
An efficient numerical solution of Equations (11) and
(12) is the critical step for the practical application of SR-
SPNs. The next section presents a SR-SPN whose subordinated
process is a SMP.
The numerical solution of a SR-SPNs with large state
space can be performed efficiently if the subordinated processes
are CTMCs. In this case, at most one regenerative
transition may be enabled in each marking. SR-SPNs
with this restriction are equivalent to the class of extended
DSPN defined in [12] and Markov regenerative SPNs defined
in [13]. In case of a subordinated CTMC, the matrix
of transient state probabilities for the subordinated process
is given by the matrix exponential of the generator matrix
for the subordinated CTMC of transition t:
In

Appendix

A we show how to generalize Jensen's method
for an efficient calculation of the rows of Equations (11)
and (12) in case of expolynomial regenerative transitions.
This technique has been implemented in TimeNET (Timed
Net Evaluation Tool), which can solve SR-SPNs, provided
that at most one expolynomial transition is enabled in
each marking, plus any number of exponential transitions
(TimeNET offers simulation capabilities as well, for SPNs
not satisfying this requirement).
The analysis can be generalized to the case where the firing
time distribution of a regenerative transition depends
on the marking through a scaling factor. This can be done
by scaling the generator matrix by the corresponding scaling
factors:
\Theta -
In this case the
matrices\Omega t and \Psi t are given by:
Z 1e
Z 1e
Equations (16) and (17) generalize the results presented
in [24] (see

Appendix

B).
SPNs
Underlying: general
SRP-SPNs
Subordinated: general
SRP-SPNs
SRP-SPNs
SMP-SPNs
Underlying: SMP
CTMC-SPNs
Underlying: CTMC
DTMC-SPNs
Underlying: DTMC
Fig. 2. SPN hierarchy.
D. Generalized semi-Markov SPNs
If there is a marking i and two transitions t; s 2 E(i)
such that e and s do not have an exponentially
distributed firing delay, the underlying process
is too difficult to study as a SRP, or it might even not be
a SRP. The underlying stochastic process is a GSMP. It is
also possible to derive the state equations for the transient
or steady-state case by means of supplementary variables
[12]. The resulting equations constitute a system of partial
differential equations which can be analyzed numerically
by replacing the differential quotients by finite difference
quotients. In practice, however, simulation is the method
of choice for the study of large SPNs with generally distributed
firing times [15], [17].

Figure

2 summarizes the classes of SPNs and relates
them to the underlying stochastic processes.
Practical limitations
We conclude this section with an informal discussion of
the models that can be solved in a reasonable amount of
time on a modern workstation. For analytical solutions,
the main obstacle is often the memory required to store the
reachability graph, or even just its tangible portion. As a
rule of thumb, 10 5 to 10 6 markings and 10 6 to 10 7 marking-
to-marking transitions can be considered the limit. A large
amount of virtual memory is usually required, but it is
not in itself sufficient, since the algorithms to build the
reachability graph exhibit little locality, causing an excessive
number of page faults if not enough main memory is
available.
In this respect, the memory requirements for a Markovian
SPN (CTMC-SPN or DTMC-SPN) are the most
512 IEEE TRANSACTIONS ON SOFTWARE ENGINEERING, VOL. 20, NO. 7, JULY 1994
straightforward to understand. For SMP-SPNs, the requirements
are similar, since the embedded process is a
DTMC. The study of a SR-SPN requires instead to consider
multiple stochastic processes. If the regenerative
transitions have expolynomial firing distributions and the
subordinated processes are CTMCs, it is appropriate to
attempt an analytical solution. For the subordinated pro-
cesses, the memory locality can be higher and the maximum
main memory requirements smaller, since the solution
of each process is performed in isolation and each of them
is usually smaller than the entire chain for a similar Markovian
SPN. However, the transition probability matrix describing
the embedded process, while possibly being of a
smaller dimension than in the Markovian case, often contains
many additional entries, corresponding to marking-
to-marking paths, rather than single transitions. Hence, for
SR-SPNs, the overall memory requirements might be better
or worse than for a similar Markovian model, depending
on the particular model.
Another issue to consider is the execution time required
for a steady-state or transient solution. For a Markovian
SPN, assuming enough memory is available, the steady-state
solution becomes a problem only if the convergence
of the linear system is excessively slow. For transient anal-
ysis, a large number of iterations is required if the system
is stiff, that is, if there is a mixture of slow and fast events
(entries differing by many orders of magnitude) and the
time at which the solution is required is sufficiently large.
For the steady-state study of a SR-SPN, analogous considerations
apply to each individual process, since a transient
analysis of the subordinated processes and a steady-state
analysis of the embedded process is required. Hence, the increased
generality of the underlying stochastic process does
not necessarily have a negative effect on the solvability.
In all cases where a numerical solution is impossible or
impractical, such as the analysis of Markovian SPNs with
excessively large reachability sets, transient analysis of a
non-trivial SMP-SPN or SR-SPN, and analysis of a general
SPN or a SR-SPN with non-Markovian subordinated
processes, simulation is an effective approach.
IV. An example
In this section, a SPN model of a simple transmission line
is considered, to illustrate the steady-state analysis of a SR-
SPN. It is assumed that, after the generation of a message,
transmission begins and a timeout clock is started. Conflict
for the medium can delay the start of transmission. If the
timeout elapses before the transmission of the message is
completed, the transmission will be repeated.

Figure

3 shows a SPN model of the system. The generation
of a message is modeled by transition t 0 , which has an
arbitrary firing time distribution with average firing time
. The timeout and the transmission of the message
are represented by transitions t 1 and t 3 with constant
firing times of - 1 and - 3 , respectively. The delay to acquire
the medium is modeled by transition t 2 , which has
an exponentially distributed firing time with rate -. The
multiplicity of some input arcs is marking-dependent to en-
Fig. 3. SR-SPN of a transmission line.
0:1000 1:0110
2:0101
Fig. 4. The reachability graph for the model.
sure that places are empty after the firing of
t 1 or t 3 . If the timeout is not larger than the transmission
time, no successful transmission can ever take place, hence
we assume
In this SPN, t 1 and t 3 have constant firing times, are concurrently
enabled, and start their firing process at different
instants of time. Nevertheless, the analysis is possible using
firings of the transitions t 0 and t 1 as regeneration points:
g. The reachability set of the SR-SPN consists
of three markings and is shown in Figure 4:
The sets S t 0
constitute a partition
of the reachability set S. Transition t 0 is exclusively
enabled, hence the steady-state solution of the SPN is insensitive
to the distribution of t 0 , it only depends on the
average firing time - 0 . The process subordinated to transition
t 1 is a SMP and is shown in Figure 5. Since t 1
can become enabled only upon entering marking 1, the
first and last row of \Pi t 1
, and \Psi t 1
are not needed.
neither t 0 nor t 1 can become enabled upon entering
marking 2, the last row of C is not needed either. In ad-
dition, after t 1 fires, the SPN cannot be in marking 2, so
the last column and row of P are not needed either. In
other words, P only needs to describe the probability of
transitions between markings 0 and 1. Finally, entry / t 1
does not need to be computed because transition t 1 is not
enabled in marking 0. For simplicity, we denote unneeded
entries with the symbol "\Gamma".
The matrix \Pi t 1
(') of the transient state probabilities for
the SMP subordinated to t 1 can be obtained symbolically:
\Theta

CIARDO ET AL., A CHARACTERIZATION OF THE STOCHASTIC PROCESS UNDERLYING A STOCHASTIC PETRI NET 513
0:1000 1:0110 2:0101
Fig. 5. The SMP subordinated to t 1 .
The matrices of state probabilities of the SMP at the instant
of firing of t 1
, and of expected holding times in
in each marking up to the firing of t 1 , \Psi t 1
are:
\Theta
and
\Theta / t 1
(')d'
where u(\Delta) is the unit step function. Employing Equations
and (10) yields the one-step transition probability matrix
P of the EMC and the matrix of conversion factors
C:
All changes of marking caused by firings of transition t 1
lead to marking 0. The steady-state probability vector of
the EMC is computed by solving the linear system of equations
(6). In this particular case, the solution is:
The steady-state marking probability vector - of the SR-
SPN is obtained as the product of the steady-state probability
vector of the EMC by the matrix C of conversion
factors:
and by subsequently normalizing fl 0 according to Equation
(8).
For a numerical example, assume -
\Theta
and
The average cycle time for the token is given by the sum
of the average enabling times for
and its throughput
However, only a portion ! t 1
10 of this throughput corresponds
to successful completions of the transmission, hence the
real transmission throughput is
Finally, when a timeout occurs, the probability that the
transmission has not yet started is
The complementary probability,
corresponds to the undesirable event of having a timeout
while the transmission is underway.
Conclusion
In this paper, we have classified the SPNs into various
classes, according to the nature of their underlying stochastic
process. The most complex class we identified, SR-
SPNs, corresponds to semi-regenerative processes and effectively
extends the class of SPNs for which an analytical
solution is known.
We illustrate the type of behavior that can be modeled by
the SR-SPNs using a simple system transmitting messages
as an example. In it, two deterministic transitions can
become enabled concurrently, but not necessarily at the
same time. A similar model was given as an example of
a DSPN which cannot be solved with previously known
methods [9].


Appendix


I. Extending Jensen's method to expolynomial
distributions
In this appendix we derive an efficient numerical computation
of Equations (11) and (12) for a transition t with an
expolynomial distributed firing time and a subordinated
CTMC [23]. The presented formulas generalize Jensen's
method and the formulas presented in [12] for polynomial
distributions.
514 IEEE TRANSACTIONS ON SOFTWARE ENGINEERING, VOL. 20, NO. 7, JULY 1994
For
The solution of (11) and (12) is a weighted sum of matrices
can be calculated with Jensen's
method: define
A =q
The rows of E ( ') are obtained as
R
where \Phi is calculated by iterative vector-matrix multiplications

is the i-th row unity-vector and fi(k; q') is the k-th Poisson
probability in q' which can be calculated iteratively by:
The truncation points L and R of the summation can be
estimated for a given error tolerance [6].
For the calculation of L (';m;-) , the power series of the
matrix exponential can be substituted:
dy
Applying right truncation leads to:
R
where fl(k) and j(k) are calculated iteratively:
A criterion to bound the truncation error can be de-
rived. The entries of each row of the matrix exponential
sum to one. The truncation error of each entry of L (';m;-)
is bounded by ", if R satisfies
r
where s is the (exact) sum of each row of L (';m;-) . If
s is given by
The computational effort for the calculation of one row
of L (';m;-) depends mainly on the number of vector-matrix
multiplications. If a weighted sum of matrices E (') and
L (';m;-) is required, it is possible to factor out the matrix
powers, thus avoiding repeated vector-matrix multiplica-
tions. The asymptotical complexity for the numerical solution
in case of an expolynomial distribution is therefore of
the same order as in the case of a deterministic firing time.
II. Formulas for marking-dependence through a
scaling factor
In this appendix we derive Equations (16) and (17) presented
for regenerative SPNs with a transition t with a
general distributed firing time depending on the marking
through a scaling factor and with a subordinated CTMC.
Define the normalized state probabilities of the subordinated
CTMC as (' j is the absolute and -
' is the normalized
elapsed firing time of t):
The matrix of normalized state probabilities is given by
the matrix exponential of the scaled generator matrix -
(this can be shown by the underlying system of differential
equations [24]):
ij as the probability, that the subordinated CTMC
is in state j after t fires, given it was in state i initially, and
ij as the expected holding time in state j up to the firing
of t. Integrating by substitution:
Z 1-
Z 1-
Substitution of the entries of the matrix exponential leads
to Equations (16) and (17).



--R

"Performance analysis using stochastic Petri nets"
"Reseaux de Petri stochastiques"
Modeling and Analysis of Communication Protocols Using Numerical Petri Nets
"A class of Generalized Stochastic Petri Nets for the performance evaluation of multiprocessor systems"
"Stochas- tic activity networks: structure, behavior, and application"
"Automated generation and analysis of Markov reward models using Stochastic Reward Nets"
"Extended Stochastic Petri Nets: applications and analysis"
Analysis of large stochastic Petri net models
"On Petri Nets with deterministic and exponentially distributed firing times"
"Timed Petri nets definitions, properties, and applications"
"A Generalized Timed Petri Net model for performance analysis"
"Analysis of Stochastic Petri Nets by the Method of Supplementary Vari- ables"
"Markov regenerative stochastic Petri nets"
"Transient analysis of deterministic and stochastic Petri nets"
"Regenerative stochastic Petri nets"
"Continuity of generalized semi-Markov processes"
"Stochastic Petri net representation of discrete event simulations"
"Discrete Time Stochastic Petri Nets"
"The effect of execution policies on the semantics and analyis of Stochastic Petri Nets"
"Analysis of deterministic and stochastic Petri nets"
"The randomization technique as a modeling tool and solution procedure for transient Markov pro- cesses"
Erhan C- inlar
Analysis of Stochastic Petri Nets with Non- Exponentially Distributed Firing Times
"Modeling discrete event systems with state-dependent deterministic service times"
--TR
A class of generalized stochastic Petri nets for the performance evaluation of multiprocessor systems
nets
Regenerative stochastic Petri nets
A generalized timed petri net model for performance analysis
Stochastic Petri Net Representation of Discrete Event Simulations
The Effect of Execution Policies on the Semantics and Analysis of Stochastic Petri Nets
Analysis of large stochastic petri net models
Analysis of stochastic Petri nets by the method of supplementary variables
Markov regenerative stochastic Petri nets
DSPNexpress
Extended Stochastic Petri Nets
On Petri nets with deterministic and exponentially distributed firing times
Transient Analysis of Deterministic and Stochastic Petri Nets
Stochastic Activity Networks

--CTR
Armin Heindl , Reinhard German, A Fourth-Order Algorithm with Automatic Stepsize Control for the Transient Analysis of DSPNs, IEEE Transactions on Software Engineering, v.25 n.2, p.194-206, March 1999
N. N. Ivanov, Decomposition Analysis of Random Processes in Time Stochastic Petri Networks, Automation and Remote Control, v.62 n.10, p.1731-1742, October 2001
Christian Kelling, A framework for rare event simulation of stochastic Petri nets using RESTART, Proceedings of the 28th conference on Winter simulation, p.317-324, December 08-11, 1996, Coronado, California, United States
Narayanan , Sanda Harabagiu, Question answering based on semantic structures, Proceedings of the 20th international conference on Computational Linguistics, p.693-es, August 23-27, 2004, Geneva, Switzerland
Andrea Bobbio , Antonio Puliafito , Mikls Tekel, A Modeling Framework to Implement Preemption Policies in Non-Markovian SPNs, IEEE Transactions on Software Engineering, v.26 n.1, p.36-54, January 2000
A. Bobbio , A. Horvth , M. Telek, The scale factor: a new degree of freedom in phase-type approximation, Performance Evaluation, v.56 n.1-4, p.121-144, March 2004
Muhammad A. Qureshi , William H. Sanders , Aad P. A. van Moorsel , Reinhard German, Algorithms for the Generation of State-Level Representations of Stochastic Activity Networks with General Reward Structures, IEEE Transactions on Software Engineering, v.22 n.9, p.603-614, September 1996
N. Chaki , S. Bhattacharya, Performance analysis of multistage interconnection networks with a new high-level net model, Journal of Systems Architecture: the EUROMICRO Journal, v.52 n.1, p.56-70, January 2006
I. Mura , A. Bondavalli, Markov Regenerative Stochastic Petri Nets to Model and Evaluate Phased Mission Systems Dependability, IEEE Transactions on Computers, v.50 n.12, p.1337-1351, December 2001
G. Ciardo , R. L. Jones, III , A. S. Miner , R. I. Siminiceanu, Logic and stochastic modeling with SMART, Performance Evaluation, v.63 n.6, p.578-608, June 2006
PH-type distributions;embedded Markov chain;stochastic Petri nets;stochastic Petri net;semiMarkovian stochastic Petri nets;stochastic process;distributed firing times;simulation;deterministic Petri nets;SPN classes;modeling power;stochastic processes;markov processes;timed Petri nets;state discretization;continuous-time case;generalized timed Petri nets;petri nets;generalized stochastic Petri nets