Evaluation of Correctness Criteria for Dynamic Workflow Changes [original]

Evaluation of Correctness Criteria for Dynamic

Workﬂow Changes

Stefanie Rinderle, Manfred Reichert, and Peter Dadam

University of Ulm, Faculty of Computer Science,

Dept. Databases and Information Systems

{rinderle, reichert, dadam}@informatik.uni-ulm.de

Abstract. The capability to dynamically adapt in-progress workﬂows

(WF) is an essential requirement for any workﬂow management system

(WfMS). This fact has been recognized by the WF community for a long

time and diﬀerent approaches in the area of adaptive workﬂows have

been developed so far. They either enable WF type changes and their

propagation to in-progress WF instances or (ad-hoc) changes of single

WF instances. Thus, at ﬁrst glance, many of the major problems related

to dynamic WF changes seem to be solved. However, this picture changes

when digging deeper into the approaches and considering implementation

and usability issues as well. This paper presents important criteria for

the correct adaptation of running workﬂows and analyzes how actual

approaches satisfy them. At this, we demonstrate the strengths of the

diﬀerent approaches and provide additional solutions to overcome current

limitations. These solutions comprise comprehensive correctness criteria

as well as migration rules for change realization.

1 Introduction

A rapidly changing environment and a turbulent market force any company to

change their business processes ever more frequently [1]. Process changes become

necessary, for example, when new laws come into eﬀect, optimized or restructured

business processes are to be implemented, exceptional situations occur, or rapid

reactions to a changed market are required. Therefore, a critical challenge for

the competitiveness of any enterprise is its ability to quickly react to business

process changes [2,3,4].

As pointed out in [2], basically, changes can take place at two levels – the

WF type and the WF instance level. Very often changes at the WF instance

level are applied in an ad-hoc manner, leading to WF instances with biased ex-

ecution schema when compared to their original WF schema – in the following,

we denote these WF instances as biased. Ad-hoc changes become necessary in

conjunction with real-world exceptions, e.g., a sudden circulatory collapse of a

This work was done within the research project “Change management in adaptive

workﬂow systems”, which has been founded by the German Research Community

(DFG).

W.M.P. van der Aalst et al. (Eds.): BPM 2003, LNCS 2678, pp. 41–57, 2003.

Springer-Verlag Berlin Heidelberg 2003

42 S. Rinderle, M. Reichert, and P. Dadam

patient, and they usually aﬀect only single WF instances. As opposed to this, in

conjunction with schema changes at the WF type level, a collection of related

instances may have to be adapted. The challenging question is how to propagate

WF type changes to running WF instances, but without violating correctness

and consistency properties set out by the used WF meta model. In other words,

how can we smoothly migrate WF instances to a changed WF schema? Addi-

tionally, in case of concurrent changes (e.g., concurrent changes at the type and

instance level), the exciting question arises how to synchronize them (e.g., how

to propagate WF type changes to biased WF instances).

There is a multitude of approaches dealing with ﬂexibility in WfMS [1,2,4,5,

6,7,8]. All of them present very interesting, but partially strongly diﬀering ideas

and solutions. Therefore, it is an important job to summarize central criteria for

adaptive workﬂows and to compare actual approaches by using these criteria.

Furthermore, we sketch suitable solutions for ”still dangling” issues, e.g., related

to the problem of checking compliance of WF instances with a modiﬁed schema.

At ﬁrst, we summarize important criteria for diﬀerent change scenarios, which

are necessary to achieve a correct and consistent ”post-change”-behavior.

1. Completeness: The WF designer must not be restricted, neither by the

used WF meta model nor the oﬀered change operations. Therefore, a WF

meta model ought to provide a complete set of control and data ﬂow con-

structs, e.g., allow the designer to model sequences, parallel/alternative

branchings, and loops [3]. For practical purposes, at minimum, change opera-

tions for inserting and deleting activities as well as control/data dependencies

between them are required. Furthermore, it must be able to combine change

primitives to deﬁne complex changes, e.g., to modify the order of activities.

2. Correctness: The ultimate ambition of all adaptive WF meta models must

be correctness of dynamic changes [1,2,4,5,6,7,8]; i.e., introducing changes to

the runtime system without causing inconsistencies or errors (like deadlocks

or improperly invoked activity programs). Therefore, adequate correctness

criteria are needed. These criteria must not be too restrictive, i.e., no WF

instance should be needlessly excluded from applying a dynamic change.

Furthermore, it must be clear how the imposed correctness criteria can be

easily and quickly checked by the WfMS. This is especially important for

large-scale environments with hundreds up to thousands of WF instances.

3. Change Realization: Assuming that a dynamic change can be correctly

propagated to a WF instance I (along the stated correctness criteria), it

should be possible to automatically migrate I to the new schema. In this

context, the WF instance state as well as dependent data structures (e.g.,

user worklists) must be correctly and eﬃciently adapted.

In the following, we provide a classiﬁcation of actual approaches which is

based on the semantics of the underlying WF meta models and on the above cri-

teria. We point out where the strengths and weaknesses of these approaches lie.

To overcome current limitations we discuss solutions which can be easily trans-

ferred to other WF models (e.g., a comprehensive correctness criterion, eﬃcient

compliance checks, and formal propositions regarding concurrent changes).

Evaluation of Correctness Criteria for Dynamic Workﬂow Changes 43

In Section 2 we give an overview of current approaches dealing with ﬂexibility

in WfMS and classify them with respect to their semantics. Section 3 summarizes

and classiﬁes correctness criteria for adaptive workﬂows. In Section 4 we show

