Advanced Migration Strategies for Adaptive Process Management Systems [original]

Advanced Migration Strategies for Adaptive Process Management Systems

Stefanie Rinderle-Ma

University of Vienna, Austria

Faculty of Computer Science

stefanie.rinderle-ma@univie.ac.at

Manfred Reichert

Ulm University, Germany

DBIS Institute

[email protected]

Abstract

Enabling dynamic process changes is an essential re-

quirement for any adaptive process management technol-

ogy. Particularly, it should be possible to migrate (long-)

running process instances to a new process schema ver-

sion. Further, instance migration must not violate sound-

ness; i.e., structural and behavorial consistency of executed

process schemas need to be preserved. State compliance

has been introduced as basic correctness notion to ensure

that instances, whose state has progressed too far, are pro-

hibited from being migrated. However, this also excludes

them from future process optimizations, which is often not

tolerable in practice. This paper introduces advanced mi-

gration strategies for coping with non-compliant instances

in the context of process change such that they can benefit

from future process type changes on the one hand, but do not

run into soundness problems on the other hand. Contrary

to existing approaches, the strategies proposed in this paper

are based on adjustments at process type and instance level.

Altogether, the suggested migration strategies complement

treatment of non-compliant process instances.

1 Introduction

The ability to effectively deal with change has been

identified as key functionality for any process-aware in-

formation systems (PAIS). Through the separation of pro-

cess logic from application code, PAIS facilitate process

changes significantly. In the context of long-running pro-

cesses (e.g., medical treatment), PAIS should additionally

enable the propagation of such process changes to ongoing

process instances. Regarding the support of dynamic pro-

cess changes, PAIS robustness is fundamental; i.e., changes

must not violate soundness [14] of the running process in-

stances. In response to this challenge adaptive process man-

agement technology has emerged, which enables dynamic

process changes at different levels [1, 8, 11, 12, 14]. Most

approaches apply a specific correctness notion to ensure

that only those process instances may migrate to a modi-

fied process schema for which soundness is maintained af-

terwards. One of the most prominent criteria used in this

context is state compliance [1, 8]. Based on state compli-

ance it is ensured that instances, whose state has progressed

too far, are prohibited from being migrated. However, tak-

ing the experience we gathered when applying our adaptive

process management system AristaFlow (www.aristaflow-

forum.de) in practice we learned that state compliance is

sometimes too restrictive in respect to the migration of long-

running processes (see next paragraph).

SS‘S‘‘

ΔSΔS‘ ΔS‘‘

I1, …, IkI1, …, Ik-j I1, …, Ik-j-i

Ik+1, …, InIk-j+1, …, IkIk-j-i+1, …, Ik-j

migrate

compliant

non-compliant

migrate

adjustment Æmigrate adjustment Æmigrate

Figure 1. Instance Migration

Consider the abstract scenario from Fig. 1: On process

schema S, instances I1, ..., Inare running. Then Sis trans-

formed into new schema version S0by applying process

change ∆S. Assume that it can be decided that I1, ..., Ik

may migrate to S0without violating soundness (i.e., they

are compliant with S0), whereas Ik+1, ..., Inhave already

progressed too far (i.e., they are not compliant with S0).1

As suggested by most approaches Ik+1, ..., Inthen remain

running on S. Assume that a further optimization of the

new schema version S0takes place captured by process

change ∆S0resulting in new type schema version S00. Then

I1, ..., Ikcould also benefit from ∆S0if they were compli-

ant with S00. However, Ik+1, ..., Inare excluded from mi-

gration to S00 anyway since they are not running on S0at

all. This is not tolerable in many practical settings. Think

of, for example, a patient who is excluded from an opti-

mized treatment because his particular process instance can-

1We assume that instances are clustered along their state.

not be migrated to the changed process type schema. Or

consider engineering processes that require changes due to

the replacement of an already released product component.

Regarding change management processes in the automotive

domain, for example, we learned that it must be also possi-

ble to adjust already passed process regions without rolling

back the process. Or in a project with an electricity sup-

plier, we experienced that in the context of schema evolu-

tion, non-compliant instances were adjusted individually to

re-link them to the new process schema version.

In this paper, we introduce advanced strategies for cop-

ing with non-compliant instances in the context of pro-

cess change such that they can benefit from future process

changes on the one hand, but do not run into soundness

problems on the other hand. As depicted in Fig. 2 existing

approaches treat non-compliant process instances by rolling

them back [11], by migrating them with delay [3], or by

enabling a higher number of process instances to migrate

based on relaxing compliance notions [10]. The approach

presented in this paper, can be seen as complementary to all

these approaches. The decision which strategy is to applied,

might depend on the application context. We will give a

short discussion on this in Sect. 5. Note that our work pro-

vides the technical foundation for improving migratability

of instances in adaptive PAIS. Additionally, semantical is-

sues can become relevant for deciding on certain cases. We

