On Design Principles for Realizing Adaptive Service Flows with BPEL [original]

On Design Principles for Realizing

Adaptive Service Flows with BPEL

Manfred Reichert1and Stefanie Rinderle2

1Information Systems Group, University of Twente, The Netherlands

[email protected]

2Dept. Databases and Information Systems, Ulm University, Germany

[email protected]

Abstract: Web servicetechnologyoffers apromising approachfor realizingenterprise-

wide and cross-organizational business applications. With the Business Process Exe-

cution Language for Web Services (BPEL, also known as WS-BPEL or BPEL4WS)

a powerful language for the process-oriented composition and orchestration of Web

services exists. However, BPEL flow specifications tend to be too complex, and cur-

rent BPEL engines do not provide the flexibility needed to cover the broad spectrum

of business processes we have to deal with in practice. Neither ad-hoc deviations

form the pre-specified BPEL schema (e.g., to add or move activities for single flow in-

stances) nor the propagation of BPEL schema changes to a collection of flow instances

have been supported by BPEL engines yet. This limits their applicability to only well-

structured, rigid service flows. In this paper we address fundamental issues, which

arise when enriching BPEL engines with dynamic change capabilities. We focus on

the question how such changes can be realized in a correct and consistent manner and

which prerequisites must be met in this context. In particular, we restrict BPEL to a

reasonable subset of language elements in order to decide on these fundamental ques-

tions. By offering flexibility and adaptability in a controlled and reliable way the so

promising Web Service technology will broaden its application scope significantly.

1 Introduction

Today there is a high need for active coordination of the various, distributed tasks nec-

essary to perform enterprise-wide business applications. Service-oriented architectures

offer a promising approach in this context [WCL+05]. Usually, they provide a framework

for specifying, implementing, and registering application services as well as for compos-

ing them in a process-oriented manner. The latter enables stateful interactions among the

services and provides the basis for reliable process orchestration. In this context, the Busi-

ness Process Execution Language for Web Services (BPEL, also known as WS-BPEL or

BPEL4WS) has emerged as de-facto standard for implementing processes based on (Web)

services [vDt+05, OAS06]. Systems like Oracle BPEL Process Manager, IBM WebSphere

Process Server, and Microsoft BizTalk Server support BPEL, thus illustrating the practical

relevance of this process description language. Though intended as a language for con-

Weske, M.; Nüttgens, M. (Hrsg.): Proc. EMISA 2006 - Methoden, Konzepte und Technologien für die Entwicklung

von dienstbasierten Informationssystemen, Hamburg, Oktober 2006, GI Lecture Notes in Informatics, LNI P-95,

2006, pp. 133-146

necting web services, it can be expected that in near future a wide variety of process-aware

information systems (PAIS) will be realized using BPEL [vDt+05].

Whilst BPEL is an expressive language, it is by far too complex to realize more advanced

process support functions. In particular, the aforementioned BPEL engines do not provide

the flexibility and dynamism needed to cover the broad spectrum of business processes we

can find in todays organizations. Neither ad-hoc deviations from the pre-planned service

flow (e.g., to add, shift or delete activities in order to deal with an exceptional situation)

nor the propagation of a business process change to a collection of flow instances have

been supported yet. This, in turn, requires from users to bypass the system in exceptional

cases or prohibits already running flow instances from being adapted to an optimized busi-

ness process. In many domains, however, PAIS will not be accepted by users when rigidity

comes with them. Creating service-oriented applications without a vision for adaptive pro-

cess management, therefore, is shortsighted and expensive. Indeed, insufficient flexibility

has been a primary reason why workflow technology failed in many process automation

projects in the past. Obviously, similar problems will result for BPEL-based process en-

gines if dynamic flow changes are prohibited a priori by a bad language design.

Barriers on the way towards adaptive BPEL flows are the complexity of BPEL and the

missing formal semantics of this language. Though several approaches exist in this con-