how the diﬀerent approaches realize dynamic WF changes. Section 5 presents a

critical discussion and Section 6 closes with a short summary.

2 Approaches Dealing with Flexibility

Figure 1 summarizes adaptive WF meta models which enable a ﬂexible pro-

cess support. According to [9], we classify those WF meta models according

to the evaluation strategies applied for executing WF instances during runtime.

The ﬁrst strategy uses only one type of (control ﬂow) token passing through each

WF instance (True-Tokens). The other strategy is based on two types of tokens –

True- and False-Tokens. True-Tokens represent activities that are to be executed

next and False-Tokens describe activities which have been skipped. Approaches

which solely use True-Tokens (cf. Fig. 2) have a True-Semantics and include, for

example, Petri-Net-based formalisms [2,5,10,1]. Approaches which, in addition,

use False-Tokens to represent skipped activities or skipped execution branches

can be found in the area of graph-based WF meta models [8,7]. They can be

further divided according to the way they represent the True- and False-Tokens.

One possibility is to gain these tokens (and therefore the state of running in-

stances) from execution histories [4], which log events like start and completion

of activity executions (cf. Fig. 3). Alternatively, special (model-inherent) mark-

ings of activities and/or control edges, which represent a consolidated view on

the history logs, can be used [6,7,8] (cf. Fig. 4).

2.1 Approaches with True-Semantics

In [2], a WF schema is represented by a WF Net which is a labeled

place/transition net N=(P,T,F,l) (cf. Fig. 2). Thereby, P denotes the set

of places, T the set of transitions, F⊆(T×P)∪(P×T) the set of directed

arcs, and lthe labeling function, which assigns a label to each transition. The

dynamic behavior of a WF instance is described by a marked WF net (N,s)

with marking (function) sand associated marking rules. The authors abstract

from data ﬂow issues, WF attributes and WF resources and consider only one

WF instance at a time.

The approach presented in [5,14,10] is based on Flow Nets, which are closely

related to WF nets. In Chautauqua [14], Flow Nets are generalized to Informa-

tion Control Networks (ICN). They allow the enactment of a new WF instance

by creating an instance speciﬁc token, which represents a data form of the en-

acted ICN. In doing so, data ﬂow is carried out by passing the token through

the ICN. WF instances (with same WF type) are distinguished by the use of

coloured tokens and are controlled by the same ICN. A meta language to support

dynamic evolution of processes is presented in [10]. In the following, however,

44 S. Rinderle, M. Reichert, and P. Dadam

Adaptive WF meta models

✘

✘✾



z

Models with

True-Semantics (→Sect. 2.1)

WF Nets [2]

Flow Nets [5,10]

MWMS/WF Net Models [1]

Models with True/False-Semantics (→Sect. 2.2)

✘

✘✾



z

Case1: Using History Logs

WIDE [4]

Case2: Model-Inherent Markings

WASA2[7]

ADEPT/WSM-Nets [8]

BREEZE [6]

Further: ROK [3], MOKASSIN [11], UltraFlow [12], TRAM [13]

Fig. 1. Selected Approaches Dealing With Flexibility Issues

we focus on the formalisms of Flow Nets as described above. An example for the

above approaches is depicted in Fig. 2a.

Another interesting approach is presented by MWMS [1]. The authors use

Net Models (NM), which are marked, acyclic Free-Choice Petri Nets. Data ﬂow

issues are not taken into account. A NM Σcan be mapped to a Sequential Model

(SM) Awhich represents the global states and state transitions of Σ. Thus, A

is comparable to the reachability graph of Petri Net Σ.

2.2 Approaches with True/False-Semantics

Case 1: Approaches based on History Logs

The most famous example and also one of the ﬁrst approaches dealing with dy-

namic WF changes was oﬀered by WIDE [4], which uses a graph-based WF meta

model. The modeling of sequential, parallel, alternative, and iterative activity

executions is possible. Furthermore, there is a set of global process variables

associated with each WF schema S. A WF instance I on WF schema S can be

described by S and by its execution history H=(S

I,0,µ

I,0,...,S

I,i,µ

I,i),

where S

I,k denotes the kth completion of a task execution in I and µS

I,i denotes

related write operations on WF variables performed by S

I,k.

In WIDE, WF schemata can be described either graphically or by using

predecessor and successor functions. Fig. 3 shows the latter variant.

Case 2: Approaches Using Model Inherent Markings

WASA2[7] introduces an object-oriented WF meta model. It comprises one

generic class Workﬂow of which WF schema and WF instance are instances.

Workﬂows are modeled by using a graph-based WF language comparable to

activity nets applied in IBM MQ Series Workﬂow. In more detail, a WF schema

S=(VS,C

S,D

S) is a tuple with sets of activity nodes VS, control connectors CS,

and data connectors DS. Similarly, a WF instance I can be described. The ﬂow

of data is modeled by data connectors which map output and input parameters

of subsequent activities. A WF schema S is correct iﬀ all input parameters are

correctly supplied by a type-conform output parameter and the graph structure

Evaluation of Correctness Criteria for Dynamic Workﬂow Changes 45

admit prepare

take blood lab test A lab test B validate

X-ray report

calc. dose &

give drug examine aftercare

admit prepare

take blood

lab test A

lab test B

validate

X-ray report

calc. dose &

give drug examine aftercare

ultrasonic

old change region

lab test A lab test B SCOC

for parallelization of labTestA

and labTestB (upsizing)

(with flow jumpers j1, j2, j3 and silent

transition λ)

Projection-inheritance-preserving

