On Dealing with Structural Conflicts between Process Type and Instance Changes [original]

On Dealing with Structural Conﬂicts between

Process Type and Instance 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. Adaptive process management systems must be able to sup-

port changes of single process instances as well as modiﬁcations at the

process type level and their propagation to a collection of related pro-

cess instances. So far, these two kinds of dynamic process changes have

been mainly considered in an isolated manner. However, especially for

long-running processes, it must be possible to handle the interplay bet-

ween process type and instance changes as well, but without running into

trouble at runtime. This paper presents an extended criterion for correc-

tly propagating process type changes to both, instances which are still

running according to their original schema and instances which have been

individually modiﬁed. In this context, we discuss and categorize struc-

tural conﬂicts potentially occuring between concurrent process changes.

We show that our considerations are applicable to diﬀerent process meta

models and present tests for quickly detecting such structural conﬂicts.

1 Introduction

Adaptivity in process management systems (PMS) is key to ﬂexible enterprise

information systems. Basically, changes in process-oriented applications can take

place at two levels – the process type or the process instance level.

Aprocess type represents a particular business process (e.g., handling of a

purchase order or treatment of a patient). It is described by a process schema

which deﬁnes a collection of activities and sets out the control as well as data

ﬂow between them. Based on such a process schema, new process instances can

be created and executed according to the deﬁned process logic. Process type

changes become necessary, for example, to adapt the process-oriented informa-

tion system to optimized business processes or to new laws. They are handled

by (structurally) modifying the respective process schema, which leads to a new

schema version of the respective type. Particularly for long-running processes

(e.g., handling of leasing contracts or medical treatments) it is desired to propa-

gate a process type change to already running process instances as well. Process

instances for which this is possible are compliant with the new schema and can

therefore be migrated to it. As opposed to process type changes, changes of

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

workﬂow systems”, which is funded by the German Research Community (DFG).

J. Desel, B. Pernici, and M. Weske (Eds.): BPM 2004, LNCS 3080, pp. 274–289, 2004.

Springer-Verlag Berlin Heidelberg 2004

On Dealing with Structural Conﬂicts 275

single process instances (e.g., to insert or skip an activity) are often carried out

in an ad-hoc manner in order to deal with an exceptional situation. Adapting

a single process instance during runtime, in turn, results in an instance-speciﬁc

schema (also called instance execution schema in the following), which diﬀers

from the original schema this instance was created from. In the following, we

denote such individually modiﬁed process instances as biased.

In the literature [1,2,3,4,5,6,7,8,9,10] process type and instance changes have

been an important research topic for several years. However, there are only few

adaptive PMS which support both kinds of changes in one system [10,11]. All of

them have in common that once an instance has been individually modiﬁed (i.e.,

it possesses an instance-speciﬁc process schema), it cannot longer beneﬁt from

process type changes; i.e., changes of the schema they were originally created

from. In WASA2[10], for example, an instance change is carried out by deriving

a new schema version to which the instance is migrated. In the sequence, this

instance is excluded from further adaptations of its original schema version at the

process type level. However, doing so is not suﬃcient in many cases, especially

in connection with long-running processes. Therefore, it must be possible to

propagate process schema changes at the type level to such biased instances as

well.

This paper focuses on the interplay of process type and instance changes un-

der appropriate correctness constraints. Such constraints are necessary since an

uncontrolled propagation of process type changes to biased instances may raise

severe errors at runtime. A ﬁrst contribution is to present a correctness crite-

rion for propagating process type changes to both unbiased and biased process

instances. This criterion is independent of the used process meta model. Furt-

hermore, it excludes state-related,structural, and semantical conﬂicts between

concurrent process type and instance changes. A second contribution deals with

structural correctness of concurrent process type and instance changes. A

simple example for such a structural conﬂict is depicted in Fig. 1. Here, propaga-

ting the process type change (cf. Fig. 1a) to biased instance Iin an uncontrolled

manner would lead to a deadlock causing cycle in the resulting process instance

schema (cf. Fig. 1b). A naive solution to overcome this undesired behavior would

be to simulate the process type change on each instance-speciﬁc schema (i.e., to

materialize the resulting instance schema) and then to verify control and data

ﬂow correctness. Doing so may become very critical regarding performance, es-

pecially in conjunction with a large number of biased instances. An alternative

solution is to check for process schema and instance changes whether they are

in conﬂict or not. Our ambition is to exclude structural conﬂicts for as much

(biased) instances as possible by the use of simple and easy to check tests. In

any case expensive control and data ﬂow analyses shall be avoided to a large

degree. This paper presents appropriate tests to detect control ﬂow as well as

data ﬂow conﬂicts between process schema and instance changes.

In Section 2, a general correctness criterion handling both process type and

instance changes is introduced. Section 3 provides necessary background infor-

mation for our concrete solution approach. In Section 4 we present structural

conﬂict tests which are illustrated by an example in Section 5. Section 6 discusses

related work and Section 7 closes with a summary of the presented results.

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

Schema S’:

A B

E F

b) Biased Instance I (on S + 'I): I (on (S + 'I) + 'T):

'T = insertPlace(S, D, E)

process type change

A B

E F

H G

A B

E F

H G

A B

E F

H G

