Control-Flow Patterns

Downloads of the original and revised control-flow patterns papers:

N. Russell, A.H.M. ter Hofstede, W.M.P. van der Aalst, and N. Mulyar.
Workflow Control-Flow Patterns: A Revised View
. (PDF, 1.04Mb)
BPM Center Report BPM-06-22
, BPMcenter.org, 2006.

W.M.P van der Aalst, A.H.M. ter Hofstede, B. Kiepuszewski, and A.P. Barros.
Workflow Patterns.
(PDF, 718 Kb).
Distributed and Parallel Databases,
14(3), pages 5-51, July 2003

Introduction

The Workflow Patterns Initiative was established with the aim of delineating the fundamental requirements that arise during business process modelling on a recurring basis and describe them in an imperative way. The first deliverable of this research project was a set of twenty patterns describing the control-flow perspective of workflow systems. Since their release, these patterns have been widely used by practitioners, vendors and academics alike in the selection, design and development of workflow systems [vdAtHKB03]. This body of work presents the first systematic review of the original twenty control-flow patterns and provides a formal description of each of them in the form of a Coloured Petri-Net (CPN) model. It also identifies twenty three new patterns relevant to the control-flow perspective. Detailed context conditions and evaluation criteria are presented for each pattern and their implementation is assessed in fourteen commercial offerings including workflow and case handling systems, business process modelling formalisms and business process execution languages.

Revisiting the Original Patterns

Here we present a revised description of the original twenty control-flow patterns previously presented in [vdAtHKB03]. Although this material is motivated by earlier research conducted as part of the Workflow Patterns Initiative, the descriptions for each of these patterns have been thoroughly revised and a new set of evaluations have been undertaken. In several cases, detailed review of a pattern has indicated that there are potentially several distinct ways in which the original pattern could be interpreted and implemented. In order to resolve these ambiguities, we have taken the decision to base the revised definition of the original pattern on the most restrictive interpretation of its operation and to delineate this from other possible interpretations that could be made. In several situations, a substantive case exists for consideration of these alterative operational scenarios and where this applies, these are presented in the form of new control-flow patterns.

New Control Flow Patterns

Review of the patterns associated with the control-flow perspective over the past few years has led to the recognition that there are a number of distinct modelling constructs that can be identified during process modelling that are not adequately captured by the original set of twenty patterns. Here we present twenty three new control-flow patterns that augment the existing range of patterns described above and elsewhere [vdABtHK00, vdAtHKB03]. In an attempt to describe the operational characteristics of each pattern more rigourously, we also present a formal model in Coloured Petri-Net (CPN) format for each of them. In fact the explicit modelling of the original patterns using CPN Tools helped identify a number of new patterns as well as delineating situations where some of the original patterns turned out to be collections of patterns.

Basic Control Flow Patterns

This class of pattern captures elementary aspects of process control and are similar to the definitions of these concepts initially proposed by the Workflow Management Coalition (WfMC) [Wor99].

1. Sequence
2. Parallel Split
3. Synchronization
4. Exclusive Choice
5. Simple Merge

Advanced Branching and Synchronization Patterns

Here we present a series of patterns which characterise more complex branching and merging concepts which arise in business processes. Although relatively commonplace in practice, these patterns are often not directly supported or even able to be represented in many commercial offerings. The original control-flow patterns identified four of these patterns: Multi-Choice, Synchronizing Merge, Multi-Merge and Discriminator.

In this revision, the Multi-Choice and Multi-Merge have been retained in their previous form albeit with a more formal description of their operational semantics. For the other patterns however, it has been recognized that there are a number of distinct alternatives to the manner in which they can operate. The original Synchronizing Merge now provides the basis for three patterns: the Structured Synchronizing Merge (WCP7), the Acyclic Synchronizing Merge (WCP37) and the General Synchronizing Merge (WCP38).

In a similar vein, the original Discriminator pattern is divided into six (6) distinct patterns: the Structured Discriminator (WCP9), the Blocking Discriminator (WCP28), the Cancelling Discriminator (WCP29), the Structured Partial Join (WCP30), the Blocking Partial Join (WCP31) and the Cancelling Partial Join (WCP32). One other addition has been the Generalized AND-Join (WCP33) which identifies a more flexible AND-join useful in concurrent processes.

Of these patterns, the original descriptions for the Synchronizing Merge and the Discriminator are superseded by their structured definitions.

