Some elementary rules of Petri net design are:

• 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.
• A path should begin and end with a place.
• 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.
  Rules of execution include the following:
• 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).

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

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 into 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 "send notice" transitions, is discussed below.

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 generated in the Rejecting and Accepting places, thus enabling the transitions Accept and Reject, as shown in step (b). Step (c) depicts the state of 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 places - Rejected and Mutex - have 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 notice - an acceptance or a rejection - is 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.

Petri Nets and Dead-Path Elimination
A mountain of academic papers has been written about the use of Petri nets to model process control flow. "Fundamentals of Control Flow in Workflows" (see References below), for example, develops precise Petri net implementations of common process patterns such as AND and XOR splits and joins, as well the thornier "dead-path elimination," considered in this section.

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 6, 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., don'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).

Part (b) shows the Petri net representation. Two crucial constructs used in this example are:

1. Color: The ability of a transition to branch to one of several places depending on the value of the token. In our case, the ability to follow different paths depending on whether "Sell Home" and "Get Mortgage" succeed or fail.
2. Lambda Transition: A transition that is strictly internal, used merely to drive control flow. A lambda transition fires immediately once it is enabled. In our case, lambda transitions are used to pass through the "dead path."

In the net, both the Sell Home and Get Mortgage transitions, representing the respective activities, branch upon completion in one of two paths: a true result leading to place T, and a false result to place F. A set of four lambda transitions then 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 is the converse of TF. Each of these transitions fires as soon as it is enabled. 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 into the place F, which, in turn, leads into lambda transitions representing the no-op versions of Buy Home and Hire Movers, which execute instantaneously and do nothing. This Petri net, simply stated, functions as a synchronizing truth table, allowing the purchase of the home and subsequent activities only when it receives "trues" for all inputs, and skipping past that logic otherwise.

Petri Nets and BPM Standards
Of the major BPM standards, three - BPEL, WSFL, and BPMN - 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."

Summary
For the BPM practitioner, theory, in the form of the Pi Calculus and the Petri net, actually matters! Why? First, because theory is mentioned so frequently in practical discussion of BPM, it is unavoidable: practitioners need to understand what the hype is all about. Second, theory injects much-needed rigor into a relatively immature BPM: Pi Calculus formalizes system interactions; Petri nets demonstrate precise control flow.

References

R. Milner. "The Polyadic Pi-Calculus: A Tutorial" in F.L. Bauer, W. Brauer, H. Schwichtenberg, editors, Logic and Algebra of Specification. Springer. 1993.

W.M.P. van der Aalst, "Pi Calculus versus Petri Nets: Let us Eat 'Humble Pie' Rather Than Further Inflate the 'Pi Hype'" Einhoven University, Department of Technology Management.

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.

N. Kavantzas. "Aggregating Web Services: Choreography and WS-CDL" (presentation), Oracle, April 2004.

Workflow Patterns Website: www.workflowpatterns.com

Petri Net Design Applet: http://is.tm.tue.nl/staff/wvdaalst/pn_applet/pn_applet.html