a) Schema S:

'I = insertPlace(S, F, C)

Fig. 1. Structural Conﬂict in Petri Nets (Deadlock)

2 A General Correctness Criterion for Process Type and

Process Instance Changes

In this section we present a criterion for correctly propagating process type

changes to both unbiased and biased process instances (cf. Axiom 1).

Axiom 1 (Propagating Type Changes To Biased Instances) LetTbea

process type with actual schema version S. Assume that a new (correct) schema

version S’ is derived from S by applying type change ∆Tto it. Then: ∆Tmay

be propagated to instance I (with type T and current instance execution schema

SI:=S+∆I):⇔

1. Structural Correctness: S∗

I:= (S+∆I)+∆Tis a correct schema ac-

cording to the structural correctness constraints set out by the used process

meta model; i.e., ∆Tcan be correctly applied to SI=(S+∆I).

2. State-Related Correctness: Iis compliant with S∗

I(cf. 2); i.e., the exe-

cution history Hred of I can be produced on S∗

Ias well.1

3. Semantical Correctness: ∆Tand ∆Iare semantically conﬂict-free.

Axiom 1 is valid for unbiased as well as for biased process instances. More

precisely, it handles unbiased instances as a special case; i.e., for an unbiased

instance we obtain S∗

I=Swhereby S’ is correct according to the assumption

of Axiom 1 and ∆Tand ∆Iare semantically conﬂict-free. Consequently, only

state-related correctness has to be checked what exactly corresponds to the well-

known compliance criterion [3,9,12]; i.e., an unbiased instance I is compliant

with a changed schema S’ if its previous execution trace on S is also a possible

execution trace on S’ (cf. Requirement 2 in Axiom 1).

Regarding Requirement 1 of Axiom 1 we ﬁrst have to ensure that ∆Tis

actually applicable to the instance-speciﬁc execution schema SI:= S+∆I.

1An execution history Hof instance I on S usually logs all start and end events gene-

rated during the execution of I. The reduced execution history Hred is determined

by logically discarding all entries from Hwhich have been produced by another than

the actual loop iteration for each loop contained in S. The reduction from Hto Hred

is necessary in order to avoid restrictiveness in conjuntion with loops [12]).

On Dealing with Structural Conﬂicts 277

Therefore, generally, all ”pre-conditions” of ∆Ton SImust be fulﬁlled. How

these change pre-conditions exactly look like depends on the respective change

operations. However, a common claim for all kinds of change operations is that

all schema objects manipulated by ∆Tshould be present in SI. An example for

a process type change ∆Tnot applicable to SIis depicted in Fig. 2: ∆Tdeletes

activity Dwhich has already been deleted at the instance level. Intuitively, ∆T

cannot be applied to the instance-speciﬁc schema SI.

'T = insertPlace(S, D, E) 'T = insertPlace(S, D, E)

completed

activated TRUE Si

naled

E F

H B G

C D

E F

H B G

C D

E F

H B G

not applicable to S

Schema S: Schema S’:

Instance I (on SI)

'T = deleteActivity(S, D)

Fig. 2. Process Type Change Not Applicable to Instance-Speciﬁc Schema

If, in contrast, ∆Tis applicable to SI, target schema S∗

I:= (S+∆I)+∆T

can be produced. However, the resulting instance-speciﬁc schema S∗

Imay still

contain control and data ﬂow errors (like deadlock-causing cycles or missing

input data). We therefore must analyze S∗

Iwith respect to its structural correc-

tness properties (e.g., absence of cycles except loop bodies) by the corresponding

”post-conditions” of ∆Ton SI. The core problem addressed in this paper is how

to (eﬃciently) ensure that S∗

Idoes not contain any control or data ﬂow errors,

i.e., to (eﬃciently) ensure that there are no structural conﬂicts between process

schema and instance changes (cf. Requirement 2 of Axiom 1). Obviously, an ap-

propriate approach for this problem has to work for a large number of biased

process instances as well. As mentioned in the introduction, a naive solution

would be to ﬁrst materialize schema S∗

I:= (S+∆I)+∆Tfor each (biased)

instance Iand then to apply respective correctness checks on S∗

I. However, this

may result in a serious performance problem caused by the expensive materia-

lization of S∗

Ion the one hand and the subsequent complex control and data

ﬂow correctness checks on S∗

Ion the other hand. Again note that these two

steps would have to be applied to each biased instance to be migrated.

Therefore, in this paper, we show how expensive correctness tests (based on

materialized schemes S∗

Ifor each biased instance I) can be avoided. The key idea

behind is to detect potential control and data ﬂow errors in S∗

I:= S+(∆I)+∆T

solely based on the applied changes ∆Tand ∆I, and the original schema S.

More precisely, we elaborate quickly checkable conﬂict tests by exploiting the

semantics of the applied changes ∆Tand ∆I. Respective conﬂict tests either

yield that there would be deﬁnitely no control or data ﬂow error in schema S∗

Ior

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

they indicate that a possible structural conﬂict between ∆Tand ∆I(potentially

leading to such an error) may occur.

How to check state-related correctness (cf. Requirement 2 of Axiom 1) has

been described in another paper of our group [12]. We have developed a set

of compliance rules which can be used for checking state-related compliance of

