Petri net

As Petri nets models of discrete, predominantly distributed systems are known. The computer scientist Carl Adam Petri has it developed starting in the 1960s by finite automata, initially not in the form used today.

This Petri has been looking for basic principles for describing concurrent switching operations that were subsequently summarized to axiomatic theories of concurrency.

Today, variants of Petri nets are used not only in computer science for modeling, but also for example in theoretical biology, in the business process world, engineering, logistics and many other fields. Many other modeling techniques such as UML activity diagrams of the two have adopted principles of Petri nets.

5.1 Properties of Petri net models
5.2 Proof of properties
5.3 Software Tools

6.1 The most common form of high -level nets
6.2 Special case of free -choice
6.3 Generalizations of elementary networks
6.4 Time signed and stochastic networks
6.5 Higher Petri nets

7.1 The beginning
7.2 Developments since the 1980s
7.3 Current Issues

General Description and symbolism

In the standard version, provides a network is as a graph, which is composed of two types of nodes, places and transitions are called. The nodes are connected by edges, where an edge connects exactly one point with a transition or vice versa. The sites can be occupied by any number of brands. Such a label represents a distributed state of the system

Originally Petri has considered untyped brands. A network of such marks is called Place / Transition net ( short: S / T network or P / T network from English translated back as a place / transition net ). Later networks with typed brands and thus values were introduced, which are evaluated with predicates on transitions and edges. A network with typed brands is therefore called predicate / transition net, with the English name Coloured Petri Net ( CPN) - colored Petri net - is at least as common.

The dynamics of a network resulting from the firing transitions: a transition switches, these are identified by marks from the passages in their immediate upstream area and puts brands in the bodies in their post set, in each case as many as indicated at the edges. Would the transition need more brands than to actually be there, so they can not switch.

Mathematical representation of a Petri net

A P / T network can be displayed as a quintuple, is

( Disjunction ) and
The ( usually finite) set of points
The ( also finite) set of transitions
The flux ratio, which indicates the edge. So edges connect places with transitions or the other way always, never points with points or transitions with transitions.
The edge weight function, expanded on by
The initial marking

The dynamics of the networks will be explained in the next section.

Dynamics of Petri nets

The switching rule in P / T nets is as follows: A transition can from a mark ( listed ) and the power in the state to bring, if and only if the condition is satisfied for all points. It then writes.

This rule arises, in the manner of operational semantics, a perhaps infinite labeled graph with root, the reachability graph, from which all possible switching sequences and resulting state changes of the network can be read. It should however be noted that this is not a real concurrent semantics, since only the Sequentialisierungen can be considered as switching sequences of any concurrent event set.

The four-season network of Figure 0a has a very simple reachability graph having as four states and four transitions that are exactly the transitions due to its very simple structure.

The network example shown in Figure 0b, however, has twice as many reachable states, there may be fallen regardless of the season the bag of rice or not. This network also shows the suitability of Petri nets to represent states of distributed and causally independent, concurrent events in different parts of the system - "In China, drops a bag of rice at" and "a" can independently switch because they have neither a common condition still one of the other dependent.

Modeling with Petri nets

For Petri nets, many different variants and forms have been proposed. In the 1960s and 1970s first elementary variants were examined; nowadays often "high -level" forms are used. They are formally complex, but describe the modeled system intuitively accurate and immediate.

Introductory Example

As an introductory example for a high-level network Figure 1 shows a detail of largely abstracting model of a Keksautomaten: In the initial state, a coin is in the input slot of the machine. This allows the machine to perform a step further: He collected the coin and puts a Cracker Box in the output tray. This is how the final state.

Figure 2 refined and extended the model to its initial state by now the behavior of the interior of the machine is visible, along with the possible return of the deposited coin.

Components of Petri nets

The exact meaning of the figures 1 and 2 it follows from the universal principles modeling of Petri nets: In a ( given or planned discrete ) system identifying a set of components that are explicitly represented in the Petri net model. These include:

Objects or data elements that occur in the system, that is, produced, transformed and consumed (in the example: coins, Keksschachteln and signals). In the model, they are referred to as brands and shown graphically as possible " intuitive ".
Can contain memory components, the objects or data elements ( in the example: input slot, Removable shelf, checkout, signal space, Keksspeicher return ). In the model they are called places and graphically represented as circles or ellipses;
States, thus changing distributions of objects or data items in memory components. (Figure 2 describes a state with a coin entry slot and 3 Keksschachteln in Keksspeicher. All other memory components are empty ). In the model, a distribution of marks on the seats forms a marker. Graphical representations ( like those in Figures 1 and 2) typically show the start marker, which describes the initial state of the system.
Activities that can alter memory contents ( in 1: t, in Figure 2: a, b, c). In the model are referred to as transitions and plotted as a square or rectangle.
The description of the transitions from states into new states: (example: the transition from the initial to the final state in Figure 1 and from the beginning to an intermediate state in the figures Figure 2 and Figure 3). In the model, one can intuitively such steps as "river of brands by the arrows ' respectively.

Steps