will refer to this issue in Sect. 5 based on our work within

the SeaFlows project [5] on semantic-aware processes.

Local Adjustment

Global Adjustment

History-based

Strategy 1

Strategy 2

Strategy 1

Strategy 2

Bias-based

Strategy 3

Strategy 4

Adjustments

Strategy 1

Strategy 2 :

- Single insertions: 

- Multiple insertions: cf. Sect. 5

Data Flow Changes

(accompanying)

Strategy 1

Strategy 2

Strategy 4

INSERT

Control Flow Changes

Strategy 1

Strategy 3

DELETE

Strategy 1

Strategies 2/4

+ Strategy 3

MOVE

Strategy 1

ANY

OTHER

Strategies along Change Types

Coping with Non-

compliant Instances

Relaxed Compliance

Partial Rollback

Delayed Migration

Figure 2. Treating Non-Compliant Instances

Section 2 introduces background information. Section 3

presents different strategies for dealing with non-compliant

instances. Section 4 shows how non-compliant process in-

stances can be structurally adjusted to make them migrate-

able. Section 5 provides an evaluation for applying the dif-

ferent strategies. Section 6 discusses related work and Sec-

tion 8 closes with a summary.

2 Background

We first summarize basic concepts and notions used in

this paper. For each business process to be supported a pro-

cess type T represented by a process schema S has to be de-

fined. For a particular type several process schemas may ex-

ist, representing the different versions and evolution of this

type over time. In the following, a single process schema

is represented as directed graph, which comprises a set of

nodes – representing activities or control connectors (e.g.,

XOR-Split, AND-Join) – and a set of control edges (i.e.,

precedence relations) between them. In the following we

assume relaxed block-structured process schemas; i.e., on

top of block-based process patterns, we provide sync links

for setting up order relations between activities belonging

to parallel branches (similar to the link concept in BPEL).

In this paper, we assume acyclic process structures. In Sect.

5 we provide a discussion on how the proposed migration

strategies can work in connection with loops as well.

Further, a process schema comprises data elements

and data edges. A data edge links an activity with

adata element and represents a read/ write access of

this activity to the respective data element. Altogether,

a process schema Sis represented by a tuple S:=

(N, CtrlE, SyncE, D, DataE, ...)where Ndenotes the

set of activities, CtrlE the set of control egdes, SyncE the

set of sync edges, Dthe set of data elements, and DataE

the set of data edges. Based on process schema Sat run-

time process instances can be created and executed. For

instance Irunning on S, start and/or completion events of

corresponding activities are recorded in execution trace σS

A compact representation of trace σS

Iis given by instance

marking NSIwhich assigns to each activity of Iits current

state. Possible activity states include NotActivated, Acti-

vated, Running, Completed, and Skipped [8].

In general, we assume sound process schemas S[2]. Fol-

lowing the definition given in [14], we distinguish between

structural and behavorial soundness. Basically, a schema

Sis structurally sound if it has exactly one start and one

end activity and all activities are connected. There might

be additional structural soundness constraints set out by the

particular process meta model (e.g. block-structuredness).

In summary, behavorial soundness refers to correct instance

states [8], i.e., the instance must not run into any livelock or

deadlock. Additionally, input data has to be correctly sup-

plied for all activities. If, for example, an activity is started

before all predecessor activities are completed, this activity

will not necessarily be supplied with all required input data.

Process change: Basically, changes can be triggered and

performed at the process type and process instance level.

Changes of a process type T may become necessary to cover

the evolution of the business processes captured in process

schemas of this type [12, 8, 14]. By contrast, changes of

individual process instances are usually performed by end

users and become necessary to react to exceptional situ-

ations [8]. In particular, effects of such changes must be

kept local, i.e., they must not affect other instances of same

type. Thus for each individually modified instance Ian

instance-specific schema SIis maintained. The difference

between SIand original schema Sis captured by the so

called instance-specific bias of I; i.e., ∆I(S). Specifically

∆I(S)captures all change operations applied to Sat in-

stance level in order to obtain instance-specific schema SI.

Instances which have not been individually modified are de-

noted as unbiased instances.

In the context of process type and process instance

changes, structural and behavorial soundness have to be pre-

served. In our ADEPT approach, structural soundness is

achieved based on well-defined pre- and post-conditions for

the different change operations [8]. Behavorial soundness

is accomplished by behavorial correctness criteria. One

prominent example is the state compliance criterion [1]

which is used in the remainder of this paper. Informally,

state compliance checks whether execution trace σS

Iof in-

stance Ion schema Scould be also produced by an instance

on S0in the same order as set out by σS

Metrics on Process Schemas: One possiblity to eval-

uate the migration strategies proposed in the following is

to measure the difference between original process schema

S1and schema S2resulting after applying a certain migra-

tion strategy. For this we apply process metrics like activity

coverage and process similarity. Further we must consider

the number of control relations being different for S1and