unbiased as well as of biased process instances with a modiﬁed schema. More

precisely, these compliance rules deﬁne eﬃciently checkable conditions on activity

node markings for each applicable change operation.

A semantical conﬂict (cf. Requirement 3 of Axiom 1) may occur, for example,

if ∆Tinserts activity ”give drug A” at process type level and ∆Iinserts activity

”give drug B” at instance level and there is a medical incompatibility between

drugs Aand B. Consequently, executing instance I on target schema S∗

Iwould

lead to a medication with incompatible drugs. The detection of this semantical

conﬂict requires additional information about the changes. Due to lack of space

we obstain from further details about semantical issues in this paper.

3 Fundamentals

In order to be able to precisely deﬁne structural conﬂicts tests for concurrent

process type and instance changes we need a formal process meta model. In this

paper, we exemplarily use WSM-Nets (as for example applied in ADEPT [13])

and the change operations based on them for this purpose. However, similar

conﬂict tests can be developed for other process meta models as well.

Deﬁnition 1 (WSM-Net). A tuple S = (N, D, NT, CtrlE, SyncE, LoopE,

DataE) is called a WSM-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}

NT assigns to each node of the WSM-Net a respective node type.

–CtrlE ⊂N×N is a precedence relation

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

ches

–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

Thus, a process schema is represented by attributed serial-parallel graphs

with additional sync links. A WSM-Net Sis structurally correct if the following

constraints hold:

1. Shas a unique start node Start and a unique end node End.

2. Except for nodes Start and End each activity node of Shas at least one

incoming and one outgoing control edge e∈CtrlE.

3. Sblock := (N, CtrlE, LoopE) is structured following a block concept, for

which control blocks (sequences, branchings, loops) can be nested but must

not overlap.

On Dealing with Structural Conﬂicts 279

4. Sfwd = (N, CtrlE, SyncE) is an acyclic graph, i.e., the use of control and

sync edges must not lead to deadlock-causing cycles.

5. Sync links must not cross the boundary of a loop block; i.e., an activity from

a loop block must not be connected with an activity from outside the loop

block via a sync link (and vice versa).

6. For activities for which a mandatory input parameter is linked to a data

element d∈Dit has to be ensured that dwill be always written at runtime

independently of which execution path will be chosen.

7. Parallel write accesses on data elements (and consequently lost updates)

have to be avoided.

Taking a correct WSM Net Snew instances can be created and started. Lo-

gically, each process instance Iis associated with an instance-speciﬁc schema

SI:= S+∆I(for unbiased instances SI=Sholds). The control state of I

is captured by a marking function MSI=(NSSI,ES

SI). It assigns to each ac-

tivity nits current status NS(n) and to each control and loop edge its marking

ES(e). These markings are determined according to well deﬁned marking rules

[8], whereas markings of already passed regions and skipped branches are preser-

ved (except loop backs). Concerning data elements, diﬀerent versions of a data

object may be stored, which is important for the context-dependent reading of

data elements and the handling of (partial) rollback operations. Formally:

Deﬁnition 2 (Process Instance). A process instance I is deﬁned by a tuple

(S, ∆I,MSI,Val

SI,H) where

–S = (N, D, NT, CtrlE, SyncE, ...) denotes the process schema I was derived

from. We call S the original schema of I.

–∆Icomprises instance-speciﬁc changes opI

1,...,op

mthat have been applied

to I so far. Schema SI:= S+∆I, which results from the application of ∆I

to S, is called the instance execution schema of I.

–MSI= (NSSI,ES

SI) describes node and edge markings of I:

NSSI:N→{NotActivated, Activated, Running, Completed,

Skipped}

ESSI: (CtrlE ∪SyncE ∪LoopE) →

{NotSignaled, TrueSignaled, FalseSignaled}

–ValSIis 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. As an example take instance Iin

Fig. 3: Activity Ais completed whereas activity Bis activated. Activities with

marking Skipped cannot longer be selected for execution.

Table 1 presents a selection of high-level operations which can be used to de-

ﬁne or change WSM-Nets. We distinguish between basic and high-level change

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

operations. Examples for basic change operations are insertion/deletion of ac-

tivity nodes or control edges. Such basic change operations can be applied to

a process schema; afterwards structural correctness of the resulting schema has

to be checked. In contrast, high-level change operations include formal pre- and

post-conditions and automatically perform the necessary schema transformati-

ons such that schema correctness can be ensured. An example is process type

change ∆Tin Fig. 3: ∆Tserially inserts activity Xinto S by automatically

embedding Xbetween activities Dand G. (For more complex examples see [8]).

Table 1. A Selection of High-Level Change Operations on WSM-Nets

Change Operation ∆Eﬀects on Schema S

Applied to Schema S

Additive Change Operations

serialInsert(S, X, A, B) serial insertion of activity X between activities A and B

parallelInsert(S, X, CtrlBlock) insertion of activity X parallel to control block CtrlBlock

insertSyncEdge(S, src, dest) insertion of sync edge linking two parallel nodes src and dest

Subtractive Change Operations

deleteActivity(S, X) deletes activity X from schema S

deleteSyncEdge(S, edge) deletes edge ∈SyncE from schema S

Order-Changing Operations