text (e.g., [Mar05, OvB+05, RRD04a]), current formalizations and verification methods

are incomplete (i.e., focussing on selected BPEL language elements only) and are not stan-

dardized. In particular, one will not be able to reason about the correctness of dynamic flow

changes if there exist no formal basis and no mechanism for reasoning about correctness

issues. In this paper we sketch how existing concepts from the area of adaptive processes

(see [RRD04b] for an overview) can be applied to restrict and configure the BPEL lan-

guage in a way such that it becomes a candidate for realizing adaptive flows. Due to lack

of space we mainly focus on design principles and omit formal issues.

Section 2 summarizes background information related to the modeling of BPEL flows.

Based on this, Section 3 introduces guidelines for a corresponding flow execution model.

Using this model, Section 4 deals with the question how to check whether a given BPEL

flow instance is compliant with a modified flow schema or not. Section 5 copes with the

state adaptations becoming necessary in this context. Finally, Section 6 discusses related

work and Section 7 concludes with a summary and an outlook.

2 Background Information

BPEL uses an expressive meta model for creating XML-based descriptions of business

processes based on the interactions between the process and its partners. In the following

we omit XML specifications and use graphical illustrations instead. In a BPEL flow, the

interaction with each partner occurs through web service interfaces. Process activities can

invoke service operations of partners synchronously, or they may receive messages from

service invocations of partners and reply to them asynchronously later. BPEL provides a

variety of possibilities to describe the desired flow logic. For example, Fig. 1 shows a

...

<flow>

<links>

…

</links>

activity A

activity B

…

activity E

joinCondition = “(L_BE OR L_DE) AND L_FE”

activity F

activity G

</sequence>

</flow>

...

flow

d > 0

d ≤ 0

Figure 1: Example of a BPEL flow schema (modeled in a graph-like fashion)

BPEL flow schema which has been modeled in a graph-like fashion, i.e., the flow logic is

described as a network of activity nodes and (control) links. For such a graph-based BPEL

flow, a variety of configuration facilities exist, like the assignment of transition conditions

to (control) links (i.e., predicates on flow variables), and the definition of activity join

conditions. However, the flow from Fig. 1 can be also modeled in a more block-oriented

fashion as depicted in Fig. 2. This flow schema is based on structured activities (sequence,

flow, switch) and two links which synchronize activities from parallel branches. Generally,

structured activities can be nested. In our example, the switch activity is contained in a

sequence activity, which itself is surrounded by a flow activity (representing parallelism).

flow

seq

d>0

d ≤ 0

switch

seq

Figure 2: BPEL flow from Fig. 1 modeled in a block-like fashion

Generally, it is possible to mix both modeling styles by having links crossing the bound-

aries of structured activities. On the one hand BPEL provides high expressiveness and

many ways to express the same thing; on the other hand this aggravates flow modeling,

analysis and verification (see [RRD04a] for details). In order to reduce this complexity and

to be able to reason about correctness properties of BPEL flow specifications, in [RRD04a]

we have introduced a classification for BPEL flow schemes. In this work, we have also

shown that block-structured modeling, together with the controlled use of links, offers ad-

vantages when compared to the graph-like modeling style. Note that such considerations

become necessary when reasoning about the correctness of flow schema changes. How-

ever, for the rest of this paper we abstract from issues related to schema correctness, and

assume that changes of BPEL flow schemes are handled in a correct manner. Instead we

focus on the propagation of such flow schema changes to running flow instances.

3 Designing an Execution Model for BPEL Flows

A prerequisite for dynamically adapting the structure and state of BPEL flow instances

is the provision of a formal semantics. It constitutes the basis for both the correct exe-

cution of BPEL flow instances and the correct adaptation of their states when applying

dynamic changes. Regarding flow instance changes it must be also possible to quickly

decide whether a given flow instance or a collection of flow instances is compliant with

the modified flow schema, and may therefore be migrated to it. In the following we dis-