transformation rule

inform

j1 j

2 j

new change

region

flow jumpers

insertion of activity ultrasonic

N1 change1

change2

Fig. 2. A Petri-Net-Based Workﬂow With Changes ([2,5,10])

is acyclic (i.e., no deadlocks will occur). The state of a WF instance is denoted

by the marking of the instance nodes (model-inherent).

Another approach with model-inherent markings is based on Well-Structured

Marking-Nets (WSM-Nets) as applied in our ADEPT WfMS [8], for example.

WSM-Nets are serial-parallel graphs with distinguishable node and edge types,

where loops and branchings are modeled in a block-oriented fashion (block struc-

ture). This structure is relaxed by oﬀering sync edges, which allow to deﬁne

precedence relations between activities of parallel branches. We ﬁrst provide two

self-explanatory deﬁnitions for WSM-Nets (cf. Def. 1) and for WF instances (cf.

Def. 2) based on them.

Deﬁnition 1 (Well-Structured Marking-Net, WSM-Nets). A tuple

S = (N, D, NT, CtrlE, SyncE, LoopE, DataE, EC) is called a Well-Structured

Marking-Net if the following holds:

–N is a set of activities and D a set of process data elements

–NT: N → {StartFlow, EndFlow, Activity, AndSplit, AndJoin,

XOrSplit, XOrJoin, StartLoop, EndLoop}

–CtrlE ⊂N×N is a precedence relation

–SyncE ⊂N×N is a precedence relation between activities of parallel executed

branches

–LoopE ⊂N×N is a set of loop backward edges

–DataE ⊆N×D×{read, write}is a set of read/write data links between

activities and data elements

–EC: CtrlE ∪SyncE ∪LoopE → Predicates(D) where Predicates(D) de-

notes the set of all valid transition conditions on data elements from D.

46 S. Rinderle, M. Reichert, and P. Dadam

Fig. 3. WF Instance Including History Logs in WIDE

A WSM-Net is correct iﬀ

•Sfwd = (N, CtrlE, SyncE) is an acyclic graph, i.e., the use of sync edges must

not cause undesired cycles leading to deadlocks (for details see [8]),

•for each split (loop start) node there is a unique join (loop end) node, and

•S is structured following a block concept, for which control blocks (sequences,

branchings, loops) can be nested but must not overlap.

Deﬁnition 2 (WF Instance Based On WSM-Nets). A WF instance I is

deﬁned by a tuple (S, MS,Val

S,H) where

–S = (N, D, NT, CtrlE, SyncE, ...) denotes the WSM-Net the execution of I

is based on.

–MS= (NSS,ES

S) describes node and edge markings of I:

NSS:N→ {NotActivated, Activated, Running, Completed, Skipped}

ESS: (CtrlE ∪SyncE ∪LoopE) → {TrueSignaled, FalseSignaled}

–ValSis a function on D. It reﬂects for each data element d ∈D either its

current value or the value UNDEFINED (if d has not been written yet).

–H=<e

0,...,e

k>is the execution history of I. e0,...,e

kdenote the start

and end events of activity executions. For each started activity X the values

of data elements read by X and for each completed activity Y the values of

data elements written by Y are logged.

Activities marked as Activated are ready to ﬁre and can then be worked on,

i.e., their status changes to Running. Activities with marking Skipped cannot

longer be selected for execution. An example of a WF instance based on a WSM-

Net is shown in Fig. 4. Another approach using WF graphs similar to WSM-Nets

but without loops is oﬀered by BREEZE [6].

3 Correctness Criteria for Dynamic WF Changes

We ﬁrst focus on WF schema changes at the type level and their propagation

to running WF instances. Regarding correctness, however, it is not important

Evaluation of Correctness Criteria for Dynamic Workﬂow Changes 47

admit

prepare

takeblood

StartLoop Activity AndSplit labTestA labTestB validate

xRay report

calc. dose&

give drug examine

EndLoop

aftercare

AndJoin

bloodVal XRay patientData

LoopE

CtrlEdge

DataE:

d=(examine, patientData, write)

DataElement

NS = Activated NS = Running ES = TrueSignaled

NS = Completed ES = FalseSignaled

a) WF Instance On WSMN

b) Changes

= ( insertActivity(ultraSonic, xRay, report), insertDataElement(ultrasonic),

insertDataEdge(ultrasonic, ultrasonic, write),

insertDataEdge(ultrasonic, report, read) )

c) Reduced Execution History

Start(admit), End(admit), Start(StartLoop, it=2), End(StartLoop), Start(prepare), End(prepare), Start(takeblood), End(takeblood),