serialMoveActivity(S, X, A, B) moves activity X from current position

to position between activities A and B

parallelMoveActivity(S, X, CtrlBlock) moves activity X to position parallel to control block CtrlBlock

Attribute Changing Operations

changeActivityAttribute(S, X, attr, nV) changes value of attribute attr of activity X to nV

changeEdgeAttribute(S, edge, attr, nV) changes value of attribute attr of edge ∈CtrlE ∪SyncE to nV

Data Flow Change Operations

addDataElement(S, d, dom, defVal) adds data element d with domain dom

and default value defVal to S

deleteDataElement(S, d) deletes data element d from S

addDataEdge(S, (X, d, mode)) adds data edge (X, d, mode) to S (mode ∈{read, write})

deleteDataEdge(S, dL)) deletes data edge dL from S

4 Structural Conﬂict Tests

In this section, we provide simple but eﬀective tests for detecting potential con-

ﬂicts between concurrently applied control and/or data ﬂow changes. In parti-

cular, respective tests can be used in connection with the common support of

process type and process instance changes.

4.1 On Detecting Control Flow Conﬂicts

A serious problem which may arise from the uncontrolled propagation of a

process type change ∆Tto a biased instance (on instance-speciﬁc schema

SI:= S+∆I) is the occurence of deadlock-causing cycles (for an example

On Dealing with Structural Conﬂicts 281

see Fig. 1). As mentioned before, a naive solution would be to ﬁrst materialize

the target schema S∗

I:= (S+∆I)+∆Tand then to carry out respective cycle

checks on S∗

I. Since these materialization and validation steps would have to be

applied for each biased instance I, this approach would cause severe performance

problems. Thus, our ambition is to perform an appropriate deadlock test based

on information given by the process type and instance changes themselves and

the original process schema S. A ﬁrst version of a deadlock tests satisfying these

claims is given in Proposition 1 [13]:

Proposition 1 (Basic Deadlock Prevention). Let S be a WSM-Net

and I be a biased instance with starting schema S and execution schema

SI:= S+∆I=(NI,D

I,NT

I,CtrlE

I, SyncEI,...). Assume that type change

∆Ttransforms S into a correct schema S’ = (N’, D’, NT’, CtrlE’, SyncE’, ...).

Then: S∗

I=(S+∆I)+∆Tdoes not contain deadlock-causing cycles if the

following condition holds:

∀(s1,d

1)∈AS(S, ∆T), ∀(s2,d

2)AS(S, ∆I):

d1∈ (pred∗(S, s2)∪{s2})∨d2∈ (pred∗(S, s1)∪{s1})(Ψ)

whereas

•AS(S, ∆T):=SyncE\SyncE

•AS(S, ∆I):=SyncEI\SyncE

•pred∗(S, n) denotes all direct and indirect predecessors of activity n

when considering both control and sync edges of S.

By simply applying condition Ψfrom Proposition 1 we can exclude deadlocks

when propagating a type change to a biased instance. Note that condition Ψis

based on the original process schema S. Consequently, an easy conﬂict test can

be derived which avoids the materialization of any other schema (SIor S∗

I).

In general, the quality of a conﬂict test can be measured according to how

eﬃciently it can be applied to concurrent process type and instance changes.

Another important quality factor is the number of ”uncritical” instances Ifor

which conﬂicts between process type and instance changes can be deﬁnitely

excluded. The deadlock test derived from Proposition 1 is a ”good” test with

respect to eﬃciency. However, it still scores lower regarding the second quality

factor. Reason is that for particular instance changes ∆Ithis test indicates

conﬂicts with type change ∆Talthough the target schema S∗

I:= (S+∆I)+∆T

will not contain any deadlock causing cycle. An example is depicted in Fig.

3: Instance change ∆Iinserts a sync edge between activities Cand Falready

contained in Swhereas type change ∆Tinserts a sync edge between also newly

inserted activites Xand Y. From the applied changes we derive AS(S, ∆T)=

{(X, Y)}and AS(S, ∆I)={(C, F)}(cf. Proposition 1). The expression yielding

from applying condition Ψfrom Proposition 1 to these sets cannot be evaluated

due to the absence of activites Xand Yin S. Consequently, the respective

conﬂict test is unable to exclude the occurence of a deadlock-causing cycle in S

although in fact there is none.

At ﬁrst glance it seems that we must materialize and validate target schema

S∗

Iin order to overcome this problem. This approach, however, oﬀends against

the eﬃciency quality factor. Fortunately, there is another solution avoiding ma-

terialization of S∗

Iand excluding deadlock conﬂicts for ”uncritical” instances.

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

Consider again the example given in Fig. 3: Here we cannot evaluate condition

Ψbased on sync edge (X, Y ) since its source and destination activities have been

newly inserted by ∆Tas well. However, the insertion of sync edge (X, Y )does

not only set out the direct order relation ”Xbefore Y” but also, for example, the

transitive order relation ”Dbefore E”. Since Dand Eare present in Swe are

able to verify condition Ψfor a respective sync edge (D, E). Based on this con-

sideration we try to virtually re-link the actual sync edge (X, Y ) to the virtual

sync edge (D, E). The challenge is to determine the virtual sync edge(s) based