cuss guidelines for the design of such an (adaptive) flow execution model for BPEL. Our

considerations are based on a previous survey on formal models for adaptive process man-

agement(cf. [RRD04b]). Due to lackof space wefocus on fundamentalissues and exclude

more advanced BPEL process patterns (e.g., scopes and exception handlers).

We distinguish between different states a single BPEL activity (i.e., a single process step)

may run through. Initially, an activity has state NotActivated. It will change to Activated

(i.e., the activity becomes enabled) if all preconditions for executing the activity are met.

When starting it (e.g., by invoking a Web Service operation or by receiving a message from

a partner) we obtain activity status Running. At successful termination activity status

passes to Completed whereas processing failures result in status Failed. Finally, status

Disabled represents activities of non-selected paths (e.g., activities whose execution has

been skipped due to a dead path elimination or which belong to a non-selected branch of

a switch block). In addition, for each instance Ian execution history HI=< e0, ..., ek>

is kept. It logs events related to the start and termination of flow activities.

A flow execution model for BPEL must provide rules for initializing activity states when

creating new flow instancesand for adapting these states when activities are started or com-

pleted. More precisely, these rules must enable the runtime system to decide in which flow

states a certain activity can be activated, and to determine the correct follow-up state of the

flow instance when activities are completed. To achieve this, for basic as well as structured

activities a well-defined operational semantics is required. For example, an adequate rep-

resentation of both activity and link states – also denoted as activity / link markings in the

following – is needed. Generally, different options exist in this context. The first one uses

only one type of control token passing through each flow instance (True-Tokens). An alter-

native is to use two types of tokens (True- and False-Tokens). Simplistically, True-Tokens

trigger activities that are to be executed next and False-Tokens describe disabled activities.

Flow description formalisms which solely use True-Tokens include Petri-Nets [RRD04b].

Approaches which additionally use False-Tokens usually preserve the markings of already

passed regions (except for loop backs) and explicitly mark disabled activities. These ap-

proaches can be further divided according to the way they represent the tokens. One option

is to gain them from execution histories (which log events like activity start / completion.

Alternatively, (model-inherent) activity markings, representing a consolidated view on ex-

ecution logs, can be used [RRD04b].

As discussed in [RRD04b] the use of a flow execution model with True-/False-Tokens

offers the best perspectives with respect to dynamic process changes. A corresponding

example is depicted in Fig. 3. As can be easily seen from this figure, activity markings

do not only indicate whether an activity is currently activated or disabled, but also provide

a consolidated view on previous instance execution; i.e., on the execution history of the

respective instance. As we show in the following this is exactly what we need to efficiently

check compliance of a flow instance with a modified BPEL flow schema and to automati-

cally adapt markings of this instance when migrating it to the new schema version.

I on S:

Disabled

Completed

Running

Activated

sequence flow

link

Activity markings / states:

Link markings / states:

False_signaled

True_signaled

tc = true

tc = false

Figure 3: BPEL flow instance with activity markings (True-/False semantics)

In principle, BPEL is coherent with this way of representing activity states. However, in

our context we need a more formal definition of the underlying operational semantics as

currently provided by the BPEL specification. In any case, BPEL shows a good potential

for satisfying the following basic properties needed for the support of adaptive flows:

1. The flow execution model must offer different kinds of activity markings to distin-

guish between executed and disabled flow paths (True-/False-Semantics).

2. Internal activity states must be reflected by the flow execution model. For example,

itmust be possibleto distinguish betweenenabled activitiesandalreadystarted ones.

This is crucial for checking compliance of a flow instance with a modified schema.

3. The markings of already passed regions should be (logically) preserved (except loop

backs); they provide a consolidated view on the previous instance execution.

4. The flow execution model must provide precise execution and marking rules, which

state under which marking an activity can be executed and which new marking re-

sults when completing it. Such a flow execution model should be based on a graph-

based representation of BPEL schemes.

Fig. 3 shows a simple BPEL flow instance – a sequence block with an embedded flow

activity as well as embedded basic activities – together with its current activity and link

markings. Note that this representation already satisfies the execution properties 1–3 men-

tioned above. At this point it is important to mention that activity/link markings only rep-

resent a logical view on the respective flow instance. How these markings are internally

represented, how they are physically stored, and which optimizations are conceivable in

this context depends on the concrete BPEL implementation and is outside the scope of this

paper. The same applies to the concrete set of marking and execution rules.

4 A Correctness Criterion for Changing BPEL Flow Instances

We now deal with the challenge to propagate changes of a BPEL flow schema to corre-

sponding flow instances. The ambition must be to preserve correctness of these instances

when dynamic changes are carried out. We need adequate criteria to decide whether an

instance Iis compliant with a changed BPEL schema; i.e., whether the change can be

correctly propagated to Iwithout causing errors (like deadlocks or improperly invoked

services). For this we need an adequate correctness criterion which does not needlessly

exclude a flow instance from being migrated to a new schema version. Furthermore, it

must be ensured that correctness can be efficiently checked by the BPEL engine.

4.1 Preliminaries

We assume that BPEL schema changes are correctly accomplished. However, this is not

sufficient to guarantee a consistent execution behavior of flow instances when migrating

them to the new BPEL schema version. Additionally, we must consider instance states. To

illustrate the problems resulting from an uncontrolled migration consider the example from

Fig. 4. The BPEL schema Sfrom Fig. 4a) represents a sequence consisting of activities