Start(labTestA), Start(xRay), End(labTestA^bloodVal.resultA=4.3), Start(labTestB), End(xRay^xRay=xRay256(2).jpg

2nd iteration:

Fig. 4. A (Clinical) WF Instance Based On WSM-Nets

whether a WF type (and therefore a collection of running instances) or a single

WF instance is aﬀected by a change. At the end of this section we provide a

correctness criterion to handle concurrent changes at the type and the instance

level (i.e., to correctly propagate WF type changes to biased WF instances).

In the following, we assume that a WF schema S is always correctly trans-

formed into another schema S’ by applying change ∆. What this exactly means

depends on the structural and dynamic correctness properties set out by the used

WF meta model. We focus on the discussion how the approaches from Section

2 decide whether an instance I can be correctly migrated to a changed schema

S’ or not. It is remarkable that all discussed solutions are based on formal cor-

rectness criteria. While some of these approaches precisely state how to ensure

correctness in conjunction with dynamic WF changes, others do not address this

point in detail.

We further distinguish between approaches founding their correctness cri-

teria on graph equivalence –WF Nets [2], MWMS [1], and WASA2[7] – and

approaches with correctness criteria based on execution equivalence –Flow Nets

[5,10], WIDE Nets [4],

and ADEPT WSM-Nets [8]. The core idea of graph equivalence is to map

the WF instance graph of I to the changed WF schema S’. Depending on the

”degree of coverage” it can be decided whether ∆is applicable to I as well.

Execution equivalence focuses on the work done by I so far. If this work could

have been achieved on S’ as well, I can be smoothly migrated to S’. Note that

both approaches are closely related to each other.

3.1 Approaches Based on Graph Equivalence

WF Nets: A ﬁrst representative based on graph equivalence (see above) is de-

scribed in [2]. The authors use branching bisimilarity as an equivalence relation

on marked, labeled P/T-Nets (cf. Section 2). It speciﬁes under which conditions

two diﬀerent marked, labeled P/T-Nets S and S’ have the same (observable)

behavior (notation: S∼bS⇐⇒ ∃ branching bisimulation Rsuch that SRS).

48 S. Rinderle, M. Reichert, and P. Dadam

Informally, a marked, labeled P/T-Net must be able to simulate each action of

an equivalent marked net.

Correctness-Criterion 1 (Branching Bisimilarity) Let S be a marked, la-

beled WF Net and ∆be a change which transforms S into another marked, labeled

WF Net S’. Then: ∆can be carried out correctly iﬀ S∼bS.

Generally, it is diﬃcult to ensure Criterion 1 for arbitrary changes. Therefore

the authors restrict the set of possible change operations to those which preserve

special inheritance relations between the old and the new net (e.g., insertion of

activity ultrasonic in Fig. 2b). If these inheritance relations hold after applying

a change, branching bisimilarity between both nets can be ensured. Inheritance-

ensuring change operations are:

•adding sequences as well as parallel, alternative and iterative branches

(direction of inheritance from class to subclass) and

•removing sequences as well as parallel, alternative and iterative branches

(direction of inheritance from class to superclass).

Unfortunately, branching bisimilarity cannot be automatically ensured for

other change operations [2]. The reason for this is a phenomenon called dynamic

change bug. Examples for non-supported operations are order-changing opera-

tions like parallelizing transitions labTestA and labTestB in Fig. 2a. Excluding

those change operations, however, leads to serious problems since related forward

and backward jumps have to be frequently applied in practice.

In MWMS [1] a set of change operations (parallelization, sequentialization

and swapping of activities) is proposed obeying special constraints (summarized

by the Minimal Critical Speciﬁcation (MCS) for the underlying SM). Intuitively,

only such change operations can be carried out which maintain the given set of

activities and which only change their order relations. For these changes the

following correctness criterion is provided:

Correctness-Criterion 2 (Safe States) Let A=(S, E, T, sin)beaSMand

∆be a change operation (within the respective MCS). ∆transforms Ainto

another SM A=(S,E,T,s



in). Then an instance I on Acan be migrated

to Aiﬀ I is not in an unsafe state. A state of Ais unsafe iﬀ there is no

corresponding state in S’

Another approach using graph equivalence is oﬀered by WASA2[7]. The

author does not explicitly state which changes can be applied. Exemplarily,

operations like adding and deleting activities or changing activity orders are

provided. The decision whether a change ∆can be applied to an in-progress WF

instance or not is based on a valid mapping of the purged WF instance graph

to the WF schema graph. Thereby, the purged WF instance graph is gained

by deleting all activities which have not been started yet, and by removing all

associated control and data connectors (cf. Fig. 5b). A mapping m:VI→ VS

between a WF instance I=(VI,C

I,D

I) and a WF schema S=(VS,C

S,D

S)

is deﬁned as follows:

Evaluation of Correctness Criteria for Dynamic Workﬂow Changes 49

A1S A2S A3S A4S

A1S

A2S

A3S A4S

’

’ c3

’

’d2

’

a) WF schema S: WF schema S’:

parallelization of

activities A2S and A3S

A1I A2I

c1I

b) purged WF instance

h I

(

on S

)

: c) valid mapping m*: I Æ S’ with

m*(A1I) = A1S’, m*(A2I) = A2S’

m*(c1I) = c1S’, m*(d1I) = d1S’

Fig. 5. Valid mapping in WASA2

∀j∈VI:∃j∈VSwith [m(j’) = j ⇒SchemaOf(j’) = j (i.e., j’ is based on j)]

∧[m(j’) = m(k’) ⇒j=k∀j,k

∈VI]

With this, the following correctness criterion based on valid mappings be-

tween WF instance graph and WF schema graph can be stated:

Correctness-Criterion 3 (Valid Mapping) Let I=(VI,C

I,D

I)be a purged

WF instance graph derived from WF schema S. Then: Change ∆can be correctly

applied to Ias well iﬀ ∃a valid mapping m*: VI→ V

S. A mapping m* is valid

if all control connectors between two instance objects i, j ∈VIhave counterparts

i’, j’ ∈VSwith SchemaOf(i) = i’ and SchemaOf(j) = j’ and ∀d∈DI∃d’ ∈DS

(and vice versa).

Intuitively, an instance I can be migrated to a changed WF schema S’ if

each completed activity of I is also contained in S’ and all control and data

dependencies existing in I have counterparts in S’ (cf. Fig. 5c).

To our knowledge no statements have been published so far, how Criterion 3