on which condition Ψcan be evaluated on S. Then solely based on Swe can

determine whether S∗

Iwill contain a deadlock-causing cycle or not. From ∆Twe

know which activities have been inserted and into which context they have been

embedded (insertion context). For serial insertion of activities, for example, the

insertion context includes the direct predecessor and successor of the newly ins-

erted activity. For the newly inserted activity Xin Fig. 3, for example, insertion

context (D, G) includes the direct predecessor Dof Xin S’ and for the newly

inserted activity Yits insertion context (B,E) includes the direct successor Eof

Yin S. Altogether, this is the information we need for determining the virtual

sync edges between activities present in S. In our example (cf. Fig. 3) we get

the virtual sync egde (D, E) instead of (X, Y ).

Schema S: Schema S’

Instance I (on S + 'I): Instance I (on (S + 'I) + 'T):

C D

E F

H B G

com

leted activated TRUE Si

naled

'T = (serialInsert(S, X, D, G), serialInsert(S, Y, B, E),

insertSyncEdge(S, (X, Y))

'I = (insertSyncEdge(S, (C, F))

nc ed

C D

Y E

B G

Fig. 3. Insertion of Sync Edges on Process Type and Instance Level

Thus, the idea behind is to ﬁrst transfer the order relations set out by the

newly inserted sync edges to starting schema Sby applying ”virtual” graph

reduction rules and then to apply condition Ψof Proposition 1 to the reduced

graph. The respective graph reduction approach applicable in connection with

the composed insertion of activities and sync edges is given in Algorithm 1:

Algorithm 1 (Graph Reduction Rules (Deadlock Prevention)) Let S

= (N, D, NT, CtrlE, SyncE, ...) be a WSM-Net and ∆be a type change which

transforms S into a correct schema S’ = (N’, D’, NT’, CtrlE’, SyncE’, ...). Let

further

•AS(S, ∆):=SyncE\SyncE and

•AA(S, ∆):= {(X, (src, dest)) |X∈N’, src, dest ∈N, X serially inserted

between src and dest by ∆}.

On Dealing with Structural Conﬂicts 283

GraphRed(N, AS(S, ∆), AA(S, ∆)) −→ (ASred(S, ∆))

ASred(S, ∆):=∅

forall (src, dest) ∈AS(S, ∆)do

while src ∈ Ndo

find (src, (pSrc, sSrc)) ∈AA(S, ∆);

src := pSrc;

done

while dest ∈ Ndo

find (dest, (pDest, sDest)) ∈AA(S, ∆);

dest := sDest;

done

ASred(S, ∆):=ASred(S, ∆)∪{(src, dest)}

done

Algorithm 1 works by replacing the source (destination) nodes of the newly

inserted sync edges by their direct predecessors (successors) if these nodes have

not been present in the original schema S. If several activities are inserted in a

row Algorithm 1 iteratively replaces them by their direct predecessors/successors

until we ﬁnd an adequate predecessor/successor also present in S. In the following

Prop. 2, condition Ψof Prop. 1 is applied based on the graph reduction of

Algorithm 1. A deadlock test derived from this proposition fulﬁlls both desired

quality factors: It is eﬃciently applicable based on original schema Sand it does

not indicate deadlocks for target schema S∗

Iif S∗

Iis actually deadlock-free.

Proposition 2 (Deadlock Prevention (2)). Let the assumption be as in Pro-

position 1. Let further ASred(S, ∆T) and ASred(S, ∆I) be the sync edge reduc-

tions after applying Algorithm 1.

Then: S∗

I=(S+∆I)+∆Sdoes not contain deadlock-causing cycles iﬀ the

following condition holds:

∀(s1,d

1)∈AS

red(S, ∆T), ∀(s2,d

2)∈AS

red(S, ∆I):

d1∈ (pred∗(S, s2)∪{s2})∨d2∈ (pred∗(S, s1)∪{s1})(Ψ)

As already mentioned, the reduction rules of Algorithm 1 are necessary in

order to transfer the order relations set out by the newly inserted sync edges

to the original schema S. As decribed in Proposition 2, we apply Algorithm 1

to the sync edges and activities newly inserted by ∆Tand ∆I. Based on the

resulting sets ASred(S, ∆T) and ASred(S, ∆I) condition Ψfrom Proposition 1

can be applied to S. Doing so saves us from expensive checks on S∗

In general, there are further constraints set out by the particular process

meta model. In block-structured meta models like BPEL4WS [14] or ADEPT

[8], for example, it is forbidden that sync links cross the boundaries of loop

blocks. However, uncontrolled propagation complex process type changes to bia-

sed instances may result in such undesired sync links. Therefore we have made

formal propositions for respective cases as well from which quick conﬂict tests

can be derived. Due to lack of space we obstain from further details here.

4.2 On Detecting Data Flow Conﬂicts

An uncontrolled propagation of process type change ∆Tto biased instance I on

SI=S+∆Imay not only cause control ﬂow errors as described above but

also severe data ﬂow problems. The detection of data ﬂow conﬂicts based on the

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

materialization of schema S∗

I:= (S+∆I)+∆Thas at least the same complexity

as respective control ﬂow checks. Our data ﬂow constraints from Def. 1 forbid