From a given marking of a Petri net model of a new marker is reached by a transition occurs. These must be enabled. is activated when each ending with arrow starts at a place that contains a brand that is listed on the arrow itself. T in Figure 1 is thus activated; in Figure 2 a and c are enabled but not b. If an enabled transition occurs, the brands described above disappear from their seats, and for each at the onset of the arrow is created according to his address a mark on the place where ends.

In this way, in Figure 1 from the initial marking through the entry of t the end marker. From Figure 2 caused by the entry of a mark shown in Figure 3.

The " abstract " mark ( black dot) on the signal - space of Figure 3 is now enabled along with a Cracker Box in memory the transition b. By b occurs, eventually a Cracker Box appears in the sampling compartment. In Figure 2, the transition C is enabled. If c (instead of a), created a mark with a coin in return.

With the above rule for entry of transitions can be seen immediately, that lead or coins in the coin slot to the corresponding number of boxes in the sampling compartment. With a second coin in the coin slot, the transition a can be immediately after their first entry again occur, regardless of the (first) entry of b.

The behavior of distributed systems

The example above shows many links between the activities of a distributed system. Accordingly, the occurrence of two transitions can be related in different ways. In Figure 2, for example:

Elemental networks

Figure 4 shows a Petri net model of the Keksautomaten in which the brands for coins, signals and Keksschachteln are not distinguished: All are equally represented as "black" brands. Here arrows bear no inscription (according to the pictures of 1 to 3, each arrow should be labeled with ""). In this form, Petri nets have been created in the 1960s and often referred to as Platz-/Transitionsnetze. The rules for entry of a transition are particularly simple in this case: is activated when everyone starts at the arrow ending in a space that contains at least one token. These marks disappear upon entry to and it is a new brand on every place where an end with the onset of the arrow.

Such simple brands are intuitively reasonable if ( distributed ) control flow is modeled, for example, in the schema of mutual exclusion in Figure 5: Each of the two processes ( "left" and "right") to cycle through the three states locally, waiting critical. The key ensures that never both processes are also critical. In this example, every place always wears either no or a brand. One can therefore understand each place as a condition that is sometimes met and sometimes unfulfilled. Such networks are often referred to as Bedingungs-/Ereignisnetze.

Analysis of Petri nets

Properties of Petri net models

Important properties of a system should be reflected in his model. A Petri net must therefore represent not only behavior, but also properties of a system. For example, in the networks of Figures 2, 3 and 4, each reachable marking the property

It called for a place the number of marks on the mark. For every coin in the till so a Cracker Box has been delivered or ( with a mark on signal) yet. According applies to Figure 5

So it's always more than one process in its critical state. An obvious, but even for elementary system networks surprisingly complicated issue is the availability of a randomly selected marker:

It took years until it found an algorithm and thus the decidability of this accessibility problem has been demonstrated [ Mayr80 ]. Other important properties of an elementary system network are:

Terminated: Each starting in the initial marking sequence of steps of eventually reaches a deadlock, that is, a mark that does not activate any transition ( the Keksautomaten schedule ).
Deadlocks is: In no deadlocks are reachable ( the mutual exclusion deadlocks ).
Is alive: From each reachable marking is for each transition from a reachable marking, the activated ( the mutual exclusion is alive ).
Is weakly live: for each transition from there is a reachable marking, the activated ( Keksautomat and mutual exclusion are both weakly live ).
Is - limited for a number: Each place contains under any reachable marking at most brands ( of Keksautomat 3 - limited, the mutual exclusion is 1- limited ).
Is reversible: The initial marking is reachable from every reachable marking ( the mutual exclusion is reversible ).
Has a Home State: A home state of a label which is obtained from any reachable marking out in any case. Neither the Keksautomat nor the mutual exclusion has a home state.

Prove properties of

All properties are described, the question arises how to prove or disprove for a given start marked network. (see verification ) All of these properties are decidable for elementary nets, but only with algorithms whose complexity in practice is much too large. In practice, therefore algorithms for sufficient or necessary conditions are used. These algorithms are based on place invariants, debut marked cases, the marking equation and the coverage graph of a system network.

Software Tools

Since the 1980s, a variety of software tools for the creation and analysis of Petri nets created. As a universal tool for high-level nets in particular, the tool CPN Tools has prevailed. There are also a number of specific tools for specific network types, for example, for analysis of time -prone and stochastic networks or for special applications, such as service-oriented architectures.

Generalizations, special cases, variations

The most common form of high -level nets

The model of the Keksautomaten in ( Figure 1 - Figure 3) is an example of a high-level network. The full expressiveness of such networks is achieved using variables and functions in the inscriptions of the arrows. As an example, Figure 6 shows a variant of the modeled Keksautomaten with 4 coins in the input slot. For the fourth coin, there is no box in memory; the coin should therefore be returned in any case. To this end, Figure 6 contains a counter whose brand represents the number of available boxes. The transition a is enabled by setting the variable x assumes the current value of this brand. In addition, A is labeled with the condition x > 0, which has to be fulfilled to the inlet of a. This reduces each entry of a counter value by 1 and a is not enabled when the value is 0. So then each additional coin lands on c in the return.

