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
P-semiflows and P-invariant relations
T-semiflows and T-invariant relations
2.5.2 Graph-based 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 T-semiflows
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 steady-state 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 PHASE-TYPE DISTRIBUTIONS
7.1 The Central Server Model Example
7.1.1 CPU interruptions
7.1.2 CPU memory policies
7.2 Phase-Type Distributions
7.2.1 Erlang distributions
7.2.2 Numerical evaluation
7.3 General Phase-Type 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 Discrete-Time Markov Chains
A.3.1 Steady-state distribution
A.3.2 Matrix formulation
A.3.3 Example
A.4 Continuous-Time Markov Chains
A.4.1 Steady-state 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 discrete-time Markov chains
A.5.2 Aggregation in continuous-time Markov chains
A.6 Semi-Markov Processes
A.7 Semi-Markov Reward Processes
Appendix B: GLOSSARY
References
Index