activities with missing input data and lost updates on data elements. Respective

problems may occur for S∗

Iif both instance and type change delete write data

links on the same data element read by other activities in the sequel. An example

is depicted in Fig. 4 where ∆Tand ∆Idelete write data links related to the same

data element d1which causes missing input data of activity Gin S∗

incorrect.

Sincorrect* := (S + 'I) + 'T

Instance I on SI:= S + 'I:

S’ := S + 'T

Schema S:

'T = (deleteActivity(S, A), deleteActvity(S, B),

deleteDataEdge(S, (A, d1, write)),

deleteData Edge(S, (B, d1, read)))

'I = (deleteActivity(S, D),

deleteDataEdge(S, (D, d1, write)))

A B C D E F

A B C E F G

C D E F G

C E F G

missing input data

Fig. 4. Deleting All Necessary Write Accesses on Instance Data (Example)

Therefore, in the following we provide a formal proposition to exclude data

ﬂow errors for S∗

Ifor a magnitude of instances solely on basis of ∆Tand ∆I.

Proposition 3 (Avoiding Missing Input Data and Lost Updates).

Let S be a WSM-Net and I be a biased instance with starting schema S and

execution schema SI:= S+∆I=(NI,D

I,NT

I,CtrlE

I, SyncEI,...). Assume

that type change ∆Ttransforms S into a correct schema S’ = (N’, D’, NT’,

CtrlE’, SyncE’, ...). Then: Propagating ∆Tto I neither results in missing input

data nor in lost updates if

∀mDL1=(d1,mode

1,[”add”|”delete”])∈AD(S, ∆T)∪DD(S, ∆T),

∀mDL2=(d2,mode

2,[”add”|”delete”])∈∈AD(S, ∆I)∪DD(S, ∆I)

with modei∈{read, write}(i=1,2):

d1=d2∨

mode1 = mode2 = read ∨

mDL1=(d1, ”read”, ”delete”) ∨mDL2=(d2, read, ”delete”) (♣)

whereas

•AD(S, ∆T):={(d, mode, ”add”) ∈DataE\DataE,mode∈{read, write}}

•DD(S, ∆T):={(d, mode, ”delete”) ∈DataE \DataE,mode∈{read, write}}

•AD(S, ∆I):={(d, mode, ”add”) ∈DataEI\DataE,mode∈{read, write}}

•DD(S, ∆I):={(d, mode, ”delete”) ∈DataE \DataEI,mode∈{read, write}}

In Fig. 5, ∆Tdeletes activities Band Ftogether with data edges (B, d2,

write) and (F, d2, read). At the instance level, ∆Iserially inserts activity Y

between activities Dand Ewith a read data link connected to data element

d2(∆I={addDataEdge(S, (Y, d2, read))}). Obviously, propagating ∆Tto SI

On Dealing with Structural Conﬂicts 285

leads to the problem of missing input data regarding the newly inserted activity

Y. Condition ♣from Proposition 3 indicates this conﬂict since both type and

instance change, work on the same data element d2by deleting write data links

and inserting new read data links for this data element. Such critical instances

can be easily detected by a test derived from Proposition 3. Note that otherwise

expensive data ﬂow analyses on S∗

Iwould become necessary.

A B C D E F

A C D E

incorrect

* := (S + '

) + '

Instance I on S

:= S + '

S’ := S + '

Schema S:

A B C D Y E

F A C D Y E

missing

input data

= (deleteActivity(S, B), deleteActvity(S, F),

deleteDataEdge(S, (B, d

, write)),

deleteData Edge(S, (F, d

, read)))

= (serialInsert(S, Y, D, E),

addDataEdge(S, (Y, d

, read)))

Fig. 5. Deleting Write Accesses on Data Read by Newly Inserted Activity (Example)

For a few special cases, a conﬂict test derived from Propostion 3 may identify

potential conﬂicts which would not lead to a violation of the data ﬂow constraints

set out in Def. 1. Nevertheless, the presented propositions and the respective tests

are very helpful to quickly and eﬃciently detect conﬂicts between concurrent

data ﬂow changes at the type and instance level.

4.3 Structural Conﬂicts for Seleted Process Meta Models

Some of the potential conﬂicts between concurrent process type and instance

changes as introduced in Section 4.1 are present for other process meta models

as well. One example is the deadlock-causing cycle contained in a Petri Net after

the uncontrolled insertion of new order relations by process and instance changes

(cf. Fig. 1). Of course a conﬂict test derived from Proposition 2 may be easily

transferred to Activity Nets as used by WebSphere MQWorkﬂow [15] as well.

For other process meta models additional conﬂicts between process type and

instance changes may occur. In the following, we exemplarily consider Activity

Nets [15]. One reasonable control ﬂow constraint for this process meta model

may be to require the absence of isolated activity nodes in order to ensure clearly

deﬁned process start and end states. An example for an Activity Net containing

an isolated activity node after an uncontrolled application of concurrent process

type and instance changes is depicted in Fig. 6: ∆Tdeletes control link (C, E)

whereas ∆Ihas already deleted control link (E,I). The uncontrolled propagation

of ∆Tto instance-speciﬁc schema SIleads to target schema (S+∆I)+∆T

containing isolated activity node E. Consequently, it would be a good idea to