S2, denoted by dS(S1, S2). Informally, for each node in S1

(S2) all successor nodes are counted that are different from

the successor nodes of S2(S1). This number should be min-

imized in order to enable propagation of subsequent schema

changes (see Sect. 5 for definitions of these metrics).

3 Treating non-compliant instances

This section discusses strategies for treating non-

compliant instances. Certain kinds of adjustment (cf. Fig.

2) enable non-compliant instances to migrate to the new

schema version if desired by the process engineer; i.e., to

relink them to the new type schema. One of the possible

adjustments is to ”simulate” an instance-specific bias such

that the effects of the type change, for which the instance

has progressed too far, are ”neutralized”. This enables mi-

gration or – more precisely – ”re-linking” of the respective

instance to the new type schema version. Consequently, this

instance can benefit from further schema optimization.

Strategy 1 (Always-Migrate): Basically, any non-

compliant instance can be migrated (i.e., relinked) to modi-

fied type schema version. The idea is as follows: Let Sbe

a process schema which is transformed into S0by change

∆S. Let further Ibe an instance on S. So far, ∆Sis prop-

agated to Iwhen migrating Ito S(i.e., Ireflects ∆Safter

its migration to S0). However, if Iis not compliant with

S0,∆Smust not be applied to I; i.e., execution of Ishould

be continued on its old schema. However, at technical level

this effect can be ”simulated” when re-linking Ito S0by

”neutralizing” type change ∆S. ”Neutralizing” means to

introduce an artificial bias ∆Ion S0which reverses the ef-

fects of ∆Sfor this particular instance. Consider Fig. 3. At

type level activity Xis inserted between activities Aand B

including the insertion of a read data edge from Xon data

element d. Then instance I(cf. Fig. 3b) is not compliant

with S’ since Bhas been already completed. Nevertheless,

Ican be migrated to S0by not applying type change ∆S.

The invalid change ∆Sfor Ion S0can be ”healed” by cre-

ating an instance-specific bias ∆I(S0)for Ion S0;∆I(S0)

then reflects the deviations between S0and instance-specific

schema SI. Specifically, ∆I(S0)constitutes the ”inverse”

change operation of ∆S. In our example, adding Xto Scan

be reversed by deleting read data edge X→das Xfrom

S0. Strategy 1 can be applied for any kind of change regard-

less whether they concern control or data flow. The chal-

lenge is to determine the ”inverse” change to be maintained

for the migrated instance. Tab. 1 shows inverse changes for

activity insertion, deletion, and order-changes as well as for

selected data flow changes. Alternatively, we can directly

determine schema ”difference” between type schema S0and

instance-specific schema, e.g., [4] presents an approach for

comparing two schemas S1and S2in terms of high-level

change operations needed to transform S1into S2.

a) Process type schema S:

b) Unbiased instance I on S:

Modified process type schema S`:

ΔS= <insert(S,X,A,B),

insDEdge(S,d,X,r>

ΔI(S‘) = <delete(S‘,X),

delDEdge(S,d,X)>

I non-compliant with S‘

migrate

Biased instance I on S‘:

S[ΔS>S‘

Activity States:

Completed

Activity:

Activated

d d

Data Flow:

Data element

Data edge

Figure 3. Strat. 1: Always-Migrate (Example)

Strategy 2 (Instance-Specific Adjustment) The idea be-

hind Strategy 2 is to conduct instance-specific adjustments

of type changes. This way we are able to relink non-

compliant instances to the new type schema version. For

this purpose we exploit the specific semantics of the applied

change operation [13]: When inserting an activity, for ex-

ample, the user has to specify the position where to insert

the new activity. Thus activity insertion is a candidate for

instance-specific change adjustment since such position pa-

rameters can be easily adapted; e.g., by inserting the activtiy

Change operation ∆on S opType subject paramList inverseOp

insert(S, X, A, B)ainsert X S, A, B delete(S, X)

Effects on S: inserts activity S between activities A and B.

delete(S, X) delete X S insert(S, X, pred(S,X), succ(S,X))b

Effects on S: deletes activities from S

move(S, X, A, B) move X S, A, B move(S, X, pred(S,X), succ(S,X))

Effects on S: moves activity S from its original position in S to another position between activity sets A and B

insDE(S, d) insert d S delDE(S,d)

Effects on S: inserts data element d into S

delDE(S, d) delete d S insDE(S,d)

Effects on S: deletes data element d from S (d is not referenced by any data connector)

insDEdge(S, d, X, [r|w]) insert d S, X, [r|w] delDEdge(S,d,X)

Effects: inserts read/write dada edge between activity X and data element d into S

delDEdge(S, d, X) delete d S, X insDEdge(S, d, X, [r|w])

Effects: deletes data edge between activity X and data element d

aBasically, insertion between activities A and B can be generalized to insertion between activity sets A,B. Additionally,

for conditional insert an optional parameter [sc] can be included for representing a conditional insert (for details see [13]).

bpred(S,X) / succ(S,X) denotes the direct predecessor(s) / successor(s) of X in S.

Table 1. Selection of Change Operations on Process Schemas

”later” than originally intended.

Consider the example depicted in Fig. 4. Instance I(cf.

Fig. 4b) is not compliant with new type schema S0since B

has state Running. Basically, if possible from a semantic

point of view, at instance level Xcan be inserted at other

positions as well such that Ibecomes compliant again. As-

suming that we keep Aas ”left anchor” for the insert opera-

tion, possible ”right anchors” for the insertion are Cand D

respectively. First consider insertion of Xbetween Aand

C(¬): When applying ∆1

I(S)to Ias instance-specific ad-

justment, we obtain instance schema S1

I. The bias between

Iand S0is captured by ∆1

I(S0)and reflects an insertion

with ”relaxed” insertion position.2Schema S2

Iresulting

from the insertion of Xbetween Aand Dis depicted in

Fig. 4b (). Obviously, the question is which of the two

schemas we shall prefer. The premise of this paper is to

enable migration of non-compliant instances such that they

can benefit from further optimizations. In general, the ap-

plication of further modifications at type level will be sup-

ported best when keeping the instance-specific schemas ”as

close as possible” to the type schema version they are mi-

grated to. Intuitively, S1

Iis ”closer” to S0when compared

to S2

I. To define ”as close as possible” we can use structural

distance dS as introduced in Section 2.

Basically, it is also possible to use ”left anchors” other

than Afor realizing instance-specific adjustments. Consider

Fig. 4b(®): When compared to S0the order between Xand

Bhas been reversed for Fig. 4b(®), whereas for Fig. 4b(¬)

Xand Bare ordered in parallel. Thus in Fig. 4b(¬), still

Xcan be started before Bis finished, what is not possible

in Fig. 4b(®). Hence, the instance schema from Fig. 4b(¬)

is ”closest” to S0. – Generally, we want to answer: how to

determine instance-specific adjustments ∆I(S0)such that I

2i.e., Xis not inserted between Aand B, but between Aand the first

”possible” successor of B.

is compliant with SIwhere S0[∆I(S0)> SI3and distance

between instance schema SIand modified type schema S0

dS(SI, S0)becomes minimal?

Strategy 3: History-Based Adjustment History-based ad-

justment is mainly applied for delete operations: e.g., an

instance is not compliant if the activity to be deleted is

running or completed. Basically, deletions of activities ”in

the past” of process instances are enabled by adjusting in-

stance traces4. Assume that activity Xis to be deleted from

schema Sresulting in schema S0. Regarding instance Ion

S,Xhas been already completed and respective start

and/events for Xwere logged in trace σS

I. Thus σS

cannot be ”replayed” on S0and compliance for Ion S0

is not fulfilled. However, when discarding respective trace

entries of Xfrom σS

I, the modified trace can be replayed

on S0and thus Ibe migrated. Entries of deleted activities

are physically not deleted from the exeuction traces, but are

only flagged within the trace to preserve traceability. Strat-

egy 3 does not harm soundness of the affected instances.

Strategy 4: Global-Adjustment Basically, adjusting

schema changes may be done at both, the process type

and the process instance level. Assume that process type

schema Sis transformed into another type schema S0by

change ∆S. Let further Ibe an instance on Swhich is not

compliant with S0. If ∆Sis adjusted to ∆0

Sat type level

(i.e., transforming Sinto S00 instead of S0), more instances

running on Sbecome compliant with S00 afterwards. Gener-

ally, more instances will become compliant with a changed

type schema, if added activities are inserted as late as pos-

sible. Most important, all data dependencies imposed by

the process type schema and the intended change must be

fulfilled. For the given example this implies that activities

3An interesting question arises in the context of data flow changes ac-

companying insert operations as, for example, depicted in Fig. 3

4For practical scenarios from the automotive domain in which such

non-compliant deletions are required, we refer to [6].





a) Process type schema S:

b) Unbiased instance I on S:

Modified process type schema S`:

ΔS= <insert(S,X,A,B),>

Δ1I(S‘) = <move(S, X, A, C)>

I non-compliant with S‘

Biased instance I on S‘:

+ +

Completed

Activity +AND-Split/Join

Δ3I(S‘) = <move(S, X, B, C)>



Δ4I(S‘) = <move(S, X, B, C)>



Δ2I(S‘) = <move(S, X, A, D)>

+ + D

Running

S1I

S3I

S4I

S2I

