M. Ajmone Marsan, G. Balbo, G. Conte, S. Donatelli and G. Franceschinis
Modelling with Generalized Stochastic Petri Nets
Wiley Series in Parallel Computing
John Wiley and Sons
ISBN: 0 471 93059 8
THIS BOOK IS OUT OF PRINT.
IT IS NOW POSSIBLE
TO DOWNLOAD A REVISED ELECTRONIC
VERSION (.pdf) OF THE BOOK.
Orders should be sent to:
John Wiley & Sons Ltd Distribution Centre
Southern Cross Trading Estate
1 Oldlands Way
Bognor Regis
West Sussex
PO22 9SA
England
Tel: +44 1243 779777
Fax: +44 1243 820250
Email: market@wiley.co.uk



MODELLING WITH GENERALIZED STOCHASTIC PETRI NETS
M. Ajmone Marsan, Politecnico di Torino, Italy,
G. Balbo, Universita' di Torino, Italy,
G. Conte, Universita' di Parma, Italy,
S. Donatelli, Universita' di Torino, Italy
and G. Franceschinis, Universita' di Torino, Italy
This book presents a unified theory of Generalized Stochastic Petri Nets
(GSPNs) together with a set of illustrative examples from different application
fields.
The continuing success of GSPNs and the increasing interest in using
them as a modelling paradigm for the quantitative analysis of distributed
systems suggested the preparation of this volume with the intent of
providing newcomers to the field with a useful tool for their first
approach.
Readers will find a clear and informal explanation of the concepts
followed by formal definitions when necessary or helpful. The largest
section of the book however is devoted to showing how this methodology
can be applied in a range of domains.
Contents:
 Preface
 1 INTRODUCTION
 1.1 Shared Resources
 1.2 Fork and Join
 1.3 Kanban Process
 1.4 Token Ring LAN
 2 PETRI NETS AND THEIR PROPERTIES
 2.1 Petri Net Models
 2.2 Models, Systems, and Nets
 2.3 System Dynamics
 2.3.1 Enabling and firing rules
 2.3.2 Reachability set and reachability graph
 2.3.3 Modelling issues
 Modelling logical conditions
 2.3.4 Typical situations in the PN system evolution
 Conflicts
 Concurrency
 Confusion
 Causal connection
 Mutual exclusion
 2.4 Properties of Petri Nets
 Reachability and reversibility
 Absence of deadlock
 Liveness
 Boundedness
 Mutual exclusion
 2.5 Structural Analysis Techniques
 2.5.1 Linear algebraic techniques
 Psemiflows and Pinvariant relations
 Tsemiflows and Tinvariant relations
 2.5.2 Graphbased structural techniques
 Deadlocks and traps
 Structural relations between transitions
 2.6 State Space Analysis Techniques
 Reachability
 Reversibility
 Absence of deadlock
 Liveness
 Boundedness
 Mutual exclusion
 Effective conflict and confusion
 3 TIME IN PETRI NETS
 3.1 The Motivations for Timing
 3.2 Timed Transitions
 3.2.1 Immediate transitions
 3.2.2 Two examples
 3.3 Parallelism and Conflict
 3.4 Memory
 3.4.1 An example with the enabling memory policy
 3.4.2 An example with the age memory policy
 3.5 Multiple Enabling
 3.6 A Timed PN Model Example
 3.7 Performance Measures
 4 PETRI NETS WITH PRIORITY
 4.1 Definition and Dynamics
 Enabling and firing
 An example
 4.2 Conflicts, Confusion and Priority
 Conflict
 Confusion and priority
 4.3 Properties of Priority PN Models
 Reachability
 Boundedness
 Liveness and liveness degree
 Reversibility and home states
 4.4 Structural Analysis Techniques
 4.4.1 Linear algebraic techniques
 P and Tsemiflows
 4.4.2 Graph based analysis
 Structural conflict
 4.5 Reachability Analysis Techniques
 Reachability graph of PN models with priority
 Reduced reachability graphs
 5 GSPN BASICS
 5.1 Exponential Distributions for Transition Delays
 5.2 Mixing Exponentially Distributed and Null Delays
 5.3 Some Extensions
 5.4 The Definition of a GSPN Model
 5.5 An Example of a GSPN Model
 5.6 Some Fine Points
 6 ANALYSIS OF GSPN MODELS
 6.1 The Stochastic Process Associated with a SPN
 6.1.1 SPN performance indices
 6.1.2 An example SPN system
 6.2 The Stochastic Process Associated with a GSPN
 6.2.1 Marking dependency
 6.2.2 An example GSPN system
 6.3 Numerical Solution of GSPN Systems
 6.3.1 Evaluation of the steadystate probability distribution for the example GSPN system
 6.3.2 Performance analysis of the example GSPN
 6.4 Reducing GSPNs to SPNs
 6.5 Simulation of GSPN Systems
 6.5.1 Simulation of the example GSPN system
 7 GSPN REPRESENTATION OF PHASETYPE DISTRIBUTIONS
 7.1 The Central Server Model Example
 7.1.1 CPU interruptions
 7.1.2 CPU memory policies
 7.2 PhaseType Distributions
 7.2.1 Erlang distributions
 7.2.2 Numerical evaluation
 7.3 General PhaseType Distributions
 8 MODELLING FLEXIBLE MANUFACTURING SYSTEMS
 8.1 Flexible Manufacturing Systems
 8.2 A Kanban System
 8.2.1 Structural analysis of the GSPN model of the Kanban system
 8.2.2 Performance analysis of the Kanban system
 8.3 Push Production Systems
 A system using continuous transportation
 A system with AGV transportation
 8.3.1 Structural analysis of the push production systems
 8.3.2 Performance analysis of the system with AGV transport
 9 COMPACT MODELS OF RANDOM PDLLING SYSTEMS
 9.1 Polling Systems
 9.2 Modelling Random Polling the Easy Way
 9.2.1 The first complete random polling model
 9.3 Beginning to Exploit Symmetries
 9.3.1 Walking before choosing?
 9.3.2 Number of states and limitations of the model
 9.4 Abstracting from the Queue Identifiers
 9.4.1 The abstract GSPN model
 9.4.2 Walking before choosing!
 9.4.3 Number of states and limitations of the model
 9.5 From GSPNs to SPNs
 10 MODELLING AND ANALYSIS OF CONCURRENT PROGRAMS
 10.1 Introduction to the Static Analysis of Concurrent Programs
 10.2 The Automatic Translation from Programs to GSPNs
 10.2.1 Languages of interest
 10.2.2 The translation procedure
 10.3 An Example of Translation
 10.4 Modelling Control Variables to Reduce Nonfaults
 10.5 Stochastic Analysis
 Probability of two communications at the same time
 Joint distribution of p_k and p_n
 Throughput
 Mutual exclusion
 11 MODELS OF CONCURRENT ARCHITECTURES
 11.1 Concurrent Architectures
 11.2 Single Processor Model
 11.3 Single Processor Model with Multitasking
 11.4 Models of Mesh Structures
 11.4.1 Mesh models without multitasking
 11.4.2 Mesh models with multitasking
 Appendix A: STOCHASTIC PROCESS FUNDAMENTALS
 A.1 Basic Definitions
 A.2 Markov Processes
 A.3 DiscreteTime Markov Chains
 A.3.1 Steadystate distribution
 A.3.2 Matrix formulation
 A.3.3 Example
 A.4 ContinuousTime Markov Chains
 A.4.1 Steadystate distribution
 A.4.2 Matrix formulation
 A.4.3 Sojourn and recurrence times
 A.4.4 The embedded Markov chain
 A.4.5 Example
 A.5 Aggregation of States in Markov Chains
 A.5.1 Aggregation in discretetime Markov chains
 A.5.2 Aggregation in continuoustime Markov chains
 A.6 SemiMarkov Processes
 A.7 SemiMarkov Reward Processes
 Appendix B: GLOSSARY
 References
 Index