Section 3.3. Petri Nets

3.3. Petri Nets

The Petri network (or Petri net ), a notion devised in 1962 by the mathematician Carl Adam Petri, is a formal graphical process modeling language that can design systems as diverse as train track switches and business processes. With respect to the latter, Petri nets help describeand indeed, can be used to implementthe semantics of process control flow, including basic branch and join rules, as well as more complicated synchronization scenarios; notably, dead path elimination , a core topic in the languages WSFL and BPEL. Petri net theory saturates the literature on process patterns, a topic introduced in Chapter 4. The keen analysis of this work, undertaken by a group of pro-Petri authors referred to in this book as the P4, injects much-needed rigor into an historically ambiguous and haphazard subject. Though among BPM champions it lacks the renown of the pi-calculus, the Petri net is a valuable abstraction and merits the attention it has been paid.

3.3.1. Petri Nets in a Nutshell

The Petri net's characteristic appearance is that of an unusual assembly of circles, rectangles, arrows, and black dots. The beginner might at first mistake it for a state-transition diagram, reasoning that the circles and rectangles are states, the arrows transitions, and the dots some other curious artifact specific to the model. But although the Petri net shares with the state machine a preoccupation with the notion of state, to compare the two is like comparing apples and oranges.

In Petri's original conception, referred to as the classical net, the symbols are the following:

Place

Drawn as a circle, a place is a stopping point in a process, representing (in many cases) the attainment of a milestone.

Transition

A transition is a rectangle that represents an event or action.

Token

A token is a black dot residing in a place. Collectively, the set of tokens represents the current state of the process. During the execution of the process, tokens move from place to place.

Arc

An arc is a link from a transition to a place or a place to a transition.