A, B and C. Assume that Sis correctly transformed into S0by adding activities X and Y as

well as a data dependency between them – Activity Y reads variable d which is written by

the preceding activity X (cf. Fig. 4a). Assume further that these changes are propagated

in an uncontrolled way to the flow instances from Fig. 4c) (currently running on S).

Concerning instance I1no problem would occur since its execution has not yet entered

the region affected by the change (activity A is still running). Uncontrolled migration of

instance I2, however, would cause malfunctions. First, an inconsistent state would result

– B is already running though its (new) predecessor X (on S) has not been completed.

Second, the newly inserted activity Y might be invoked though variable d has not been

written (by X). For flow instance I3migration would be possible. When doing so, however,

activation of B has to be undone and the added activity X be activated instead. – In the

following we do not distinguish between changes of single flow instances (e.g., to deal

with exceptions) and adaptations of a collection of flow instances (e.g., to deal with a

process type change). Instead we focus on fundamental issues related to dynamic changes

of BPEL flow instances and sketch how they can be addressed.

Our previous example has demonstrated that the applicability of a dynamic flow change

Completed

Running

Activated

A X BYC

change

AB C

sequence sequence

Change

Flow schema S

a) Flow schema S

= {serialInsert(S, X ,A, B), serialInsert(S, Y, B, C), insertVariable(S, d, …),

insertDataLink(S, X, d, write), insertDataLink(S, Y, d, read) }

AB C

c) Flow Instances on S

AB C

Execution history of I1: START(A)

Execution history of I2: START(A), END(A), START(B)

Execution history of I3: START(A), END(A)

Figure 4: BPEL flow schema and related flow instances

depends on the current flow state as well as on the kind of changes being applied. Let Ibe

a flow instance with BPEL schema S; assume that Sis transformed into another ”correct”

BPEL schema S0by applying change ∆. Then two fundamental issues arise:

1. Can ∆be correctly propagated to flow instance I, i.e., without causing errors and

inconsistencies? If yes, we denote Ias compliant with respect to S0.

2. Assuming Iis compliant with S0, how can we smoothly migrate it to S0such that its

further execution can be based on this new BPEL schema? Which state adaptations

(e.g., enabling/disabling of activities) become necessary in this context?

While the first issue concerns pre-conditions on the current state of I, the second one is