6. Multi-Choice
7. Structured Synchronizing Merge
8. Multi-Merge
9. Structured Discriminator
28. Blocking Discriminator
29. Cancelling Discriminator
30. Structured Partial Join
31. Blocking Partial Join
32. Cancelling Partial Join
33. Generalised AND-Join
37. Local Synchronizing Merge
38. General Synchronizing Merge
41. Thread Merge
42. Thread Split

Multiple Instance Patterns

Multiple instance patterns describe situations where there are multiple threads of execution active in a process model which relate to the same activity (an hence share the same implementation definition). Multiple instances can arise in three situations:

  1. An activity is able to initiate multiple instances of itself when triggered (we denote this form of activity a multiple instance activity);
  2. A given activity is initiated multiple times as a consequence of it receiving several independent triggerings (e.g. as part of a loop or in a process instance in which there are several concurrent threads of execution as might result from a Multi-Merge for example; and
  3. Two or more activities in a process share the same implementation definition. This may be the same activity definition in the case of a multiple instance activity or a common sub-process definition in the case of a block activity. Two (or more) of these activities are triggered such that their executions overlap (either partially or wholly).

Although all of these situations potentially involve multiple concurrent instances of an activity or sub-process, it is the first of them in which we are most interested as they require the triggering and synchonization of multiple concurrent activity instances. This group of patterns focusses on the various ways in which these events can occur.

Similar to the differentiation introduced in the Advanced Branching and Synchronization Patterns to capture the distinction between the Discriminator and the Partial Join pattern variants, three new patterns have been introduced to recognize alternative operational semantics for multiple instances. These are the the Static Partial Join for Multiple Instances (WCP34), the Cancelling Static Partial Join for Multiple Instances (WCP35) and the Dynamic Partial Join for Multiple Instances (WCP36).

12. Multiple Instances without Synchronization
13. Multiple Instances with a Priori Design-Time Knowledge
14. Multiple Instances with a Priori Run-Time Knowledge
15. Multiple Instances without a Priori Run-Time Knowledge
34. Static Partial Join for Multiple Instances
35. Cancelling Partial Join for Multiple Instances
36. Dynamic Partial Join for Multiple Instances

State-based Patterns

State-based patterns reflect situations for which solutions are most easily accomplished in process languages that support the notion of state. In this context, we consider the state of a process instance to include the broad collection of data associated with current execution including the status of various activities as well as process-relevant working data such as activity and case data elements.

The original patterns include three patterns in which the current state is the main determinant in the course of action that will be taken from a control-flow perspective. These are: Deferred Choice (WCP16), where the decision about which branch to take is based on interaction with the operating environment, Interleaved Parallel Routing (WCP 17), where two or more sequences of activities are undertaken on an interleaved basis such that only one activity instance is executing at any given time and Milestone (WCP18), where the enabling of a given activity only occurs where the process is in a specific state.

In recognition of further state-based modelling scenarios, four new patterns have also been identified. These are: Critical Section (WCP39), which provides the ability to prevent concurrent execution of specific parts of a process, Interleaved Routing (WCP40), which denotes situations where a group of activities can be executed sequentially in any order, and Thread Merge (WCP41) and Thread Split (WCP42) which provide for coalescence and divergence of distinct threads of control along a single branch.

16. Deferred Choice
17. Interleaved Parallel Routing
18. Milestone
39. Critical Section
40. Interleaved Routing

Cancellation and Force Completion Patterns

Several of the patterns above (e.g. (WCP6) Structured Synchronizing Merge and (WCP9) Structured Discriminator) have variants that utlize the concept of activity cancellation where enabled or active activity instance are withdrawn. Various forms of exception handling in processes are also based on cancellation concepts. This section presents two cancellation patterns - Cancel Task (WCP19) and Cancel Case (WCP20).

Three new cancellation patterns have also been identified Cancel Region (WCP25), Cancel Multiple Instance Activity (WCP26) and Complete Multiple Instance Activity (WCP27).

19. Cancel Task
20. Cancel Case
25. Cancel Region
26. Cancel Multiple Instance Activity
27. Complete Multiple Instance Activity

Iteration Patterns

The following patterns deal with capturing repetitive behaviour in a workflow.

10. Arbitrary Cycles
21. Structured Loop
22. Recursion

Termination Patterns

The following patterns deal with the circumstances under which a workflow is considered to be completed.

11. Implicit Termination
43. Explicit Termination

Trigger Patterns

The following patterns deal with the external signals that may be required to start certain tasks.

23. Transient Trigger
24. Persistent Trigger

Disclaimer

We, the authors and the associated institutions, assume no legal liability or responsibility for the accuracy and completeness of any product-specific information contained in this body of work. All possible efforts have been make to ensure that the results presented are, to the best of our knowledge, up to date and correct.