The Workflow Patterns in Asynchronous Pi-Calculus

Introduction

This article describes the representation of the Workflow Patterns in the asynchronous pi-calculus. It is based on a corresponding paper published at the 3rd BPM conference in Nancy, France (2005).

The asynchronous pi-calculus only supports asynchronous communication. This kind of communication uses a "medium" for transfering information among agents. Since it is inherent to the medium that it cannot be observed if—or when—the information is delivered, nothing else than inaction is allowed to appear after a send prefix. To keep a straight implementation of the asynchronous idea, also unguarded output actions are disallowed in summations. If they would be allowed, all information contained in a summation had to be offered via the "medium", but some (the non-selected) had to be withdrawn afterwards. Since this is difficult (especially in real environments), it is left out. Furthermore, the match prefix is dropped to simplify the grammar:

P ::= 'x<y>.0 | M | P|P | (^v)P | A(x,...,y)
M ::= 0 | x(z).P | t.P | M + M

The grammar of the asynchronous pi-calculus only consists of two levels: agents (processes) and summations. We use <⋅> to represent the functional part of an activity in contrast to an internal action t.

Basic Control Flow Patterns

The basic control flow patterns capture elementary aspects of control flow.

Sequence

An activity in a business process is enabled after the completion of another activity in the same process.

A = <⋅>.'b.0
B = b.<⋅>.B'

Agent A (representing an activity) signals its finalization via 'b, that triggers the activation of agent B representing another activity.

Parallel Split

A point in the business process where a single thread of control splits into multiple threads of control which can be executed in parallel, thus allowing activities to be executed simultaneously or in any order.

A = <⋅>.('b.0 | 'c.0)
B = b.<⋅>.B'
C = c.<⋅>.C'

Synchronization

A point in the business process where multiple parallel (complex) activities converge into one single thread of control, thus synchronizing multiple threads. It is an assumption of this pattern that each incoming branch of a synchronizer is executed once.

B = <⋅>.'d1.0
C = <⋅>.'d2.0
D = d1.d2.<⋅>.D'

Exclusive Choice

A point in the business process where, based on a decision or data, one of several branches is chosen.

A = <⋅>.('b.0 + 'c.0)
B = b.<⋅>.B'
C = c.<⋅>.C'

Simple Merge

A point in the business process where two or more alternative branches come together without synchronization. It is an assumption of this pattern that none of the alternative branches is ever executed in parallel.

B = <⋅>.'d.0
C = <⋅>.'d.0
D = d.<⋅>.D'

Advanced Branching and Synchronization Patterns

Multiple Choice

A point in the workflow process where, based on a decision or data, a number of branches are chosen.

A = <⋅>.(t.'b.0 + t.'c.0 + t.('b.0 | 'c.0))
B = b.<⋅>.B'
C = c.<⋅>.C'

Synchronizing Merge

A point in the business process where multiple paths converge into one single thread. If more than one path is taken, synchronization of the active threads needs to take place. If only one path is taken, the alternative branches should reconverge without synchronization. It is an assumption of this pattern that a branch that has already been activated, cannot be activated again while the merge is still waiting for other branches to complete.

B = <⋅>.'d1.0
C = <⋅>.'d2.0
D = d1.<⋅>.D' + d2.<⋅>.D' + d1.d2.<⋅>.D'

This pattern makes a non-deterministic choice. If information about the incoming branches is available (required for execution), the representation is different.

Multiple Merge

A point in a business process where two or more branches reconverge without synchronization. If more than one branch gets activated, possibly concurrently, the activity following the merge is started for every activation of every incoming branch.

