Skip to main content

1998 | Buch

Lectures on Petri Nets II: Applications

Advances in Petri Nets

herausgegeben von: Wolfgang Reisig, Grzegorz Rozenberg

Verlag: Springer Berlin Heidelberg

Buchreihe : Lecture Notes in Computer Science

insite
SUCHEN

Über dieses Buch

The two-volume set originates from the Advanced Course on Petri Nets held in Dagstuhl, Germany in September 1996; beyond the lectures given there, additional chapters have been commissioned to give a well-balanced presentation of the state of the art in the area.
Together with its companion volume "Lectures on Petri Nets I: Basic Models" this book is the actual reference for the area and addresses professionals, students, lecturers, and researchers who are
- interested in systems design and would like to learn to use Petri nets familiar with subareas of the theory or its applications and wish to view the whole area
- interested in learning about recent results presented within a unified framework
- planning to apply Petri nets in practical situations
- interested in the relationship of Petri nets to other models of concurrent systems.

Inhaltsverzeichnis

Frontmatter
Petri nets, process algebras and concurrent programming languages
Abstract
This paper discusses issues that arise when process algebras and Petri nets are linked; in particular, operators, compositional ity, recursion, refinement and equivalences. It uses the box algebra in order to show how Petri nets can be manipulated algebraically. Also, the paper shows how other process algebras such as CCS, COSY and CSP can be treated in the same way, how Petri net semantics of concurrent programming languages can be given, and how Petri net methods can be applied to the verification of concurrent algorithms.
Eike Best, Raymond Devillers, Maciej Koutny
Petri nets and production systems
Abstract
Modern production systems pose a diversity of problems all along their life cycle which are often treated with particular independent formalisms and techniques. Production systems can be viewed as discrete event, continuous, or hybrid systems. Petri nets are a family of formalisms which can be used for the modelling, analysis, implementation and control of these systems, with the benefit of improving the communication between stages of the life cycle.
The utilisation of Petri nets in several of these stages is illustrated in this tutorial paper through a selected set of examples.
Manuel Silva, Enrique Teruel, Robert Valette, Hervé Pingaud
Computer Supported Cooperative Work and Petri Nets
Abstract
Computer Supported Cooperative Work (CSCW) has brought to the attention of computer professionals the role computer applications may play supporting collaboration, coordination and communication among people cooperating in a common task. In particular, people acting in accordance with a structured workflow, as a procedure or as a project plan, can be supported by a class of systems called workflow management systems, not only to play their role in it, but also to increase their awareness of the situation in which they are acting so that they can make better decisions when needed and overcome breakdowns finding new (exceptional) paths. Workflow management systems, in fact, facilitate the description, modeling, analysis, enactment, and coordination of (the) structured (component of) work processes. These systems assist and mediate communication, interaction, understanding, and synchronization among collaborating people and processes within organizations.
Giorgio De Michelis, Clarence A. Ellis
Petri nets and digital hardware design
Abstract
Petri nets are a powerful language for describing processes in digital hardware, and particularly asynchronous or self-timed circuits. Self-timed circuits are designed to operate without the use of a global clock signal. Applications for such circuits are likely to increase during the next decade, due to problems with on-chip event coordination as VLSI technology approaches a density of one hundred million transistors per chip. Designing such circuits without help of formal tools does not seem to be possible. We present an overview of the methods for specification, verification and synthesis of asynchronous circuits with the aid of Petri nets. We present a number of design examples which are used to illustrate the authors' belief that Petri nets could become widely accepted by digital system designers as a design method.
Alexandre V. Yakovlev, Albert M. Koelmans
An introduction to the practical use of coloured Petri Nets
Abstract
The development of Coloured Petri Nets (CP-nets or CPN) has been driven by the desire to develop a modelling language - at the same time theoretically well-founded and versatile enough to be used in practice for systems of the size and complexity found in typical industrial projects. To achieve this, we have combined the strength of Petri nets with the strength of programming languages. Petri nets provide the primitives for describing synchronisation of concurrent processes, while programming languages provide the primitives for definition of data types and manipulation of their data values.
The paper focuses on the practical use of Coloured Petri Nets. It introduces the basic ideas behind the CPN language, and it illustrates how CPN models can be analysed by means of simulation, state spaces and condensed state spaces. The paper also describes how CP-nets can be extended with a time concept. In this way it is also possible to use CP-nets for performance evaluation, i.e., to evaluate the speed by which a system operates. Finally, we describe a set of computer tools that support the use of CP-nets. This tool set is used by more than three hundred organisations in forty different countries — including seventy-five commercial companies. It is available free of charge, also for commercial use.
The present paper does not contain any formal definitions. Instead all ideas and concepts are introduced by means of a number of small examples. Readers who want to consult the formal definitions can find these in [1], [2], [3], and [4]. The latter is a 3-volume text book providing a detailed description of CP-nets and their use. Volume I introduces the basic concepts and definitions. Volume 2 describes the different analysis methods. Volume 3 describes experiences from nineteen projects in which CP-nets and the CPN tools have been put to practical use. Most of the projects have been carried out in an industrial setting.
Kurt Jensen
Protocol specification using P-graphs, a technique based on coloured Petri Nets
Abstract
P-Graphs combine inhibitor Petri nets and abstract data types within the same algebraic framework. They are useful for the specification of concrete concurrent systems and in particular communication protocols. The inhibitor has been included to allow compact descriptions of systems by promoting the economy of data types. They are also necessary for the purging of resources; a common activity when modelling protocols or their services. This paper introduces P-Graphs with the aid of some simple examples. It also shows how to map P-Graphs to P-nets, which are Coloured Petri Nets (CP-nets) extended with place capacities and inhibitors. This is important for the analysis of P-Graph specifications, as P-nets can be transformed to CP-nets in almost all practical situations. Thus the analysis techniques of CP-nets can then be applied. Useful notation for capacities are introduced and their semantics defined in terms of the P-Graph. A notation for purging places of their tokens is also introduced, involving the superimposition of the inhibitor and normal arc. Two case studies, the Demon game and the M-Access Service of the Cambridge Fast Ring, are included to illustrate the use of the P-Graph and the extended notation for protocol specification.
Jonathan Billington
Distributed algorithms for networks of agents
Abstract
A new kind of algorithms, called distributed algorithms, has emerged during the last decade, aimed at efficiently solving problems that occur whenever distributed computing systems are to be made applicable to real-world problems.
Distributed computing systems are frequently organized as networks of agents, with each agent asynchronously interacting with some of its neighboring agents. Algorithms running on such networks are called distributed.
A network algorithm is a schema, intended to run on any network in a whole class of networks. Such an algorithm can be modeled as a high-level Petri net schema. Each interpretation of the schema yields an algorithm for a concrete network.
This paper suggests a variety of Petri net models of network algorithms, formally represents their most decisive properties, and proves their validity. To this end, well-known techniques such as place invariants and traps are adjusted to Petri net schemata, and new techniques to prove progress properties are suggested.
W. Reisig, E. Kindler, T. Vesper, H. Völzer, R. Walter
Efficient performance analysis techniques for stochastic well-formed nets and stochastic process algebras
Abstract
Stochastic Well Formed Nets and Stochastic Process Algebras are high level description languages for the specification and the performance evaluation of concurrent systems. In both formalisms the performance analysis of the modelled system can be performed by generating a continuous time Markov chain of the size of the model state space: this often leads to the so called state space explosion problem which can prevent the possibility of completing the desired analysis. In this chapter we will present two state space aggregation techniques, each working on one of the two formalisms, allowing efficient performance analysis. The advantages and disadvantages of the two techniques will be discussed and compared.
G. Franceschinis, M. Ribaudo
Modelling and analysis of distributed software using GSPNs
Abstract
This chapter discusses the role that Generalized Stochastic Petri Nets (GSPN) can play in the static analysis of distributed software. The material is organized along two main lines: the need and the advantages of studying both qualitative and quantitative aspects of a program, and the need for doing it in an automatic manner. The role of performance evaluation in the analysis of distributed software is illustrated through a small example, classical in the qualitative approach (the dining philosophers). Although small this example allows to point out the need and the requirements of automatic translation and to discuss the main hypothesis behind program performance evaluation through GSPN models. A procedure for the automatic generation of GSPN models starting from a distributed program written in a CSP-like language, and for the definition of program performance indices in terms of GSPN ones is then given and illustrated by means of a realistic example.
Susanna Donatelli, Giuliana Franceschinis
Backmatter
Metadaten
Titel
Lectures on Petri Nets II: Applications
herausgegeben von
Wolfgang Reisig
Grzegorz Rozenberg
Copyright-Jahr
1998
Verlag
Springer Berlin Heidelberg
Electronic ISBN
978-3-540-49441-6
Print ISBN
978-3-540-65307-3
DOI
https://doi.org/10.1007/3-540-65307-4