can be (eﬃciently) checked. However, an implementation of WASA2exists [7].

3.2 Approaches Based on Execution Equivalence

Flow Nets: A ﬁrst approach based on execution equivalence has been presented

in [5,10] (details of the used Flow Nets have been given in Section 2.1). In [5],

changes of a Flow Net S(with True-Semantics) are carried out by substituting

the marked sub-net N1of S, which is aﬀected by ∆, by another marked sub-net

N2, which reﬂects the modiﬁcations set out by ∆. Thereby, N1is referred to as

the old change region and N2as new change region. As the authors point out, the

selection of the change regions cannot be ﬁxed. Roughly, the old change region

is deﬁned as the smallest marked sub-net containing all activities aﬀected by ∆.

Assume, for example, that in Fig. 2a) change operation ∆is to parallelize the

so far sequentially ordered activities LabTestA and LabTestB. Then N1is the

sub-net containing the aﬀected activities LabTestA and LabTestB. To be able to

decide whether ∆can be correctly propagated to an instance or not the authors

introduce the pre-change (ﬁring) sequence ωto conceptualize the work done by

the WF instance so far. Thereby, ωdenotes all transition ﬁrings previous to

the introduction of ∆. Based on this, the following correctness criterion can be

formulated:

50 S. Rinderle, M. Reichert, and P. Dadam

Correctness-Criterion 4 (Pre-Change sequence ω)Let ∆be a change,

which transforms Flow Net Sinto Flow Net S. Let further be I an instance

on S with pre-change sequence ω. Then I can be migrated to S’ iﬀ ωcan be

continued on S’ as well.

In order to check whether Criterion 4 is met, the authors present two kinds of

change operations and a special change class, the so called Synthetic Cut-Over

Change (SCOC). Applying SCOC, the old change region N1is maintained in S

together with N2(for an example see Fig. 2b); i.e., S’ contains two versions of

the modiﬁed subnet. How this ”fusion” of old and new change region is carried

out depends on the applied change. In [5] two change scenarios – Upsizing and

Downsizing – are introduced. Upsizing means that N2can ”do more” than N1,

i.e., the set of all valid ﬁring sequences on N1is a subset of all valid ﬁring

sequences on N2. Downsizing is the dual counterpart of upsizing, i.e., N2can

”do less” than N1. For example, Fig. 2b shows an upsizing. In this case, the

SCOC can be constructed by sticking N1and N2together over ﬂow-jumpers

(cf. Fig. 2b). Flow-jumpers are transitions, which map each marking of N1to a

marking of N2. This way of constructing the SCOC in conjunction with upsizing

operations is correct regarding Criterion 4. In the other case – downsizing – the

SCOC is constructed by merging N1and N2over one output place, i.e., instances

with tokens in N1are further executed according to the old net. Trivially, this

restrictive approach is also correct regarding Criterion 4. Other important change

operations, like the insertion of new activities, are not discussed. Very interesting

is that upsizing and downsizing are excluded by [2] since these changes lead to

the dynamic change bug (cf. Section 3.1).

A widely-used correctness property is the compliance criterion introduced by

WIDE [4]. Intuitively, change ∆of WF schema S can be correctly propagated

to a WF instance I iﬀ the execution of I, taken place so far, can be ”simulated”

on the modiﬁed WF schema S’ as well. Note that Criterion 5 is similar to Cri-

terion 4 at ﬁrst glance. But Criterion 4 is only based on a snapshot of the WF

execution whereas Criterion 5 takes the whole WF execution into account. Since

the authors work with a history-based execution model, compliance is based on

replaying the execution history Hof WF instance I on the changed WF schema

S’. Formally:

Correctness-Criterion 5 (Intuitive Compliance Criterion) Let S be a

WF schema and I be a WF instance on S with execution history H. Let fur-

ther S be transformed into another schema S’ by change operation ∆. Then:

I is compliant with S’ iﬀ Hcan be produced on S’ as well.

Assume that in WF schema S in Fig. 3 task aftercare is to be deleted. Re-

ferring to execution history Hof WF instance I (cf. Fig. 3) the intended deletion

is possible since Hcontains no entry related to aftercare and can therefore be

(re-)produced on the changed WF schema as well. As opposed to this, the inser-

tion of a new task ultrasonic between tasks xRay and report is not possible

regarding Criterion 5. The reason is that activity ultrasonic has not written

Evaluation of Correctness Criteria for Dynamic Workﬂow Changes 51

any entries into Hduring the ﬁrst loop iteration (note that the loop is actually

in its 2nd iteration). Inserting ultrasonic in the actual loop iteration, how-

ever, would cause no inconsistencies or errors at runtime (irrespective of (rare)

roll-back operations into former loop iterations which become more expensive).

Consequently, Criterion 5 is too restrictive, especially in conjunction with iter-

ative, long-running workﬂows. Since in [4] no further information about how to

check Criterion 5 is given, we assume that compliance is ensured by trying to

replay the whole execution history on the changed WF schema. Doing so causes

a big overhead due to the possibly extensive volume of the history (caused by

information like user assignments or time stamps).

WSM-Nets: In ADEPT [8], we focus on ﬁnding a correctness criterion which

works in conjunction with loops as well as other orthogonal aspects (e.g., data

ﬂow). The key to solution with respect to loops is to be able to diﬀerentiate

between completed and future executions of loop iterations. From a formal point

of view there are two possible approaches. One approach is to logically treat

loop structures as being equivalent to respective linear sequences. The other

approach is to maintain the loop construct but to restrict the evaluation to

the relevant parts of the execution history (cf. Def. 3). We adope the second