B = <⋅>.'d.0
C = <⋅>.'d.0
D = d.(<⋅>.D' | D)

Discriminator

The discriminator is a point in a business process that waits for one of the incoming branches to complete before activating the subsequent activity. From that moment on it waits for all remaining branches to complete and "ignores" them. Once all incoming branches have been triggered, it resets itself so that it can be triggered again.

A = <⋅>.'d1.0
B = <⋅>.'d2.0
C = <⋅>.'d3.0
D = (^h,exec)( d1.'h.0 | d2.'h.0 | d3.'h.0 | h.'exec.h.h.D | exec.<⋅>.D')

Structural Patterns

Arbitrary Cycles

A point in a business process where one or more activities can be done repeatedly.

A = a.(<⋅>.'b.0 | A)
B = b.(<⋅>.'c.0 | B)
C = c.(<⋅>.(t.'a.0 + t.'d.0) | C)
D = d.<⋅>.D'

The code pattern describes a cycle that includes A, B, and C.

Implicit Termination

A given complex activity should be terminated when there is nothing else to be done. In other words, there are no active activities in the business process and no other activity can be made active (and at the same time the business process is not in deadlock).

A = <⋅>.0

Multiple Instance Patterns

All multiple instance activities should be abstracted to <⋅> for analysis.

Multiple Instances without Synchronization

Within the context of a single process instance multiple instances of an activity are created, i.e., there is a facility to spawn off new threads of control. Each of these threads is independent of other threads. Moreover, there is no need to synchronize these threads.

A = a.(<⋅>.0 | <⋅>.0 | <⋅>.0 | A')

Agent A creates three parallel instances of itself (represented by <⋅>) and continues immediately as A'.

Multiple Instances with a priori Design Time Knowledge

For one process instance an activity is enabled multiple times. The number of instances of a given activity for a given process instance is known at design time. Once all instances are finished some other activity needs to be started.

A = (^h) a.(<⋅>.'h.0 | <⋅>.'h.0 | <⋅>.'h.0 | h.h.h.A')

Agent A creates three parallel instances of itself and continues as A' after all of them have finished (due to the synchronization via h).

Multiple Instances with a priori Runtime Knowledge

For one process instance an activity is enabled multiple times. The number of instances of a given activity for a given process instance varies and may depend on characteristics of the process instance or availability of resources, but is known at some stage during runtime, before the instances of that activity have to be created. Once all instances are finished some other activity needs to be started.

Multiple Instances without a priori Runtime Knowledge

For one process instance an activity is enabled multiple times. The number of instances of a given activity for a given process instance is not known during design time, nor is it known at any stage during runtime, before the instances of that activity have to be created. Once all instances are finished, some other activity needs to be started. The difference with previous pattern (Multiple Instances with a priori Runtime Knowledge) is that even while some of the instances are running or already finished, new ones can be created.

A = a.(A1(b) | A2)
A1(prev) = (^next) t.('create<next,prev>.0 | A1(next)) + t.'prev.0
A2 = create(next,prev).(<⋅>.next.'prev.0 | A2)
B = b.<⋅>.B'

State-based Patterns

Deferred Choice

A point in the business process where one of several branches is chosen. In contrast to the exclusive choice pattern, the choice is not made explicitly (e.g. base on data or a decision) but several alternatives are offered to the environment. However, in contrast to the parallel split pattern, only one of the alternatives is executed. This means that once the environment activates one of the branches the other alternative branches are withdrawn. It is important to note that the choice is delayed until the processing in one of the alternative branches is actually started, i.e. the moment of choice is as late as possible.

A = a.<⋅>.(env1.'b.0 + env2.'c.0)
B = b.<⋅>.B'
C = c.<⋅>.C'

The choice is guarded by environmental triggers env1 and env2.

Interleaved Parallel Routing

A set of activities is executed in an arbitrary order: Each activity in the set is executed, the order is decided at runtime, and no two activities are executed at the same moment (i.e. no two activities are running for the same process instance at the same time).

A = <⋅>.('x.0 | y.('x.0 | y.A'))
B = x.<⋅>.'y.0
C = x.<⋅>.'y.0

Milestone

The enabling of an activity depends on the process instance being in a specific state, i.e. the activity is only enabled if a certain milestone has been reached which did not expire yet.

A = a.'check.<⋅>.A'
M = check.M + withdraw.0

The milestone is represented by the agent M. It provides either a check (an unlimited number of times) or the withdraw of the milestone.

Cancelation Patterns

Cancel Activity

An enabled activity is disabled, i.e. a thread waiting for the execution of an activity is removed.

A = a.<⋅>.A' + cancel.0

Cancel Case

A process instance is removed completely (i.e., even if parts of the process are instantiated multiple times, all descendants are removed).

Cancel process instance equals the cancel activity pattern with the difference that all remaining agents representing nodes of a process graph receive a cancel name. To implement this pattern, all agents representing nodes of a process graph have to be enhanced with an according sum.