ﬁnd an appropriate formal proposition setting out conditions to detect isolated

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

activity nodes based on the applied change operations. Based on this an eﬃcient

conﬂict test could be derived.

Schema S: Schema S’:

Instance I (on S + 'I): Instance I (on (S + 'I) + 'T):

A B I H

G F

A B I H

G F

'T = (deleteCtrlEdge(S, (C, E)))

'T = (deleteCtrlEdge(S, (E, I)))

isolated

activity!!

A B com

leted activated

Fig. 6. Changes Causing Isolated Activity Nodes in Activity Nets

Interestingly, the test detecting isolated activities does not depend on the

underlying process meta model but on the kind of applied change operation. As

we have discussed in Section 3, generally, there are two levels for deﬁning change

operations. On the basis level change primitives may be carried out without

special pre- and post-conditions. This is the reason why we get an isolated ac-

tivity node in Fig. 6. When applying change operations on a higher semantical

level, as for example deﬁned for WSM-Nets (cf. Table 1) this speciﬁc problem is

prohibited. Another problem arising in connection with basis change primitives

is present for block-structured process meta models, like BPEL4WS [14] and

ADEPT, namely the violation ot the block structure.

5 Illustrating Example

To summarize the results presented in this paper and to show the whole mi-

gration process followed in our approach we provide an illustrating example. In

Fig. 7 process type change ∆Ttransforms schema Sinto new schema version

Sby serially inserting activites Xand Yand by connecting them via a sync

link (X, Y ). Furthermore ∆Tdeletes activities Fand Htogether with their res-

pective data links dL6and dL7. Based on original schema Stwo instances have

been started. Instance I1is biased and therefore runs according to its instance-

speciﬁc schema SI1whereas I2is an unbiased instance still running according

to S. If now type change ∆Tshall be propagated to these instances we have to

check structural as well as state-related compliance for the running instances.

Instance change ∆I1has serially inserted two activites Uand Tand sync link

(T,U) between them. At ﬁrst, the deadlock test derived from Proposition 2 is

carried out to detect whether target schema S∗

1will contain a deadlock-causing

cycle or not. After applying the graph reduction rules of Algorithm 1 we obtain

that S∗

1will actually contain a deadlock-causing cycle and therefore I1cannot

On Dealing with Structural Conﬂicts 287

migrate to S(and remains running according to S). For unbiased Instance I2

we only have to check state-related compliance as described in Section 2. Since

the previous execution of I2can be replayed on S,I2is compliant with Sand

therefore migrates to Sby applying appropriate marking adaptation rules [13].

Schema S:

Schema S’

'T = (serialInsert(S, X, C, D), serialInsert(S, Y, E, F), insertSyncEdge(S, (X, Y)),

deleteDataEdge(S, dL6), deleteDataEdge(S, dL7), deleteActivity(S, F), deleteActivity(S, H))

1 d

2 d

1 d

2 d

3 d

C X

E Y

B G

d1 d2

dL1 dL2

dL3 dL4