The Java applet design editor and simulator (at http://is.tm.tue.nl/staff/wvdaalst/pn_applet/pn_applet.html) shown in Figure 3-4 is a typical Petri net modeling tool, which promotes a design-and-simulate approach to building a Petri net.

Figure 3-4. Petri net simulator Java applet

Designing a system involves dragging places and transitions onto a canvas, drawing arcs between them, and dropping an initial placement of tokens into a subset of the places. Simulating a design initiates a step-by-step run of the Petri net in which each step involves firing a transition and watching the tokens advance to new places.

Here are some elementary rules of Petri net design:

• An arc can connect a place to a transition, or a transition to a place, but never a place to a place, or a transition to a transition. Thus, the order of places and transitions alternates on a given path: place transition place transition place, and so on.

• Place and transition are many-to-many. A place can branch into multiple transitions. Multiple places can join into a single transition. A transition can branch into multiple places. Multiple transitions can converge into a single place.

• Tokens belong in places. A transition cannot contain a token.

Here are the rules of execution:

• A transition is enabled (i.e., capable of firing) if each input place (i.e., each place that links to it) has at least one token.

• When a transition fires, it consumes a token from each input place and generates a token for each output place (i.e., each place that the place links to).

The next section illustrates these concepts in action.

3.3.1.1 Example

Consider the process by which magazine editors might vote on whether to accept an article for publication. When the article arrives, it is distributed for review and voting to a number of editors. The voting completes either when two editors accept it or when one rejects it; in the former case, the author is sent an acceptance notice, in the latter a rejection. Figure 3-5 shows the Petri net for this process.

The Petri net starts at the New place. When the Send For Vote transition fires, the net branches into three paths: two for acceptance, one for rejection. In the acceptance paths, the place Accepting links to the transition Accept, whose output place is Accepted; in effect, when Accept fires, a token is passed from Accepting to Accepted. The rejection path is similar: the transition Reject moves a token from the place Rejecting to the place Rejected. The two acceptance paths converge in the transition Send accept notice. Similarly, in the rejection path, the place Rejected links to the transition Send reject notice. Each of the send notice transitions links to the output place Done, the final step in the process. The curiously named place Mutex, an input to the send notice transitions, is discussed later in this section.

The behavior of the voting process is best understood by following the path of tokens through the net. Step (a) shows the initial placement: one token in New and one in Mutex. The shading of the transition Send for vote indicates that it is enabled; it is enabled because its one input place, New, has a token. When Send for vote fires, the token is removed from New, and tokens are populated in the Rejecting and Accepting places, thus enabling the transitions Accept and Reject, as shown in (b). Step (c) depicts the state of

Figure 3-5. Petri net process for vote

the net after one acceptance and one rejection. The token from the uppermost Accepting has now moved to Accepted; likewise, Rejecting has now transitioned to Rejected. Of the two send notice transitions, only Send reject notice is enabled because both of its input placesRejected and Mutexhave a token. When Send reject notice fires in Step (d), the tokens from Rejected and Mutex disappear, and a token is moved into Done.

Exemplifying the powerful synchronization capabilities of Petri nets is the Mutex (mutual exclusion) place, which ensures that only one noticean acceptance or a rejectionis sent to the author. Mutex is an input place to both the Send accept notice and Send reject notice transitions, and hence neither of these transitions can fire unless Mutex has a token. However, in the initial token placement, Mutex has exactly one token. If two acceptances and one rejection occur at roughly the same time, both Send accept notice and Send reject notice will contend for that token. But when one transition fires, it will consume the token, immediately disabling the other transition, thereby preventing it from firing.

3.3.1.2 Petri Net Extensions

The high-level Petri net extends the classical conception considered previously and facilitates the construction of larger and more complex processes. It supports the following constructs:

Color

In the classical model, tokens are indistinguishable. In the color extension, each token has an associated set of attributes that distinguishes it from the others. Token identity makes possible two new Petri net features: conditional branching (when a transition fires, select one of several output places based on attributes of the fired token) and guards (when a transition is about to occur, a decision whether to allow it can be made based on the attributes of the tokens about to be passed).

The rationale for the term "color" is that in the classical model all tokens are black, but now tokens can be differentiated by color, making them distinguishable. Another way to think of it is that classically tokens had no attributes, but now they do and hence are distinguishable.

Hierarchy

Some processes are too large to be represented as a single net. The hierarchy extension permits a modular approach in which a net can initiate subnets on the firing of a transition. The idea is similar to that of child states in the state machine methodologies of the Unified Modeling Language (UML) and Real-time Object-Oriented Modeling (ROOM) .

3.3.2. Petri Nets and BPM Patterns

The Petri net is a suitable model for control flow in business processes. Van der Aalst and his group, the P4 (mentioned previously), have published a mountain of papers on control flow and patterns, much of it applying ideas of Petri nets to demonstrate semantics. This section explores the P4 findings on basic AND, XOR, and dead path elimination patterns.^[*]

^[*] B. Kiepuszewski, A. H. M. ter Hofstede, W. M. P. van der Aalst, "Fundamentals of Control Flow in Workflows," Acta Informatica, 39(3):143-209, 2003

3.3.2.1 AND and XOR split and join

Every BPM modeling language permits a process to branch into parallel paths and then later join these paths back into one. In the process fragment shown in Figure 3-6, when activity A completes, activities B and C begin running in parallel; activity D begins only upon completion of both B and C.

Figure 3-6. Typical AND split and join in pseudocode

Figure 3-7 shows an exclusive-OR conditional split from A to either B or C; when the split is joined back, activity D is executed.

Figure 3-7. Typical XOR split and join in pseudocode

The P4 approach to modeling flow charts as Petri nets is to represent flow chart activities as transitions, where the name of the transition is the name of the activity. Some transitionsknown as lambda (also known as anonymous) transitionsare left unlabeled (i.e., unnamed), as are all places. Places and lambda transitions, as we will see, combine to drive the control flow (that is, the parallel, conditional, sequential, and synchronization logic) of a process.engine. A Petri net model for the AND split and join is shown in Figure 3-8.

Figure 3-8. Petri net AND split and join

The Petri net model for an XOR split and an OR join is shown in Figure 3-9.

Figure 3-9. Petri net XOR split and OR join

The best way to understand the behavior of the model, in particular the unusual lambda transitions, is to trace the flow of tokens through these processes. Figure 3-10 shows the AND case.

Figure 3-10. Token flow in Petri AND split-join

In Step 1, transition A is enabled because its input place has a token. When A completes, a lambda transition is enabled (Step 2) that accomplishes the split to B and C by duplicating the token from its input place to the input places of B and C. At this point, B and C are enabled (Step 3), and in unpredictable order (Steps 4 and 5), B and C complete. The lambda transition that follows B and C, by virtue of Petri net token synchronization semantics, waits for tokens from both of the branches before commencing (Step 6). Once it fires, transition D is enabled, and its completion ends the process (Step 7). The key to the split is the token duplication from a single input place to two output places; the key to the join is the synchronization of input places.

The XOR case, shown in Figure 3-11, starts the same way as the AND case.

Figure 3-11. Token flow in Petri XOR split-OR Join

In Step 1, transition A, having a token in its input place, is enabled and executes. The succeeding lambda transition in Step 2 evaluates a condition based on information in the token and accordingly passes that token to exactly one of its output places. In the example, that output place is the input to B (Step 3), and when B completes (Step 4), its succeeding lambda transition passes through the token to enable D (Step 5), whose completion in Step 6 concludes the process. The key to the split is the conditional flow made possible by the color extension; the join is trivial.

3.3.2.2 Dead path elimination

Dead path elimination is a technique used in languages such as BPEL and WSFL to bypass, or "pass through," activities whose preconditions are not met. For example, in Part (a) of Figure 3-12, the activity Buy new home waits for the parallel activities Sell home and Get mortgage to complete, and it executes only if both have a true result. If at least one is false, the execution of Buy new home is skipped (i.e., can't buy a new home without financing and the sale of your old home), as is the execution of the successor activity Hire movers (i.e., don't call movers if you aren't moving).

Figure 3-12. Dead path elimination for home move

Part (b) shows the Petri net representation. Both the Sell home and Get mortgage transitions, representing the respective activities, branch upon completion in one of two paths: a true result leads into the place T, a false result to place F. A set of four lambda transitions waits for and aggregates the results of the two activities: TT is enabled when both activities return true, FF when both are false, TF when Sell home is true and Get mortgage false, and FT the converse of TF. The TT transition passes a token to the place T, thereby enabling the Buy home transition, and, further downstream, Hire movers. TF, FT, and FF each link to the place F, which leads into lambda transitions representing the no-op version of Buy home and Hire movers. The Petri net functions as a synchronizing truth table, allowing the purchase of the home and subsequent activities only when it receives "trues" for all inputs.

3.3.3. Petri Nets and the Standards

Of the major BPM standards, threeBPEL (Chapter 5), WSFL (Chapter 9), and BPMN (Chapter 6)have roots in Petri nets. Each standard uses the notion of token passing to describe the semantics of control flow. The BPMN specification uses the token concept throughout. In WSFL and BPEL, the most striking Petri-net-inspired discussion is dead path elimination.