related to post-conditions that must be satisfied after propagating the change. In any case

we have to provide an efficient solution which enables automatic and correct compliance

checks as well as automated instance migrations.

4.2 A General Correctness Criterion

In [RRD04c] we have introduced a general correctness criterion, which is independent of

the used process description formalism and which allows us to argue about the correctness

of dynamic flow changes. In more detail, this criterion enables us to decide whether a

given flow instance can be migrated to the modified schema or not (so-called compliance).

In addition, we provide automated procedures to determine the correct follow-up state of

compliant flow instance resulting after their migration.

Simplistically, flow instance Iwould be compliant with a (modified) flow schema S0if

Icould have been executed according to S0as well, and would have produced the same

effects on flow state and variables. Trivially, this will be always the case if Ihas not yet

entered the region affected by the flow schema change. Generally, we need information

about previous flow execution to decide on this property and to determine correct follow-

up states for the (compliant) flow instances to be migrated. For this purpose, we can make

use of the execution history which is kept for each flow instance (cf. Fig. 4c) independent

of the applied flow description language. Usually, this history logs events related to the

start / completion of flow activities. Obviously, flow instance Iwith history HIwill be

compliant with S0(and therefore be able to migrate to this schema) if HIcan be produced

on S0as well. Consequently we then obtain a correct new state of flow instance Ion

schema S0by replaying all events from HIon S0in chronological order. Taking our

example from Fig. 4 this holds for I1and I3, but does not apply to I2. Furthermore,

when replaying HIon S0, we obtain the new flow states as sketched above. Note that the

aforementioned criteria are independent of the underlying flow description language.

The described criterion is still too restrictive to serve as general correctness principle. Par-

ticularly with respect to loops1it may needlessly exclude flow instances from being mi-

grated to a modified schema. As an example take a flow instance Ifor which a loop block

is in its 2nd iteration. Assume that the flow schema shall be modified by adding activities

to a non-entered region fromthis loop block. Taking the above criterion this change will be

not allowed if the first loop iteration of Iis not compliant with the resulting flow schema;

i.e., HIcould not be completely produced on the modified schema. However, exclud-

ing such flow instances from migrations is not in accordance with practice. To cope with

this we relax the above criterion by (logically) discarding those history entries from the

execution history produced within another loop iteration than the last (completed loops)

or current one (running loops). We denote this reduced view on execution history HIas

reduced execution history RHI. Based on this we can apply the following fundamental

correctness principle for dynamic changes of BPEL flow instances:

Axiom 1 (Dynamic Change Correctness) Let Ibe a BPEL flow instance on schema S

with execution history HIand reduced execution history RHI. Assume further that Sis

transformed into a correct schema S0by applying change ∆. Then:

1. ∆can be correctly propagated to BPEL flow instance Iiff RHIcan be produced

on S0as well – for this case Iis said to be compliant with S0.

2. When propagating ∆to a flow instance I, which is compliant with S0, the correct

state of Ion S0(e.g., activity markings) can be obtained by replaying RHIon S0.

4.3 Rules for Automatically and Efficiently Checking Compliance

The challenge is how to efficiently guarantee compliance and how to determine the cor-

rect new state of compliant flow instances (according to Axiom 1) in BPEL. Certainly, it

1Loops can be modeled in BPEL by means of a specific block element.

would be no good idea to access the whole (reduced) execution history and to try to replay

it on the modified BPEL flow schema. This may cause a performance penalty due to the

large number of instances to be treated. In the following we present optimized rules and

procedures for BPEL flows in order to ensure dynamic change correctness according to

Axiom 1. For selected change operations we examplarily sketch compliance conditions

which can be efficiently checked by an adaptive BPEL flow engine. We apply the follow-

ing design principles: (1) We consider change semantics and change context in order to

precisely specify which state information is needed for checking compliance. (2) We make

use of the dynamic model properties sketched in Section 3. In particular, the derivation of