approach since it facilitates the treatment of nested loops, provides a good basis

for implementation, and leads to ”smart” proofs.

Deﬁnition 3 (Reduced Execution History Hred). Let I be a WF instance

with execution history H. The reduced execution history Hred is obtained as

follows: In the absence of loops Hred is identical to H. Otherwise, it is derived

from Hby discarding all history entries related to other loop iterations than the

last one (completed loop) or the actual iteration (running loop). (Note that Hred

can be easily produced in conjunction with nested loops as well.)

As an example take Fig. 4c, which shows the reduced execution history for

the instance from Fig. 4a. Taking Def. 3 we now present a comprehensive compli-

ance criterion for WF schema evolution. According to this property, an instance

is compliant with a changed schema iﬀ the reduced execution history can be

produced on the modiﬁed schema as well.

Correctness-Criterion 6 (Comprehensive Compliance Criterion) Let I

be a WF instance on WF schema S with execution history Hand reduced execu-

tion history Hred. Assume further that a change ∆transforms S into the correct

WF schema S’. Then I is said to be compliant with S’ iﬀ Hred can be produced

on S’ as well.

Again, the challenging question is how to eﬃciently check the comprehensive

compliance criterion. We present easily and quickly checkable marking conditions

for each kind of change on WSM-Nets [8] (additive, subtractive, order-changing,

and complex operations). Due to lack of space, we exemplarily summarize these

conditions for additive change operations in Theorem 1.

Theorem 1 (Additive Change Operations On WSM-Nets). LetS=(N,

D, ...) be a correct WSM-Net and I be a WF instance on S with execution history

52 S. Rinderle, M. Reichert, and P. Dadam

Hred. Assume further that change ∆transforms S into correct WSM-Net S’ =

(N’, D’, ...).

(a) ∆inserts an activity ninsert (with associated control and sync edges) into S.

Then:

I is compliant with S’ ⇔

∀n∈{x∈N|ninsert →x∈E’}: NS(n) ∈{NotActivated, Activated,

Skipped}∨

ninsert is inserted into an already skipped branch of an XOr-branching

(b) ∆inserts a control edge nsrc →ndest into S. Then:

I is compliant with S’ ⇔NS(ndest)∈{NotActivated, Activated,

Skipped}

far). Then:

I is compliant with S’ ⇔

[NS(ndest)∈{NotActivated, Activated, Skipped}]∨

[NS(nsrc)=Completed ∧NS(ndest)∈{Running, Completed}with

∃ei=END(nsrc),ej=START(ndest)∈H

red ∧i<j))]∨

[NS(nsrc)=Skipped ∧NS(ndest)∈

{Running, Completed}) with

∀n∈Ncritical with NS(n) =Skipped:

∃ei=START(ndest),ej=END(n) ∈H

red with j<i),

where Ncritical =(cpred∗(S, nsrc)¬cpred∗(S, ndest))

and c pred∗(S, n)) denotes all direct/indirect predecessors of n in S con-

cerning

edges ∈CtrlE ]

For additive change operations, Theorem 1 presents precise conditions for

eﬃcient compliance checks with an estimated complexity of O(n). These condi-

tions base on a consolidated view of the reduced execution history Hred.Asan

example take the insertion of activity ultrasonic as deﬁned by change ∆in Fig.

4b. According to Theorem 1(a) it is only necessary to determine the marking of

the successors of ultrasonic in S’. In our example, activity report is marked

as Activated such that ∆can be applied to the WF instance depicted in Fig.

4a. To show their eﬃciency we have implemented several simulations checking

our compliance conditions.

Besides, we explicitly deal with compliance issues in conjunction with data

ﬂow changes. We shortly summarize the basic ideas: Data elements can be always

inserted, but must not be deleted if there was a read or write access on them.

Read data edges eread =(n, d, read) on data element d can only be inserted

or deleted iﬀ activity n is marked as NotActivated, Activated or Skipped.

Write data edges ewrite =(n, d, write) on data element d can only be inserted

or deleted iﬀ activity n has not been completed yet.

3.3 Concurrent Type and Instance Changes

Finally, we want to give an idea how the propagation of WF schema changes to

biased WF instances can be managed correctly in the context of WSM-Nets [8].

Evaluation of Correctness Criteria for Dynamic Workﬂow Changes 53

But it should be clear that the following conclusions are applicable to other WF

meta models as well. To meet a formal point of view, we ﬁrst give a deﬁnition

of a biased WF instance (compare Def. 1 and 2).

Deﬁnition 4 (Biased WF Instance). A biased instance I is described by a

tuple (S, ∆I,M

S+∆I,Val

S+∆I,H), where S denotes the WSM-Net from which

I was created and ∆Icomprises ad-hoc changes op1

I,...,op

Ithat have been

applied to I so far. WSM-Net SI:= S + ∆I, which results from the application

of ∆Ito S, is called execution schema of I.

Comparable to the already discussed correctness criteria we introduce a gen-

eral criterion that allows us to argue about both – propagation of WF schema

changes on ”normal” (unbiased) and on biased WF instances. Obviously, when

propagating a WF schema change ∆Sto a biased WF instance I we must not

only consider its current state (i.e., marking MS+∆I) but we also have to cope

with structural and semantic conﬂicts that may exist between the concurrent

changes ∆Iand ∆S. (Note that both, ∆Iand ∆Shave been based on S.) Due

to lack of space we only consider structural conﬂicts in the following.

Correctness-Criterion 7 (Concurrent Changes) Let S be a correct WSM-