Instance I1 (on SI1 = S + 'I1): 'I1 = (serialInsert(S, U, B, C), serialInsert(S, T, F, G), insertSyncEdge(S, (T, U)))

U C

E F

H B G

d1 d2 d3

dL1 dL2

dL3 dL4

dL5

dL6

C D

E F

H B G

d1 d2 d3

dL1 dL2

dL3 dL4

dL5

dL6

Structural Compliance:

AS(S, ∆I1) = {(T, U)}, AA(S, ∆I1) = {(U, (B, C)), (T, (F, G))}

Æ (Alg. 1) ASred(S, ∆I1) = {(F, C)}

AS(S, ∆T) = {(X, Y)}, AA(S, ∆T) = {(Y, (E, F)), (X, (C, D))}

Æ (Alg. 1) ASred(S, ∆T) = {(C, G)}

C  pred*(S, C) 

S1* will contain deadlock-causing cycle

Instance I2 (on S):

C X

E Y

B G

d1 d2

dL1 dL2

dL3 dL4

State-Related Compliance Æ migrate I2 to S’ + marking adaptations

Fig. 7. Process Type Change and Instance Migration

6 Related Work

Today’s workﬂow technology is rather weak with respect to dynamic process

changes [16]. Particularly, it is unsuited for supporting long-running processes.

As a consequence, process descriptions are often split into a series of smaller,

short-running process fragments that are maintained as separate schemes and

correlated through application data at runtime. Such a fragmented representa-

tion, however, does not provide a natural view of the process and is also unfa-

vorable in other respects. In particular, it does not abolish the need for dynamic

instance migrations (even if techniques such as late binding are applied).

Adaptive workﬂows have been addressed in many research papers so far [1,2,

3,5,6,7,10]. The main focus was put on providing appropriate correctness crite-

ria for deciding about compliance of unbiased process instances with a changed

process schema. More precisely, these criteria solely aim on state-related correc-

tness when propagating a process type change to an instance. There are only few

approaches [10,11] to allow process type and changes within one PMS. Howe-

ver, there is no interplay between process type and instance changes. WASA2

[10], for example, realizes changes of single process instances by deriving a new

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

schema version with one running instance. Consequently, individually modiﬁed

instances are totally excluded from further process type optimizations.

For unbiased process instances, correctness criteria range from graph equiva-

lence [1,2,10] to trace equivalence [3,5,6,7]:

In [1], v.d. Aalst and Basten base correctness of dynamic process change

on special inheritance relations between original and changed process schema.

Compliance can be ensured by checking easy conditions on these two schemes.

This approach also provides transformation rules which automatically adapt

instance markings on the changed schema. For correctness checking, Agostini

and De Michelis [2] construct reachability graphs for the original and the changed

process schema. Based on this, it can be determined whether a process instance

is in a state which exists on the changed process schema as well. In contrast,

Weske [10] proposes to construct the purged instance graph – a subgraph of the

respective process schema consisting of already passed regions for each instance.

Then it has to be analyzed if there is a valid mapping between the purged

instance graph and the changed process schema.

A ﬁrst approach based on trace equivalence was presented by Casati et al [3].

Here a process instance is compliant with a changed process schema if the exe-

cution history of this instance can be reproduced on the change process schema

as well. Ellis et al [5] present a Petri-Net based approach. A process instance is

compliant with the changed process schema if the ﬁring sequence of this instance

previous to the change can be executed on the changed process schema as well.

Kradolfer [6] and Sadiq et al [7] both use the compliance criterion presented in

[3]. Thereby Kradolfer [6] provides conditions based on the instance execution

history and the applied change operation to check compliance whereas Sadiq et

al [7] focus on the treatment of non-compliant instances and temporal aspects

in conjunction with dynamic change.

The described WSM-Nets are somewhat comparable to BPEL4WS (Business

Process Execution Language for Web Services) [14], but with a better understan-

ding and formal foundation regarding the use of links (called sync links in our

approach). Though there is some work on exception handling in BPEL4WS [17],

dynamic change issues have been completely factored out.

A detailed discussion of all these approaches can be found in [16]. It would

be very interesting to learn more about the deﬁnition of change operations and

the use of their speciﬁc semantics for the diﬀerent process meta models.

7 Summary and Outlook

We have introduced basic work on the challenging question of how to correctly

deal with concurrent process type and instance changes. At ﬁrst, a comprehen-

sive correctness criterion has been presented including structural, state-related

and semantical correctness when propagating process type changes to biased

process instances. Furthermore, we have derived formal propositions for con-

structing eﬃcient tests which allow us to quickly and eﬃciently detect potential

conﬂicts between changes at the type and instance level. These tests are based

on WSM-Nets. However, we have discussed possible conﬂicts between process

type and instance changes for other process meta models like Petri-Nets and

On Dealing with Structural Conﬂicts 289

Activity Nets as well. In our future work on adaptive processes, we will consider

semantical conﬂicts between concurrent process changes and their treatment as

well. Furthermore, we will fully implement both, structural as well as semanti-

cal conﬂict tests in our current proof-of-concept prototype for process schema

evolution. Hereby, it is very important to think about implementation issues like

locking of instances or the order in which structural, state-related and semanti-

cal correctness is checked. In any case, the support of process type and instance

changes would beneﬁt by a more intense study of the research community.

References

1. 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

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

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

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

Engineering 24 (1998) 211–238

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

Data and Knowledge Engineering 34 (2000) 271–304

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

In: Proc. COOCS ’95, Milpitas, CA (1995) 10–21

6. 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

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

workﬂow processes. IJCIS 9(2000) 93–116

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

without losing control. JIIS 10 (1998) 93–129

9. Rinderle, S., Reichert, M., Dadam, P.: Evaluation of correctness criteria for dy-

namic workﬂow changes. In: Proc. Int’l Conf. on Business Process Management

(BPM ’03). LNCS 2678, Eindhoven, The Netherlands, Springer (2003) 41–57

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

workﬂow management system. In: HICSS-34. (2001)

11. Kochut, K., Arnold, J., Sheth, A., Miller, J., Kraemer, E., Arpinar, B., Cardoso,

J.: IntelliGEN: A distributed workﬂow system for discovering protein-protein in-

teractions. Distributed and Parallel Databases 13 (2003) 43–72

12. Rinderle, S., Reichert, M., Dadam, P.: Flexible support of team processes by

adaptive workﬂow systems. Distributed and Parallel Databases (to appear)

13. Reichert, M., Rinderle, S., Dadam, P.: On the common support of workﬂow type

and instance changes under correctness constraints. In: Proc. CoopIS ’03, Catania,

Italy (2003) 407–425

14. Curbera, F., Goland, Y., Klein, J., Leymann, F., Roller, D., Thatte, S., Weera-

warana, S.: Business Process Execution Language for Web Services, Version 1.0.

(2002) http://www.ibm.com/developerworks/library/ws-bpel/.

15. Leymann, F., Altenhuber, W.: Managing business processes as an information

ressource. IBM Systems Journal 33 (1994) 326–348

16. Rinderle, S., Reichert, M., Dadam, P.: Correctness criteria for dynamic changes in

workﬂow systems – a survey. Data and Knowledge Engineering (to appear)

17. Curbera, F., Khalaf, R., Leymann, F., Weerawarana, S.: Execption handling in

the BPEL4WS language. In: BPM’03, Eindhoven (2003) 276–290