compliance rules benefits from model-inherent activity markings which already provide a

consolidated view on the (reduced) history of a flow instance.

In the following let Sbe an executable BPEL flow schema and let Ibe a flow instance

on Swith marking MS = (NS, ES)2. Assume that Sis correctly transformed into another

BPEL flow schema S0by applying change ∆3. For selected changes ∆, Fig. 5 shows the

formal conditions under which we can ensure compliance of Iwith the modified BPEL

flow schema S0. More precisely, one can formally prove that flow instance Iis compliant

with flow schema S0=S+∆(according to Axiom 1) if the compliance rule related to ∆

is satisfied. Note that none of the change operations depicted in Fig. 5 requires access to

the (complete) execution history. Generally, this cannot always be achieved. Concerning

the insertion of a new link, for example, in certain cases compliance can be guaranteed

even if the target activity of this link has been started, completed, or disabled. To decide

on this, however, additional information from execution logs is needed.

Change Operation Δ on schema S... ... and Related Compliance Condition

addActivity(S, act, Preds, Succs)

Inserts activity act between node sets

Preds and Succs; i.e., each node of

Preds will become a predecessor and

each node of Succs a successor of act.

[ ∀ n ∈Preds: NS(n) = Disabled] ∨

[ ∀ n ∈Succs: (NS(n) ∈ {NotActivated, Activated}) ∨

(NS(n) = Disabled ∧

∀ m ∈ succs(S,n): NS(m) ∈ {NotActivated, Activated, Disabled})]

(succs(S,n) denotes the set of direct and indirect successors of n in flow schema S)

deleteActivity(S, act) NS(act) ∈ {NotActivated, Activated, Disabled}

addVariable(S, var, ...) no condition

addDataLink(S, act, var, read)

Adds a read data link to schema S; i.e.,

activity act will have read access on

variable var.

NS(act) ∈ {NotActivated, Activated, Disabled}

addDataLink(S, act, var, write)

Adds a write data link to schema S;

i.e., activity act will have write access

on variable var.

NS(act) ≠ COMPLETED

Figure 5: Examples of compliance rules for dynamic changes of BPEL flows

We exemplarily describe the compliance condition of change operation addActivity. Re-

2To each activity of the respective flow instance NS assigns one of the markings NotActivated, Activated,

Completed, Disabled or Failed, and to each link of the respective flow instance ES assigns one of the states

NotSignaled, TrueSignaled or FalseSignaled

3What BPEL schema correctness means in our context has been discussed in [RRD04a]

garding the insertion of an activity act between two node sets P reds and Succs compli-

ance can be guaranteed if all activities from Succs possess one of the markings Activated

or NotActivated. In this case, none of the successors of act has yet written an entry into

the execution history HI. A simple example is depicted in Fig. 6 where activities X and

Y as well as a data dependency between them are added. Furthermore, compliance can be

also ensured if all activities from P reds are marked as Disabled. Then the added activ-

ity will be disabled as well, i.e., its insertion will have no effect on compliance. Finally,

activity act may be added as predecessor of a disabled activity provided that none of the

successors of this activity has a marking other than NotActivated, Activated, or Disabled.

flow instance I on S:

I compliant with modified

flow schema

change operation ...

addActivity(S, act, Preds, Sucss)

... and related compliance condition:

[ ∀n∈Preds: NS(n) = Disabled] ∨

[∀n ∈Succs:

(NS(n) ∈{NotActivated, Activated}) ∨

(NS(n) = Disabled ∧∀m ∈succ(S,n):

NS(m) ∈{NotActivated, Activated, Disabled})]

NS(D) = Activated, NS(F) = NotActivated

(NS: Node/Activity State)

= {addActivity(S, X ,B, D),

addActivity(S, Y, E, F), … }

Change

Figure 6: Checking compliance when inserting new activities

Fig. 5 shows compliance conditions for several other change operations (e.g., deletion

of activities, insertion of data links). In a similar way, compliance conditions for other