Special case of free -choice

In the model of Keksautomaten of Figures 2, 3 and 4, the brand selected in the drop slot nondeterministic one of the transitions a or c. This choice depends on no additional preconditions; it is free.

In the system of mutual exclusion from Figure 5, the key to choose between the transitions b and e This choice, however, depends additionally depend on that are also and marked. It is not free.

A network is a free-choice net, if its structure all choices are already free, so even if two arrows that start at the same place, then: They end at transitions in which end no more arrows. Figure 7 outlines this condition. Obviously all models of Keksautomaten free-choice nets, but not the mutual exclusion in Figure 5 are

Whether any of the properties described in the above is true or not true, is decidable for free-choice nets with efficient algorithms.

Generalizations of elementary networks

Already in the 1970s, elementary nets were supplemented by numerous other means of expression. Three of them are described here:

Weight arrows: each arrow is assigned as the "weight" of a natural number. When connected to the inlet will flow transition arrow marks ( instead of only one mark) by the arrow.
The capacity of the courts limit: Each space is allocated as a " barrier" is a natural number. When would create more than marks on the occurrence of a transition is not enabled. Figure 8 shows an example.
A place for the absence of brands test: A place connected to a transition by a novel "inhibitor " edge. is not activated when one or more brands carries. Figure 9 outlines this design.

Weighted arrows and capacity- limited seats increase not really the expressive power: they can simulate with intuitively plausible means. However, one can actually express with inhibitor edges more and decide consequently less. In particular, the accessibility of networks is not decidable with inhibitor edges. Other means of expression are occasionally required to really accurately model behaves as a distributed system. For example, we want to represent in the system of mutual exclusion in Figure 5, each of the two processes forever in its local state, but not forever may persist in its critical state. We distinguish the cold transition a ( " does not necessarily when it is activated") from the hot transition b ( " occurs when it is enabled "). With the transitions b and e, it is even more complicated if we want to guarantee every waiting process that he will someday critical, we must demand fairness for b and e. With the difference between hot and cold transitions and with the requirement of fairness can characterize the set of " meant " processes of a Petri net much more accurate.

Time signed and stochastic networks

If transitions occur sorted, in Figure 2, for example, only a then b, this order shall be interpreted causally and not temporal. Then it is logical to be construed in Figure 2 with a second coin entry slot, the first entry of B and the second occurrence of a and independently of one another rather than the same.

However, there are systems with actions whose duration is to be modeled, or oriented in any way to watch. To model such systems, numerous variants time -prone Petri nets have been proposed. This places, transitions, trademarks and arrows with timestamps and time intervals are provided. These additives regulate the activation of transitions and generate new timestamps after the occurrence of a transition.

If two transitions and competing for the same brand a mark ( for example, compete in Figure 5 b and e to the brand on key ) and when it is reached again and again, you want to model on occasion that occurs with probability and with probability. This is something that developed a broad theory of stochastic networks is suitable.

Higher Petri nets

In order to uniformly describe systems containing mobile components and subsystems, Petrinetzformalismen have been developed in which the marks are in turn interpreted as a network instances. These so-called nets in nets several semantic variants are possible, which differ from one another with regard to the question of whether brands are to be understood as a network copies or merely as references.

These formalisms arise from an object-oriented approach in which instances of classes (network ) patterns can be generated and a communication between objects via defined interfaces is possible.

Some of the early representatives are the object of Petri nets Lakos (now in the face of intense development primarily of historical significance ) and Valk, who originally introduced this along with Jessen in the context of application systems.

The historical development

The beginning

Research on Petri nets began with the thesis of Carl Adam Petri in 1962 This work was initially little attention. ; Theoretical computer science has then pursued other issues and suggestions for practice Petris came too early. A first breakthrough in the theory came in the late 1960s with the use of Petri's ideas in the Project MAC at MIT. In the 1970s Platz-/Transitionsnetze have been studied worldwide, but quite often from the restricted viewpoint of formal languages .

The development since the 1980s

Since the early 1980s, many different variants of high -level networks have been proposed which use objects, data elements or symbols as trademarks. These formalisms increase the expressiveness of Platz-/Transitionsnetzen considerably. At the same time many techniques for analysis of Platz-/Transitionsnetzen to these formalisms could be generalized.

Were With increasing interest in distributed systems and distributed algorithms and proposed a number of new modeling techniques since the 1980s. Petri nets have stood up to these new developments; often they are used as a benchmark for the quality and expressiveness of models of distributed systems. Gives an overview of a range of applications of Petri nets.

Current Issues

With Petri nets systems are nowadays modeled their behavior consists of discrete, localized steps. These are often, but not exclusively systems that integrate computer or be simulated with computers. Among the currently most promising applications of Petri nets include the modeling of processes of systems biology, the world business process and service-oriented architectures.

Areas of application

Asynchronous circuit
Concurrent Programming
Parallel algorithm
Software Design
Workflow management
Verification of concurrent processes
Automation ( Control Products)
Material flow network
Business Process Modeling

Finite-state machine State transition system

645360