Net and I = (S, ∆I,M

S+∆I, ...) be a biased WF instance that was created from

S. Let further ∆Sbe a change operation, which transforms S into another correct

WSM-Net S’. Then: ∆Smay be propagated to biased WF instance I :⇔

1. S* = (S + ∆I)+∆Sis a correct WSM-Net, i.e., ∆Scan be correctly applied

to the execution schema SI=(S+∆I).

2. I is compliant with S*; i.e., the reduced execution history Hred canbepro-

duced on S* as well. The marking MS∗resulting from this is considered as

a correct marking.

Again, the challenging question is how to eﬃciently verify the conditions set

out by Criterion 7. A naive solution would be to ﬁrst generate the WSM-Net

SI+∆Sand then to check whether it satisﬁes the required structural and dy-

namic properties. Generally, this would be too expensive, in particular if diﬀerent

WF aspects (control ﬂow, data ﬂow, work assignments, etc.) are concerned or

∆Sis to be propagated to a large collection of instances. Instead we must deﬁne

appropriate and eﬃcient rules for excluding potential conﬂicts (e.g., undesired

cycles and deadlocks) between instance and type changes for as many instances

as possible. Due to lack of space we abstain from further details.

4 Change Realization

We have now reached the stage of checking compliance of WF instances with

a changed WF schema. This analysis leads to two instance categories – com-

pliant and non-compliant WF instances [4,6]. We ﬁrst discuss how the diﬀer-

ent approaches concretely carry out the migration of compliant WF instances

54 S. Rinderle, M. Reichert, and P. Dadam

(instance adaptations). Then a short overview about approaches dealing with

non-compliant WF instances is presented.

Approaches With True-Semantics: For Petri-Net based approaches, in-

stance migration means to ﬁnd a suitable marking on the changed net.

WF Nets: In [2], for each imposed change operation transfer rules are deﬁned,

which automatically adapt net markings. Concerning the insertion of sequences

and alternative branches, the respective transfer rule maps marking sof the old

net S to the identical marking on the new net S’ (transfer rule is identity function

id :(S, s)→ (S,s)). As an example take the markings of the net in Fig. 2 before

and after insertion of transition ultrasonic. For other change operations the

insertion of additional tokens becomes necessary. Examples are changes like the

insertion of new parallel branches or the deletion of alternative branches and

sequences which contain tokens. Due to lack of space we abstain from discussing

further transfer rules.

Flow Nets: For the change operations provided by [5,10], trivially, markings

are adapted by constructing the SCOC (cf. Section 3.2). Note that the schema

resulting from a SCOC always contains the marking of the old net.

Approaches With True/False-Semantics: To our knowledge neither

WASA2[7] nor WIDE [4] provide detailed information about marking adap-

tations. In WIDE, however, follow-up markings may result from the replay of

the execution history. As mentioned in Section 3.2, doing so is very expensive

since execution histories often contain extensive data.

WSM-Nets: Our ADEPT approach is somewhat diﬀerent regarding mark-

ing adaptations of compliant instances. To keep these adaptations eﬃcient, we

restrict them to those nodes and edges of the respective execution schema SI,

which constitute the context of the change region. Therefore, for each change

operation op initial sets of nodes end edges to be re-evaluated are determined.

Depending on the result of the evaluation the inspection of additional nodes and

edges may become necessary. In addition, we beneﬁt from well-deﬁned mark-

ing rules as well as the way markings are represented (preserving markings of

passed regions, True/False semantics). As an example take change ∆in Fig.

4. In the course of the following adaptation, ultrasonic has to be marked as

Activated and marking of report is re-evaluated to NotActivated. Finally,

an algorithm has been formulated, which evaluates instance markings with an

estimated complexity of O(n).

Dealing With Non-Compliant WF Instances: There are several approaches

dealing with (temporarily) non-compliant instances [5,6]. BREEZE [6] provides

a special graph construct which consists of compensation activities. With this,

non-compliant instances are partially rolled back into a compliant state. The

ﬁrst approach which gives an idea of delayed migration is presented in the area

of Flow Nets [5]. As an example consider Fig. 2. Even if the given instance

passes through the old change region, a delayed migration to the new change

region is possible when another loop iteration takes place. We have adopted this

concept and suggest to keep such (temporary) non compliant instances pending

to migrate.

Evaluation of Correctness Criteria for Dynamic Workﬂow Changes 55

5 Discussion

WF Nets: In [2], a wide range of change operations is covered and provided with

correctness criteria and (automatic) transfer rules for adapting markings. In case

of selected change operations (e.g., adding new parallel branches) new tokens

can be automatically created when migrating instances. Though the authors

completely abstract from data ﬂow, for practical purposes it is necessary that

tokens carry data ﬂow information as well. Therefore, the semantics of newly

inserted tokens at runtime is not always clear.

Flow Nets: [5,10] introduce a special class of changes, the described SCOC

(cf. Section 3.2). Trivially, applying SCOC changes, marking adaptations are

always correctly performed since the old change region is completely contained

in the new net. For a special kind of changes – upsizing – the states of the old

change region are mapped to states of the new change region by ﬂow-jumpers (cf.

Fig. 2b). [10] suggest to determine these ﬂow jumpers manually which implies a

very experienced WF designer. A very nice idea is oﬀered by delayed migrations,

i.e., the possibility of (temporarily) non-compliant instances to later migrate to

the changes schema, e.g., when a loop back takes place. This approach gets even

more complex when data ﬂow issues are to be taken into account as well.

In MWMS [1] a special class of change operations is oﬀered which provides