change primitives can be derived (e.g., insertion/deletion of structured activities, update of

a transition/join condition, etc.). Altogether we can state that compliance (cf. Axiom 1)

very often can be decided on basis of current activity markings; i.e., the engine must not

explicitly check the producibility of execution histories on the modified schema. In order

to come to a complete solution, corresponding compliance conditions must be derived for

all basic change operations applicable on a BPEL schema. Based on them, one can develop

high-level change operations and related compliance rules. Since the latter can be derived

by merging compliance conditions of the applied change operations and by discarding

unnecessary expressions (e.g., conditions on nodes not present in the original flow schema)

we do not consider them in this paper. As mentioned, Fig. 5 only presents the compliance

conditions for selected change primitives. One remaining task is to provide a complete set

of change operations on BPEL schemes and to derive respective compliance conditions for

them. One challenge in this context is the high expressiveness of the BPEL4WS language.

5 Automatically Adapting BPEL Flows After Changes

We exemplarily show how compliant flow instances can be migrated to a changed flow

schema. One problem to be solved is the correct and efficient adaptation of activity and

link markings. How extensive marking adaptations turn out for an instance Ito be mi-

grated depends on the kind and scope of the change. Except initialization of newly added

activities and links, for example, no adaptations will become necessary if execution of I

has not yet entered the change region. In other cases extensive marking adaptations may

be required. An activity X, which is enclosed by a flow activity, may have to be deacti-

vated if new links are inserted with X as target activity. Conversely, an added activity Y

will have to be immediately activated or disabled if all predecessors of Y possess a final

marking (Completed, Disabled). As shown in Fig. 7, it may even become necessary to

reset disabled activities in their state when adding an activity.

According to Axiom 1,(2) the marking of a migrated flow instance must be the same

as it could be obtained when replaying the respective (reduced) history on the modified

flow schema. Following the sketched approach, however, it does not become necessary to

access execution logs. Instead the necessary adaptations of activity/link markings can be

automatically and efficiently done by (re-)evaluating the markings of those activities/links,

which constitute the context of a change region. Regarding activity insertion, for example,

one must re-evaluate the marking of the added activity itself as well as of its successors.

With respect to insertion of a new link, the marking of this link and its target activity must

be evaluated. We omit a presentation of algorithmic details and discuss the basic principles

along two simple examples instead.

Example 1 (Adding a new activity): A first example is depicted in Fig. 7. Control

flow is defined by a network of links. Activities A and D have been completed, whereas

activities B and C have been disabled due to a dead path elimination. Let us assume

that activity X shall be inserted as successor of A and as predecessor of C. Though C is

disabled, this change is allowed since there is no successor of C which has been started

yet. Thus the given flow instance is compliant with the modified BPEL schema. When

migrating it to this schema, several marking adaptations become necessary to correctly

proceed with the flow of control. At first, the incoming link of activity X is evaluated

to True Signaled (since A has marking Completed and the inserted link has no transition

condition). This, in turn, leads to activation of X. Since the outgoing link of X cannot be

signaled at the moment, the marking of its target activity C (and of C’s successor E) is reset

to NotActivated. – This simple example illustrates that changes cannot only be applied to

the not yet entered regions of a BPEL flow schema. Very helpful for efficiently deciding on

the compliance of a flow instance with a modified BPEL schema and for adapting markings

is the distinction between completed and disabled activities (True-/False-Semantics) as

well as the preservation of markings of already passed regions.

Example 2 (Changing Activity Orders): Consider Fig. 8. Let us assume that, at a certain

point in time, a BPEL flow instance looks like the one depicted in Fig. 8a): Activities A

and B have been completed and activity C is currently activated (i.e., C is read to start).

Normally, A, B, C, D, and E have to be executed in sequence. Assume that an exception

occurs which makes it necessary to immediately perform D (which is currently in state