15.4. Foundations for Process Theory

Process modeling is an application that has motivated many technologists to build automated systems to support process definition, execution, management, and so on. There are probably well over a hundred tools and techniques in current circulation, with more arriving all the time. Unfortunately, most of these approaches are based on vague intuitions about process features, with the result that their associated semantics are often a matter of guesswork. This is an unfortunate state of affairs if we have ambitions to derive information system elements from business models, because our model does not provide a definitive baseline to work from. The problems resulting from this have prompted interest in more formal ways of defining processes. The formality is not necessarily something that needs to be exposed at the business level, but we need to be sure that our business models are built on firm foundations.

The technique that has attracted most attention in this regard is the use of Petri nets. These were first defined in Carl Adam Petri’s Ph.D. thesis in 1962. They immediately attracted interest from theorists, but it took a little longer for them to find practical uses. Petri nets are now used in many fields, and the basic concepts have been extended in several ways. This section looks briefly at how they can be used to represent business processes. References to more detailed treatments of Petri nets are given in the chapter notes.

Fundamentally, a Petri net is a bipartite graph with variable markings at some of the nodes. There are two node types: places and transitions. Places and transitions are connected by directed arcs. The possible connections are place to transition or transition to place, but never place to place or transition to transition. A Petri net is used to represent a dynamic situation, but the structure of the graph does not change as the situation unfolds. Instead, the different conditions are marked by different arrangements of tokens at the places in the network. A particular configuration of tokens is sometimes referred to as the state of the network— “state” here does not have quite the same meaning that it does in the context of state machines. Tokens are created at places, or removed from places, according to certain rules. A token cannot exist at a transition. Graphically, places are usually shown as large open circles, tokens as small filled circles, and transitions as either rectangles or thick bars. Figure 15.25 shows a simple Petri net with tokens at some of the network places.

A transition is said to be enabled if it has a token at each of its input places. An enabled transition can fire, and in doing so it consumes a token from each of its input places and produces a token at each of its output places. For the configuration shown in Figure 15.25, transition tl is enabled but t2 and t3 are not (t3 does not have a token at all of its input places). The resulting situation after transition tl has fired is shown in Figure 15.26. A token has been removed from pi and a new token added at p2.

Conceptually, tokens are consumed or created at transitions. Transitions can have input places (the arc from the place is directed toward the transition) or output places (the arc to the place is directed away from the transition). The same place can be both an input place and an output place relative to some transition. In Figure 15.25, transition tl has pi as an input place and p2 as an output place. Place p3 is both an input place and an output place for t3.

Now both t2 and t3 are enabled. Since we have only one token at p2, only one of t2 and t3 can fire. In a basic Petri net this situation is nondeterministic: we cannot decide in advance which of the transitions will fire. Adding more tokens to place p2 would not solve the problem: transitions t2 and t3 would still compete for each token. However, in this particular case, the same state results whichever transition fires. If t2 fires, it consumes the token at p2 and produces a token at p4. If t3 fires, it consumes the tokens at p2 and p3 and produces a token at p3 and p4. The final result is shown in Figure 15.27. At this point, no further transitions are enabled and activity ceases.

In order to make use of a Petri net, we have to map its elements onto the real world. Generally speaking, tokens are taken to represent objects (people, goods, machines), information conditions, or object status; places represent buffers, channels, geographical locations, conditions, or situations; and transitions represent events, transportation, or transformation. In the specific case of business process modeling, transitions are usually taken to represent business activities, whereas the combination of places and tokens determines when the activity is carried out.

The basic constructs of the Petri net can be composed into more convenient forms to provide building blocks to model business processes. Some constructs appear frequently and it’s useful to be able to insert these into a model without repeating the basic Petri elements that they are built from. Processes commonly need to split into parallel branches at some point and then reconcile the branches at some later point—for example, by waiting until activities on preceding parallel branches have completed. Various forms of “Split” and “Join” (or “Merge”) are commonplace in process models. Both of these come in two flavors: OR and AND. An OR-split sends a token along one path or another; an AND-split sends a token along multiple paths. Similarly, an OR-join expects a token to arrive on one of several branches, whereas an AND-join expects a token on all branches.

Figure 15.28 shows the high level elements with their equivalent constructs in a basic Petri net. The notation used for the high level constructs is taken from YAWL: a workflow language based firmly on Petri nets. Note particularly that the construction for the OR-split is nondeterministic in its basic Petri net form. To make it more useful for business modeling, we assume the existence of a business rule (or rule set) that is able to steer a token in the appropriate direction.

Given these constructs, we can begin to put together networks of increasing complexity. As an example, Figure 15.29 shows how we can define some classical looping constructs using Petri nets.

The standard Petri net allows us to construct models of dynamic behavior, but it has some shortcomings for process modeling. Nets that result from the primitive constructs become too large and clumsy for realistic cases, and it’s difficult to represent finegrained business information. Because of this, a number of extensions have been proposed to make Petri nets more useful in a business context.

The first idea is to use different types of token. In the basic Petri net, tokens are all of the same kind. If we retain the place/transition network but allow multiple token types, we open up some new possibilities. For example, we can make the firing of a transition dependent on token types and values. Conceptually, we can think of the different token types as being tokens of different colors, and so a network extended in this way is known as a colored Petri net.

A second important idea is to provide ways of organizing networks hierarchically. We have already seen this concept from other perspectives. In the case of Petri nets we have networks containing subnetworks, potentially nested to several levels. At a high level, we can represent a subnetwork (which might correspond to a subprocess) as a single block, allowing us to selectively hide detail in complex networks.

A third extension introduces the dimension of time. Activities are typically modeled as transitions, but in a basic Petri net, transitions are considered instantaneous. We can provide a more realistic simulation by time stamping tokens so that we have information about their temporal evolution, and allowing transitions to have delays, that would represent the passage of time while an activity is carried out in the real world.

Figure 15.30 shows an example of a hierarchical network for a process to handle complaints that uses different types of token to indicate different cases that are being progressed.

Several other candidate formalisms for business processes have been proposed. One is the use of state machines, of the kind we have already discussed. There is not a single state machine formalism, but several state machine frameworks have been formally defined, notably by David Harel. If we begin with a state machine that has a formal description, then we can build other constructs on top that inherit the formal foundations.

Another approach that has received a fair amount of publicity is the use of process algebras—the most prominent example being the pi calculus defined by Robin Milner. In these approaches, a series of algebraic expressions replaces a network as the basis for defining process structure. For space reasons, we won’t go into detail here, but the following example provides something of the flavor of the approach. As a simple example we can take a common workflow pattern: a parallel split. (We discuss this and other patterns in more detail later in the chapter.) Figure 15.31 shows equivalent specifications of this pattern using both Petri nets and pi calculus.

There is currently no agreement on whether algebraic approaches offer significant advantages over other approaches such as Petri nets. They are certainly not at all useful at the business level, but their place is more likely to be hidden under the covers of a tool that presents a more user-friendly interface.

So far, we’ve looked at some basic ideas about describing information dynamics in a fairly generic way. The features of process- and state-based models discussed so far can be found in many methodologies and tools that address this area. To provide a more concrete illustration, we turn to one of the most widely used modeling approaches: the Unified Modeling Language (UML).