correct migration of instances in safe states. Both the imposed WF model and

the oﬀered change operations are strongly restricted. To our knowledge, there

is no detailed discussion about how to check the provided correctness criterion

and how to adapt markings after instance migrations.

WASA2[7] suggests valid mappings between the purged WF instance graph

and the changed WF schema in order to preserve correctness. Though [7] presents

an implementation there is no detailed conceptualization of the mentioned valid

mappings. In WASA2the loop problem is not present since only acyclic WF

graphs are allowed. However, WASA2is one of the few approaches, which beneﬁts

from a concrete implementation of a powerful WF engine.

WIDE [4] has oﬀered a cornerstone for many other approaches – the intuitive

compliance criterion. Unfortunately, this criterion suﬀers from its restrictions

concerning loops (cf. Section 3). Furthermore, it is not clear how the given cri-

terion can be checked and implemented. If we had assumed that replaying the

whole execution history is necessary this could not be eﬃciently realized. Gen-

erally, execution history logs are not captured in primary storage and contain

extensive information like work assignments, time stamps, etc.

All discussed approaches – except our ADEPT approach – do not explicitly

deal with data ﬂow aspects. Furthermore, one of the few approaches to care

about orthogonal aspects in conjunction with dynamic WF changes is oﬀered by

BREEZE [6]. Here, WF schema evolution in conjunction with time management

is discussed. As already mentioned concurrent changes have been adressed only

in the area of our ADEPT WSM-Nets so far.

Table 1 compares the discussed approaches along the stated criteria.

56 S. Rinderle, M. Reichert, and P. Dadam

Table 1. A Comparison Of The Discussed Approaches

WF Nets Flow Nets MWMS WASA2WIDE ADEPT

Completeness of

•WF Model – ◦––++

•Changes – + – + + +

•Correctness Criteria + + + + – +

Checking Compliance + – – – – +

Change Realization + – ? ? + +

Available Implementation ? + ? + ? +

6 Summary and Outlook

In this paper we have compared actual approaches dealing with adaptive work-

ﬂows along fundamental criteria. Thereby the main focus lies on providing cor-

rectness criteria to decide whether a WF instance can be smoothly migrated to a

changed WF schema or not. In many applications, the question how to eﬃciently

check these criteria, how to accomplish instance migrations, how to implement

the presented concepts, and how to oﬀer change facilities to users remains unan-

swered. Therefore, we have presented simple state conditions for compliance

checks and a nice solution to adapt instance markings after change propaga-

tion. Furthermore, we have discussed issues regarding concurrent changes. We

strictly encourage other research groups to deal with this exciting problem as

well and to provide implementations of their concepts within a powerful WF

engine. There are many other interesting questions mainly concerning imple-

mentation of the presented concepts. Within this, questions related to change

authorization, change analyses, and usability have to be carefully answered.

References

1. Agostini, A., De Michelis, G.: Improving ﬂexibility of workﬂow management sys-

tems. In: Proc. BPM ’2000. LNCS 1806, Springer (2000) 218–234

2. van der Aalst, W., Basten, T.: Inheritance of workﬂows: An approach to tackling

problems related to change. Theoretical Computer Science 270 (2002) 125–203

3. Edmond, D., ter Hofstede, A.: A reﬂective infrastructure for workﬂow adaptability.

Data and Knowledge Engineering 34 (2000) 271–304

4. Casati, F., Ceri, S., Pernici, B., Pozzi, G.: Workﬂow evolution. Data and Knowledge

Engineering 24 (1998) 211–238

5. Ellis, C., Keddara, K., Rozenberg, G.: Dynamic change within workﬂow systems.

In: Proc. Int’l Conf. on Org. Comp. Sys. (COOCS ’95), Milpitas, CA (1995) 10–21

6. Sadiq, S., Marjanovic, O., Orlowska, M.: Managing change and time in dynamic

workﬂow processes. Int’l J Coop IS 9(2000)

7. Weske, M.: Formal foundation and conceptual design of dynamic adaptations in a

workﬂow management system. In: Proc. 34th Hawaii Int’l Conf. on System Sciences

(HICSS-34). (2001)

Evaluation of Correctness Criteria for Dynamic Workﬂow Changes 57

8. Reichert, M., Dadam, P.: ADEPTf lex - supporting dynamic changes of workﬂows

without losing control. Journal of Intelligent Inf. Systems 10 (1998) 93–129

9. Kiepuszewski, B., ter Hofstede, A., Bussler, C.: On structured workﬂow modelling.

In: Proc. CAiSE ’00. LNCS 1789, Springer (2000) 431–445

10. Ellis, C., Keddara, K.: A workﬂow change is a workﬂow. In: Proc. BPM 2000.

Volume 1806 of LNCS., Springer (2000) 516–534

11. Joeris, G., Herzog, O.: Managing evolving workﬂow speciﬁcations. In: Proc. Int’l

Conf. on Coop. Inf. Systems (CoopIS ’98), New York City (1998) 310–321

12. Fent, A., Reiter, H., Freitag, B.: Design for change: Evolving workﬂow speciﬁcations

in ULTRAﬂow. In: Proc. CAiSE ’02. (2002) 516–534

13. Kradolfer, M., Geppert, A.: Dynamic workﬂow schema evolution based on workﬂow

type versioning and workﬂow migration. In: Proc. CoopIS ’99, Edinburgh (1999)

104–114

14. Ellis, C., Maltzahn, C.: The Chautauqua workﬂow system. In: Proc. 30th Int’l

Conf. on System Science, Maui (1997)