S[ΔS>S‘

Activated

Figure 4. Strat. 2: Instance-Specific Adjust-

ment (Example)

X and Y can be inserted ”later in the type schema” (i.e.,

as ”close” to the process end as possible) as long as the

data dependency between them is fulfilled. Since a pro-

cess type schema might contain more than one process end

node, the formalization of ”later in a process graph” should

not be based on structural properties; i.e., we want to be in-

dependent of a particular process meta model. As for state

compliance, we use process traces in this context. Due to

lack of space we omit a formalization here. Finally, when

inserting two or more data-dependent activities, additional

constraints must hold. More precisely, it cannot be allowed

to move the insertion position of the writing activity ”be-

hind” the reading activity since the resulting schema would

not be correct anymore.

4 Instance-Specific Adjustment of Instances

Bias-based strategies as introduced in Sect. 3 are promis-

ing approaches for treating non-compliant instances. As-

sume that instance Ion Sis not compliant with modified

type schema version S0(S[∆S> S0). However, if type

change ∆Scan be locally adjusted to ∆I(S0)such that I

becomes compliant with instance schema S|∆I(S0)> SI,

Ican be relinked to S0using bias ∆I(S0)(Strategy 2). As

motivated by Fig. 4, different adjustments of ∆Sare con-

ceivable. However, we are particularly interested in the

adjustment which results in the lowest structural distance

dS(S0, SI)between instance schema SIand type schema

S0(cf. Sect. 2). In this section we show how to automat-

ically derive such optimal instance-specific adjustment for

unbiased process instances. In the example from Fig. 4, op-

timal instance-specific adjustment for operation ”insert ac-

tivity Xbetween Aand B” can be achieved if Xis inserted

between Aand the next possible successor of Awhich has

not been started yet. Theorem 1 captures this aspect:

Theorem 1 (Optimal Instance-specific Adjustment)

Let S = (N, E, ...) and S’ be two process schemas and let

∆S=<insert(S, X, A, B)>describe an insertion which

transforms S into S’; i.e., S[∆S> S0. Let further I ∈ I5be

an instance running on S for which NSI(B)∈ {Running,

Completed}holds for the state of activity B; i.e., I is not

compliant with S’. We define instance-specific adjustment

∆I(S0)as follows:

∆I(S0)= move(S’,X,A,C) with

C∈nextNonStartedSucc(S’,I,B)6where

nextNonStartedSucc: S × I × N7→ 2Nwith

nextNotStartedSucc(S’,I,n) =

{n∈succ*(S’,X) 7|NSI(n)6∈ {Running, Com-

pleted}

∧(6 ∃ n’: NSI(n0)6∈ {Running, Completed}

∧n∈succ*(S’,n’) }

Then: Iis compliant with SIwhere S0[∆I(S0)>SIand

dS(S’,SI) = min{dS(S’, ˜

SI)|S0[˜

∆I(S0)>˜

SIwith I com-

pliant with ˜

SI}

We prove Theorem 1 in a technical report [9]. Its ad-

justment strategy is applicable for single insert operations

with accompanying data flow change operations as well.

Consider, for example, Fig. 3 where the insertion of ac-

tivity Xat schema level is accompanied by insertion of a

read data edge between activity Xand data element d. If

we adjust the insert operation at instance level to ∆I(S0)=

<move(S’,X,A,C)>according to Theorem 1, data flow re-

mainsl correct. This holds for all possible single insert op-

erations with accompanying data flow operations. Accom-

panying data flow operations for single activity insertions

can only be insertions of read data edges for the inserted

activity. Correct supply of the corresponding read accesses

at schema level requires that the left anchor of the newly

inserted activity or one of its predecessors writes the data

element accordingly. Since the left anchor as well as all

its predecessors still precede the inserted activity after ad-

justing the change at instance level, the read access will be

correctly supplied.

So far, insert and delete operations have been discussed.

Regarding insert operations instance-specific adjustments

can be applied (cf. Strategy 2), whereas for delete op-

erations, ”adjustment” of the execution history of the af-

fected instance might relax compliance issues (cf. Strategy

3). What about move operations? First, moving an activity

5Idenotes the set of all instances

6In connection with parallel or alternative branchings more than one

successor of B can be the ”next non-started activity”. In this case one of

them is chosen arbitrarily or the user is asked to make a choice.

7succ*(S, X) returns all direct and indirect successor activities of aci-

tivity X in S.

can be logically seen as combination of a delete and insert

operation. Second, regarding state compliance, an activ-

ity cannot be moved if it has already been started or com-

pleted. Further it cannot be moved in front of an activity

which has been already started or completed. Thus we dis-

tinguish between the following cases: if an activity shall be

moved, which has been already started or completed, we

apply history-based adjustment (Strategy 3). If it shall be

moved to a position before an already started or completed

activity, we apply instance-specific adjustment (Strategy 2).

When using ADEPT technology and AristaFlow BPM

Suite in practice, it has often become necessary to apply

more than one (i.e., multiple) change operation to conduct

an intended change at process type level. Assume, for ex-

ample, that a set of activities is inserted while other ones

are deleted at same time. The challenge then is to de-

termine instance-specific adjustments in case of multiple

change operations. We illustrate the basic idea of instance-

specific adjustments for multiple change operations by ex-

ample of multiple insertions: For each insert operation ap-

plied to schema Sa corresponding move operation is gen-

erated based on Theorem 1 if necessary; i.e., if I is not com-

pliant regarding this particular insert operation. In Fig. 5,

Iis not compliant with S0. Hence for both insert oper-

ations (i.e., of Xand Y) corresponding move operations

are applied to realize an instance-specific adjustment (bias).

However, we have to take special care of multiple inser-

tions in connection with data flow changes: assume that for

the change operations depicted in Fig. 5 accompanying data

flow changes are applied, i.e., new data element dis inserted

with write data edge from Yto dand read access from Xon

d. At schema level, these data flow change operations are

correctly applicable since Yis a predecessor of Xin any

case. However, at instance level, after adjusting instance I

as shown in Fig. 5, it is not guaranteed that data element d

is written by Ybefore being read by X, since Yis no pre-

decessor of Xfor Ion S0(specifically Xand Yare ordered

in parallel). Thus the correct data supply of Xby Yis not

ensured at instance level.

Thus, the optimality criterion set out by Theorem 1 has

to be modified to conditional optimality; i.e., we have to de-

termine instance-specific adjustment ∆0

I(S0)in such a way

that the order relation between writing activity Xand read-

ing Yis preserved. This can be accomplished by inserting

an additional sync edge between Xand Y(this is possi-

ble since they are ordered in parallel) leading to instance-

specific schema SI0. We will elaborate on conditional opti-

mality in future work.

5 Strategy Evaluation

Assume that instances IS:= {I1, ..., In}are running on

type schema Swhich is then transformed into schema S0

a) Process Type Schema S:

b) Instances on Schema S:

Process Type Schema Sb:

ΔS= < insert(S,X,C,E).

insert(S, Y, A, B)>

+ +

Activity States: Completed

Activity

XXOR-Split/Join

Control edge

Sync edge

ΔI= < insert(S,X,C,F)>

ΔI(S)= <>

ΔI(S‘)= < move(S,X,C,F), move(S, Y, A, D)>

sD(S‘, S‘I) = 5



Skipped



Activated

Figure 5. Instance-specific Adjustment

(S[∆S>S’). Assume further that a subset of the running in-

stances is not compliant with S’. In this section we want to

evaluate the quality of the different strategies introduced in

Section 3 for treating such non-compliant instances. On the

one hand, the quality of a strategy is related to the number

of instances which can be migrated in addition to the num-

ber of compliant instances (i.e., instances without applying

any strategy). On the other hand, we also have to consider

the ”price” to be paid for each additionally migrated in-

stance I. The latter is reflected by the distance between

instance schema SIand S0after migration. One metric

for measuring structural distance between process schemas

SI:= (NI, CtrlEI, ...)and S0= (N0, CtrlE0, ...)is pro-

vided by structural distance dS(S0, SI)as introduced in

Sect. 2. However, this metrics can be only applied if SI

and S0have same activity set; i.e., there exists a bijective

mapping between NIand N0or – in other words – activ-

ity coverage between SIand S0is 100%. Actually, activity

coverage can be also used to compare process schemas, for

example, in the context of Strategy 1 (cf. Section 3), which

leads to NI6=N0in most cases. Finally, process schemas

SIand S0can be also compared based on the number of

high-level operations necessary to transform SIinto S0.

Formula (1) enables evaluation of the quality of Strate-

gies 1 to 4 with SC(s, S0,IS) :=

#mIs−PI∈ISP S(SI, S0)−PI∈ISAC(SI, S0)−PI∈ISSD(SI, S0)

|IS|

(1)

Specifically, #mIsdenotes the number of migratable in-

stances when applying strategy s. Note that we can com-

pare the application of a strategy with the case of applying

no strategy. Then #mIsreflects the number of instances,

which are compliant with modified type schema version S0

anyway. The remainder of the formula quantifies the side-

effects when applying one of the strategies. If we do not

apply any strategy, the formula yields SC(”none”, S’, IS)

Metric M Formula Preconditions

Process Similarity PS(SI,S’):= distance(SI,S0)

|NI|+|N0|−|NI∩N0|

Activity Coverage AC(SI,S’):= |NI∩N0|

|NI|+|N0|−|NI∩N0|

Structural Distance SD(SI,S’):= dS(SI,S0)

|NI|AC(SI,S’) = 100%

adistance(SI,S’)denotes the high-level operations applied for transforming SIinto S0.

Table 2. Metrics for Comparing Process schemas

=#mIs

|IS|; i.e., the number of compliant instances divided

by the number of all instances. For Strategy 1, for ex-

ample, which enables migration of all instances (”always-

migrate”), #mIs=|IS|and thus SC = 1 holds.

Consider the scenario depicted in Fig. 6. Type schema

Sis transformed into S0by inserting activity Xbetween

Aand Band by deleting C. Assume that 500 instances

are running based on Sand that they are clustered along

their current instance state. Assume further that for in-

stances I1, ..., I100, activity Ais completed and Bis ac-

tivated, for instances I101, ..., I200 activities Aand Bare

completed and Cis activated, and for I201, ..., I500 activi-

ties A,B, and Care completed whereas Dis either acti-

vated or running. Then instances I1, ..., I100 are compliant

with S0, whereas I101, ..., I500 have progressed too far; i.e.,

they are non-compliant with S0. Without any further treat-

ment of the non-compliant instances the quality turns out as

SC(”none”,S’,IS) = 0.2.

The result of applying our four strategies is illustrated

by Fig. 6. First, Strategy 1 (Always-Migrate) is applied

to instances I101, ..., I500. Instances I101, ..., I200 are not

compliant with respect to the insertion of X, but they are

compliant with respect to the deletion of C. Hence, when

applying Strategy 1 to I101, ..., I200, the insert operation

has to be neutralized, which can be expressed by a delete

operation on S0(i.e., to delete Xon S0). Contrary, in-

stances I201, ..., I500 are not compliant with respect to both

changes. Hence, the deletion of Chas to be neutralized as

well by a respective insert operation (cf. Fig. 6).

As summarized in Fig. 2, some of the strategies are only

applicable in the context of certain change operations; i.e.,

Strategy 2 for insert operations and Strategy 3 for delete

operations. Type schema change ∆Scaptures an insert as

well as a delete operation. Hence, we have to combine

Strategies 2 and 3 in order to adequately treat non-compliant

instances by bias-based local adjustment. Regarding in-

stances I101, ..., I200, the delete operation can be applied

(no history-based adjustment). However, the insert opera-

tion has to be adjusted to a move operation as depicted in

Fig. 6. Regarding I201, ..., I500 we have to apply history-

based adjustment for the deletion of Cas well (i.e., logi-

cally discarding the entries of Cin traces of I201, ..., I500).

Finally, Fig. 6 shows an example for applying Strategy 4

(Global Adjustment); i.e., by inserting activity Xbetween

Cand Dinstead of inserting it between Aand B, all in-

stances for which Dhas not been started yet become com-

pliant with S00 (e.g., I1, ..., I450). Fig. 6 also depicts quality

estimations for Strategies 1, 2, and 4 as depicted in Fig. 6.

Strategy 1: Always Migrate

Instances

I101, …, 200 A B D

Instances

I201, …, 500

ΔIj = <delete(S‘,X)>, j = 101, …, 200

A B C D

ΔIj = <delete(S‘,X), insert(S, C, B, D)>, j = 201, …, 500

Strategy 2: Local Adjustment

Instances

I101, …, 500

ΔIj = <move(S‘,X,A,D)>, j = 101, …, 500 A B D

+ +

A B C D

A B C D A X B D

a) Process Schema S: S`:

ΔS= < insert(S,X,A,B), delete(S,C)>

A B X D

A B C D

Strategy 4: Global Adjustment Δ‘S= < insert(S,X,C,D), delete(S,C)> S‘‘:

SC(1,S‘,I)=1.31

SC(2,S‘,I)=1.5

SC(4,S‘,I)=1.9

Figure 6. Application of Different Strategies

Aside this quantitative reflections, applicability of the

proposed strategies has to be discussed in connection with

advanced issues such as loops and semantic constraints on

the one side and its application-dependency on the other

side. Commenting on the latter, Strategy 1, for example,

can be applied when no other strategy seems to be conceiv-

able. Definitely, this might be useful in the medical domain,

where there is often no time to roll-back an instance first

and then migrate it, but rather let a patient benefit from fur-

ther process optimizations immediately. Instance-specific

and global adjustments exploit the flexibility degrees pro-

cess schemas offer anyway. This is supported by the emer-

gence of new paradigms such as declarative modeling.

When Strategy 1 is applied within a loop, within the next

iteration the change would become effective. However, we

have to ”take back” the instance-specific bias for subsequent

iterations and mark this within the assoicated change op-

eration. We will further investigate on the connection of

loops with the other strategies in future work. Regarding

semantic constraints, they might yield useful information

for the application of the different scenarios. One example

is global adjustment which might be applicable without vi-

olating soundness, but harming some semantic constraints.

6 Related Work

Many approaches deal with soundness issues in adaptive

PAIS [12, 14, 8, 11]. The kind of applied correctness cri-

terion often depends on the used process meta model. A

discussion and comparison of the particular correctness cri-

teria is given in [8]. Aside from the applied correctness cri-

teria, mostly, these approaches do neither address the ques-

tion of how to increase the number of migratable instances

nor how to deal with non-compliant instances. Frameworks

for process flexibility have been presented in [7, 13]. In

[7], different paradigms for process flexibility and related

technologies are described. [13] provides change patterns

and evaluates different approaches based on them. How-

ever, [7, 13] do not address the treatment of non-compliant

instances. For treating non-compliant instances, different

strategies have been proposed in literature (cf. Sect. 2).

Partial rollback has been suggested [11]. Applying this pol-

icy to instances which have already progressed too far re-

sults in a compliant state. Generally, instance rollback is

accomplished by compensating activities [11]. An obvious

drawback is that it is not always possible to find compen-

sating activities, i.e., to adequately rollback non-compliant

instances. Apart from this, rollback is mostly connected

with loss of work and thus not well accepted by users. An

alternative is delayed migration of non-compliant instances.

Even if instance Ion Sis not compliant with S0within the

actual iteration of a loop, a delayed migration of Ito the

new change region is possible when another loop iteration

takes place. Alternatively, the number of non-compliant in-

stances can be kept smaller by relaxing the underlying cor-

rectness criteria. Basically, the strategies presented in this

paper can be combined with any of the above strategies as

well. For example, it is possible to first reduce the number

of non-compliant instances by applying relaxed compliance

[10], then apply one of the strategies provided in this paper,

and try to treat the remaining instances by partial rollback.

Further the strategies are applicable to any other flexible

process approach using change operations and compliance.

7 Summary and Outlook

In this paper we provided four strategies to cope with

non-compliant process instances that are based on adjust-

ments either of process changes at type schema level or in-

stance level. Alternatively, ”adjustments” of the instance

traces are helpful in some cases. All strategies preserve

soundness of the running instances after relinking them to

the new type schema version. In particular, we elaborated

the migration of instances by locally adjusting the type

schema change at instance level; e.g., moving the inser-

tion position such that the instances become compliant with

the resulting instance-specific schema. How respective ad-

justments can be determined such that the distance between

instance-specific schema and modified type schema version

becomes minimal has been shown as well. When consider-

ing real-world migration scenarios in domains like health-

care, automotive engineering or electricity supply, we could

experience the high practical relevance of the presented re-

search. In future work, we will investigate the interplay

between relaxing compliance, treating non-compliant in-

stances, and ensuring semantic process constraints.

References

[1] F. Casati, S. Ceri, B. Pernici, and G. Pozzi. Workflow evolu-

tion. Data and Knowl. Engineering, 24(3):211–238, 1998.

[2] J. Dehnert and A. Zimmermann. On the suitability of cor-

rectness criteria for business process models. In Int’l Confer-

ence Business Process Management, pages 386–391, 2005.

[3] C. Ellis, K. Keddara, and G. Rozenberg. Dynamic change

within workflow systems. In ACM Conf. on Organizational

Computing Systems, pages 10–21, 1995.

[4] C. Li, M. Reichert, and A. Wombacher. On measuring

process model similarity based on high-level change oper-

ations. In Int’l Conf. on Conceptual Modeling, pages 248–

264, 2008.

[5] L. Ly, S. Rinderle-Ma, and P. Dadam. Design and verication

of instantiable compliance rule graphs in process-aware in-

formation systems. In Int’l Conf on Advanced Information

Systems Engineering, pages 9–23, 2010.

[6] D. M¨

uller, M. Reichert, and J. Herbst. A new paradigm for

the enactment and dynamic adaptation of data-driven pro-

cess structures. In Int’l Conf. on Advanced Information Sys-

tems Engineering (CaISE’08), pages 48–63, 2008.

[7] N. Mulyar, M. Schonenberg, R. Mans, N. Russell, and

W. van der Aalst. Towards a taxonomy of process flexibility.

Technical Report BPM-07-11, BPMcenter.org, 2007.

[8] S. Rinderle, M. Reichert, and P. Dadam. Correctness criteria

for dynamic changes in workflow systems – a survey. Data

and Knowledge Engineering, 50(1):9–34, 2004.

[9] S. Rinderle-Ma and M. Reichert. Adjustment strategies for

non-compliant process instances. Technical Report UIB-

2009-06, Ulm University, 2009.

[10] S. Rinderle-Ma, M. Reichert, and B. Weber. Relaxed com-

pliance notions in adaptive process management systems. In

Int’l Conf. on Conceptual Modeling, pages 232–247, 2008.

[11] S. Sadiq, O. Marjanovic, and M. Orlowska. Managing

change and time in dynamic workflow processes. IJCIS,

9(1&2):93–116, 2000.

[12] W. van der Aalst and T. Basten. Inheritance of workflows:

An approach to tackling problems related to change. Theo-

ret. Comp. Science, 270(1-2):125–203, 2002.

[13] B. Weber, M. Reichert, and S. Rinderle-Ma. Change pat-

terns and change support features - enhancing flexibility in

process-aware information systems. Data and Knowledge

Engineering, 66(3):438–466, 2008.

[14] M. Weske. Business Process Management: Concepts, Lan-

guages, Architectures. Springer, 2007.