Today's organizations are characterized by long-running distributed business processes, which involve di erent stakeholders and share common resources. One of the main challenges posed in such a highly distributed setting comes from the interference between di erent processes that are running in parallel. During execution of a business process, a data modi cation caused by some external process may lead to erroneous and undesirable business outcomes. In order to address this problem, we propose to annotate business processes with dependency scopes, which cover critical sections of the process. Erroneous execution can be prevented by executing intervention processes, which are triggered at runtime. However, for complex processes with a large number of activities and many interactions with the environment, the manual speci cation of the appropriate critical sections can be particularly time-consuming and error-prone. To overcome this limitation, we present an algorithm for automating the discovery of critical sections. The proposed approach is applied on a real case-study of a BP from the Dutch e-Government.
Modern private and public organizations are moving from traditional,
proprietary and locally managed Business Process Management Systems (BPMS) to
BPMS where more and more tasks are outsourced to third party providers and
resources are shared among di erent stakeholders. Often, this is realized by the
emergent paradigms such as Service Oriented Computing (SOC) and cloud
computing. As a result, business processes (BPs) can no longer be considered in
isolation, since data can be simultaneously accessed and modi ed by di erent
external processes. Disregarding the interdependencies with external actors and
other processes may lead to inconsistent situations, potentially resulting in
undesirable business outcomes. The situation where undesirable business outcomes
are caused by data modi cations of some other concurrently executing process is
known as process interference [
E-Government is a typical area characterized by multiple concurrently executing knowledge-intensive processes. These processes access and modify commonly shared resources such as citizen data, information reported by external contracted parties, etc. In such a context, a \think globally, act locally" approach has to be adopted: each BP instance has to take its own action, independently of other processes, based on how its knowledge about the world evolves during runtime, and how this knowledge a ects the next tasks in its work ow. For example, important data used by subsequent tasks may become obsolete, and conditions on which the process relies may not hold anymore. Therefore, a BP has to be continuously informed about changes concerning that data, reason about them, and react accordingly in order to be able to ensure its consistency with the new state of the world.
In the Netherlands, a rst attempt has been made to provide a Software
as a Service (SaaS) solution for the local e-Government (www.govunited.nl).
One of the processes that is proposed as a candidate for this initiative concerns
the process of the Dutch Law for Societal Support, known as the WMO law.
This law is intended to o er support for people with a chronic disease or a
disability, by providing facilities (usually by external parties) such as domestic
care, transportation, a wheelchair or a home modi cation. Naturally, several
di erent instances of the WMO process can be executed concurrently, together
with other governmental processes, which may access and modify the same data.
For example, during the execution of the WMO process, the citizen may move
to a di erent address, the medical status of the citizen may alter, the eligibility
criteria may change because of some new directive etc. These changes may pass
unnoticed by BPs which rely upon them, and consequently result in unexpected
behavior and undesirable business outcomes. The consequences are often noticed
only by end customers [
Traditional veri cation techniques for work ow and data- ow (e.g. [
In this paper, we extend the initial idea presented in [
The remainder of this paper is organized as follows. Section 2 describes a possible interference scenario on a real case-study taken from Dutch e-Government, which plays the role of our running example. In Section 3 the basic de nitions required for the proposed approach are presented. The algorithm for the automatic identi cation of critical sections is described in Section 4. Section 5 provides an overview of related work, and the overall conclusions are drawn in Section 6. 2
In order to illustrate the e ects of process interference and the potential ways to
overcome them, let us consider a real case-study from the Dutch e-Government
regarding the WMO law, as described in [
The WMO process (shown in Figure 1) starts with the submission of an application for a provision by a citizen. After receiving the application at the municipality o ce, a home visit is executed by an o cer, in order to gather a detailed understanding of the situation. After the home visit, additional information on the citizen's health may still be required, which can be obtained via a medical advice provided by e.g. a general practitioner. Based on this information, a decision is made by the municipality to determine whether the citizen is eligible to receive the requested provision or not. In case of a negative decision, the citizen has the possibility for appeal. In case of a positive decision, the process continues and the requested provision will be provided. For domestic help, the citizen has the choice between \Personal Budget" and \Care in Kind". In case of a \Personal Budget", the citizen periodically receives a certain amount of money for the granted provision, and in case of \Care In Kind" suppliers who can take care of the provision are contacted. For obtaining a wheelchair, rst the detailed requirements are acquired before sending the order to the supplier. The home
Decision T e r m i n a t e T e r m i n a t e
Handle+invoice
Handle invoice
Receive invoice Rtoetthuernsiunpvpoliiceer Cwhitehcdkeincvisoioicne [Invoice not correct]
[Invoice correct] Receive delivery confirmation Handle+invoice
Payment modi cation involves a tender procedure to select a supplier that provides the best o er. If the selected tender is approved by the municipality, the order is sent to the selected supplier. After delivery of the provision, an invoice is sent by the supplier to the municipality. Finally, the invoice is checked and paid. 2.2
The request for a wheelchair or a home modi cation may take up to 6 weeks until the delivery of the provision. These processes depend on the correctness of a number of process variables, like the address of the citizen and the content of the decision. However, these process variables may be changed by another process running in parallel, independently from the WMO process, and are, therefore, volatile. A change in either of these process variables (e.g. address) may have potentially negative consequences for the WMO process, due to its dependencies
DS1: {Address, Medical Condition} DS2: ‘homperomvoidsiifoinca=t=ion’ ‘wheelchair’
provision == {WMO Eligibility Criteria}
Tender Procedure
Check Tender tenderOK == FALSE tenderOK
== TRUE Send Order to Supplier
Acquire Requirements Send Order to
Supplier Delivery Confirmation ‘pcraorveisiinonkin=d=’ ‘peprrsoovniasliobnud=g=et’ DS3: {Address,
Medical Condition} Send Request to Supplier Delivery Confirmation Handle
Invoice on those variables, and lead to erronous outcomes. Such situations are typical examples of process interference.
For example, the requirements of a wheelchair may depend on certain
characteristics of the citizen's home. Consequently, an address change after \Acquire
requirements" might result in a wheelchair that does not t the actual
requirements. Similarly, if the citizen moves to a nursing home after \Check tender
with decision", the home modi cation is not necessary anymore. However, the
supplier is not noti ed of this address change and the municipality is noti ed
through a di erent process, which is external to the WMO process. As a result,
unless some action is taken to cancel or update the order, the WMO process will
proceed with the home modi cation. In order to guard for changes to the volatile
process variables, DSs can be de ned, covering those activities for which such a
change poses a potential risk of interference. In Figure 2, a part of the process is
annotated with DSs using a Process Modeller tool developed for the graphical
modeling of BPs. The tool provides a selection of standard control blocks like
ow, switch etc., with the extra support of design tools for modeling DSs. For
the implementation details see [
The activities in DS1 rely on the accuracy of the address. If the address changes, the DS should be triggered, and potentially some recovery activities need to be executed, depending on the state of the BP at that point. For example, if the address change is detected before the order for a wheelchair is sent to the supplier, it is su cient to execute the IP as shown in Figure 3a. However, if the order is already sent to the supplier, some additional activities are required (Figure 3b). First of all, the current order should be put on hold. After acquiring
Home visit
Acquire requirements
Send order to supplier
Receive delivery confirmation Pause order
Home visit
Acquire requirements
Receive delivery confirmation [Requirements Unchanged] Resume order [New Requirements]
Cancel order
Send order to
supplier
the requirements again, it is evaluated whether there is a change. If not, the order
can be resumed, otherwise the old order should be cancelled and a new order
should be sent. The speci cation of IPs is outside the scope of this paper (for a
detailed discussion about the speci cation of IPs see [
In this section, we provide the basic de nitions regarding the BP representation extended with the support of DSs. First, we de ne the Service Repository (SR), which is a registry that keeps semantic information about a set of services that are accessible to the client who is executing a speci c BP. The SR plays the role of a pool of service descriptions and instances, which are used as the building elements of di erent process speci cations. Service descriptions specify the basic functionalities provided by a service. Service instances refer to speci c providers, which o er a service whose functionality conforms to some service description.
The service descriptions specify the operations o ered by the respective service type and are represented in terms of simple semantics. Service instances refer to speci c providers of a certain service description. The service descriptions can be extracted from standard semantic languages for representing Web Services, such as WSDL-S (www.w3.org/Submission/WSDL-S) and OWL-S (www. w3.org/Submission/OWL-S). The service descriptions capture the Input-Output behavior of the operations, i.e. the type of the input parameters inputs and of the expected outputs, as well as some information about its internal variables (similar to Locals in OWL-S). No extra semantic information is required to automatically identify the critical sections of a BP.
De nition 1 (Service Repository (SR)). A Service Repository SR=(SD ; SI ) is a registry, which keeps a set of Service Descriptions SD , and a set of Service Instances SI . A Service Description sd 2 SD is a tuple sd = (sdid ; O ; SV ), where sdid is a unique identi er, O is a set of service operations, and SV is a list of variables, each ranging over a nite domain. These variables correspond to state variables internal to the service, whose value can be changed by the service operations. Each service operation o 2 O is a tuple o = (id (o); in(o); out (o)) where: { id (o) is the identi er of the operation { in(o) is a list of variables that play the role of input parameters to o, ranging over nite domains { out (o) is a list of variables that play the role of output parameters to o, ranging over nite domains A Service Instance si 2 SI is a tuple si = (iid (si ); st (si )): { st (si ) is the unique identi er (service type) of the service description sd 2 SD this instance complies with { iid (si ) is an instance identi er. For each pair of service instances si1 ; si2 2 SI that have the same service type st (si1 ) = st (si2 ), iid (si1 ) 6= iid (si2 ).
The set of state variables involved in the SR may be used by di erent running process instances, and their value may be changed by any process that has access to the respective setting service operation.
In the followings, the working de nition of a Business Process (BP) is
provided. Although the WMO process (Figure 1) is represented in BPMN-notation
for readability, the core BP representation used in this paper is block-structured
[
{ DS is a dependency scope as de ned in De nition 3. 3.1
The DS is based on a guard-verify structure to deal with modi cation events
due to factors exogenous to the BP, e.g. due to some other process execution
which a ects some data on which the BP relies. The critical part of the BP is
included in the guard block, while the verify block speci es the types of events
that require intervention. The mechanism of event recording and handling are
out of scope of this paper (for a system dealing with process-generated events see
e.g. [
De nition 3 (Dependency Scope (DS)). Given a SR = (SD ; SI ) and a BP = (PVi [ PVe ; E ), a dependency scope is a tuple DS = hguard (VV )fCS g; verify (f(ci ; IPi j terminate(IPi ))g)i, where: { guard (VV ) indicates the set of volatile variables VV PVe whose modi cation triggers the veri cation of the DS, and CS a process element of BP which is called the Critical Section. Whenever during the execution of CS a modi cation event regarding the value of a vv 2 VV is received, the verify part of the DS is triggered, and BP 's execution is interrupted. { verify (f(ci ; IPi )g) comprises a set of tuples consisting of a logical condition ci and an intervention process IPi in compliance with De nition 2 to be pursued if ci holds. Providing a case condition is optional, with the default interpretation being ci = TRUE . IPi speci es a BP which ensures the satisfaction of the properties that re ect the state right after the nal activity of CS . After the interruption of the BP , some IPi is executed, and then BP is resumed just after CS (and from any other parallel branches that were interrupted). { terminate(IP ) forces the rest of BP 's execution to be aborted after completing IP 's execution.
Following De nition 3, the DS speci cation representing DS1 of Figure 2 is as follows, where IPa; IPb and IPc refer to the respective intervention processes, which take care of repairing the erroneous execution in each of the cases. According to DS1 , if a modi cation event regarding the address or the medical condition is received within the scope of the guarded subprocess, di erent IPs are executed, depending on the state of execution and the kind of modi cation that has occurred. For example, if the address change indicates that the citizen has moved to another municipality, then IPa includes canceling the order (either for a wheelchair or home modi cation) if one has already been issued, and sending a noti cation to the city hall. Similarly, IPb takes care of the situation where the customer has moved within the range of the municipality, and IPc in case his medical condition has changed to `deceased'. In the following section we describe how the guard (VV )fCS g part of a DS description can be derived automatically, by parsing the BP speci cation. 4
The algorithm of automated generation of the parts of a BP covered by a DS is presented in Algorithm 1 below. The algorithm guarantees that the computed CSs are elements of the BP in compliance with De nition 2. CSs cover all activities that are directly or indirectly dependent on the same set of volatile variables VV . That is, they either use a vv 2 VV as input or use the output of another activity, which is dependent on vv . These activities are referred to as Dependent Activities (DA). In order to ensure that important change events will not pass untreated, any part of the process in a potential execution path between two activities dependent on the same VV should also be covered by the respective CS. This is necessary to take care of any modi cation of vv that occurs during the execution of this intermediate part, since the modi cation may require the cancelation or repetition of some preceding part of the BP which relied on some vv 2 VV (e.g. performing a new visit to the new house if the address has changed), and which is used by a succeeding element (e.g. to calculate the characteristics of the requested wheelchair). However, branches in switch or ow constructs that are not on a potential path between two activities dependent on some vv , should not be unnecessarily included in the respective CS, in order to avoid unnecessary invocation of intervention processes.
In Figure 4, some examples of CSs are provided to illustrate the properties described above. The shaded activities are dependent on VV and should be covered by a CS. The CSs are indicated by a dashed line. In case (a), only the speci c branches of the switch-constructs that comprise dependent activities are included in the CS. In situation (b), however, the second switch has to be covered entirely by a CS, because the last activity is dependent on VV as well. Any modi cation event regarding a vv 2 VV that occurs during the upper branch (which is not dependent on VV ) has still to be dealt with, since the last activity may use a a variable that is a result of some dependent activities before the switch, which produced this result based on the obsolete vv . In situation (c), both branches of the rst switch contain activities that are not dependent on VV . However, as they both are on a path between activities that are dependent on VV , the entire switch is covered by a CS.
The main function of Algorithm 1 is extractScopes, which takes as an input a BP speci cation in accordance with De nition 2 and the list of volatile variables VV . extractScopes returns a list of tuples hVVi ; CSi i, which correspond to the guard parts of all DSs in the BP. Given a BP = (PVi [ PVe ; E ), VV = PVe . That is, all state variables that are declared in the SR and used in the BP should be guarded, since their modi cation may be a source of erroneous results. The
BP is treated as a tree (represented in XML), where the root is the outermost element in the speci cation, and the leaves are the activities.
The outermost loop in the function extractScopes iterates over the list of volatile variables VV . For each vv 2 VV , critical sections are extracted separately. Identical CSs for di erent variables are merged into a united CS at the end by mergeScopes. The rst step (line 4) is to nd all activities and switch{ blocks that depend directly or indirectly on the volatile variable vv , by calling the function getDependentElems. First (line 18), all activities for which vv is assigned to some of their input parameters directly or by transitivity are added to the dependent elements DE . Then (line 24), DE is augmented by adding all switch{blocks whose condition is either on vv , or some variable produced by the already considered activities. All elements in DE are arranged in a breadth- rst order as they appear in the BP. The next step in extractScopes is to iterate through the list DE . In the inner loop, for each pair of elements ei; ej , it is checked whether their minimal common ancestor is of type sequence. If so, then the function getTempCS is called, which returns a set of elements that are candidates for being CSs with respect to the variable vv , and lie between ei and ej . Then, ej can be removed from DE , since subsequent inspections on it are redundant, as the appropriate CSs covering it have already been computed.
Function getTempCS(ei ; ej ; BP ) rst calls getPathBtw to compute the path between ei and ej (line 31), which comprises all elements that are part of the sequence between ei and ej , including the special markers StartBranchEl and EndBranchEl . These markers indicate the start (splits) and end points (joins) of branching elements. Consequently, a path is a list with members of type Item (line 44), where an item is either a process element or a BranchElMarker . Markers are added in the path only if they concern joins (splits) for which the respective split (join) is not encountered during the traversal of the BP from ei to ej . This way, the markers divide the path into the appropriate sequences of elements (lines 33 to 39), each of which is a candidate for being a CS.
Function getPathBtw uses the auxiliary function nextItems (not explained in the algorithm for space reasons), which returns a list consisting of the next element in the sequence path, and some possible EndBranchEl , if any are encountered before the next element is fetched. These are added to the path, and the process proceeds by fetching the next items (line 45), until the element in the sequence that contains ej is reached. In the latter case, pathInElem is called, which traverses the path within this last element until ej is reached. If the element containing ej is an activity or sequence, this activity (ej ) or the subsequence till ej (line 52) are returned respectively. If the element is a switch or ow, then a StartBranchEl marker is added in the list of results, and the branch containing ej is inspected. pathInElem is called recursively on this branch, and all items in the path leading to ej are collected in pathj . Consequently, the computation of the entire path is completed, and returned to getTempCS . The path is traversed (line 33), and divided into the appropriate CSs: currCS is constructed as a sequence of the elements in path, until a marker is met, at which point currCS is added to the list of candidate CSs. Algorithm 1 Automatic computation of the set of the pairs Guarded=fhVVi ; CSi ig, consisting of volatile variables and respective elements that constitute the Critical Sections 1: function extractScopes(BP ; VV ): List[(List[V], E)] 2: for each vv 2 VV do 3: guardList = ; 4: DE = getDependentElems(vv ; BP ) 5: for each ei 2 DE do 6: tmpCS = ; 7: DE = DE .remove(ei) 8: for each ej 2 DE do 9: if type(minCommonAncestor(ei; ej ))=sequence then 10: tmpCS = tmpCS [ getTempCS(ei, ej, BP ) 11: DE = DE .remove(ej ) 12: for tmpCSi 2 tmpCS do 13: guardList .add(hfvv g; tmpCSi i) 14: mergeScopes (guardList ) 15: function getDependentElems(vv ; BP ): List[Element] 16: varList = fvv g 17: DE = ; 18: for each ai 2 BP .getActivities do 19: for each ipi := v 2 ai .parseInputAssignments do 20: if v 2 varList then 21: for each opi 2 out (ai ) do 22: varList :add (opi ) 23: DE .add(ai); break; 24: for each SW IT CHi 2 BP .getSWITCHelements do 25: ci = SWITCHi .getFirstCondition 26: if ci :getLeftVariable 2 varList then 27: miDE.add(SW IT CHi); 28: return DE 41: function getPathBtw(ei ; ej ; BP ): List[Item] 42: currElem = ei 43: while : currElem.contains(ej) do 44: path.append(currItems) 45: currItems = nextItem(currElem; ei ; BP ) 46: currElem = currItems.getElement 47: if currItems = ; then return ; 48: path.append(pathInElem(currElem; ej ; BP )) 49: return path 50: function pathInElem(el ; endEl ; BP ): List[Item] 51: match type(el ) 52: case activity: 53: return fel g 54: case sequence: 55: return el :subsequenceTill (endEl ) 56: case SWITCH _ ow: 57: pathj = fStartBrEl g 58: branchj = el :getBranchWith(endEl ) 59: return pathj .append(pathInElem(branchj ; endEl ; BP ) 60: return ;
Once the list of temporary CSs tmpCS regarding a volatile variable vv is computed as described above, extractScopes proceeds with constructing the respective guardList consisting of tuples hfvv g; tmpCSi i (line 12). After repeating the process described above for each vv 2 VV , mergeScopes is called, in order to clean up the candidate CSs. The following steps are performed in that order: { If there are two tuples hfv1 g; CS1 i and hfv2 g; CS2 i, where CS1 and CS2 are identical, then they are replaced by a single tuple hfv1; v2g; CS1i. { If there are two tuples hfv1 g; CS1 i and hfv2 g; CS2 i, where v1 =v2 and
CS1 :descendantOf (CS2 ), then the former tuple is removed as redundant. { If a list of tuples on the same volatile variable set hVV ; CS1 i; : : : ; hVV ; CSn i correspond to the branches of a switch, i.e. there is an eswitch = switchf (CS1 ; e1 ); : : : ; (CSn ; en )g, then these are replaced with a single CS, which covers the entire switch{element. A similar process is performed for ow branches. { If a list of tuples on the same volatile variable set hVV ; CS1 i; : : : ; hVV ; CSn i are interrelated through a sequence relation, i.e. there is a seq fCS1 ; : : : ; CSn g, then these are replaced with a single CS, which covers the entire sequence. Algorithm 1 has been applied to the BP speci cation of the WMO process represented in Figure 1. The algorithm identi ed three volatile variables, and all ve critical sections related to them. The total time for parsing the WMO process speci cation and computing all CSs is below 100 msec. The discovered CSs can then be projected on the Process Modeller, as presented in Figure 2.
Process interference between concurrent BPs occurs frequently in organizations,
and some solutions have been provided in literature, e.g. [
However, most existing mechanisms to resolve process interference are either
providing a design-time solution, thus requiring that the designer anticipates
all potential problems and ways to overcome them in advance, or are based
on failing processes [
Interference causes processes to provide erroneous outcomes as a result of
wrong data values. In most cases, however, wrong data values are interpreted a
data integrity problem. Much work has been done with respect to ensuring data
integrity in distributed and concurrent systems. Some techniques for checking
the integrity of distributed and dynamic data stored on the cloud are discussed
in [
One of the main challenges posed by the emergent distributed setting of modern BP Management Systems comes from the interference between di erent processes that access common resources. During execution of a business process, a data modi cation caused by some external factor may lead to erronous results, and should, therefore, be guarded and dealt with. To address this issue, the correct identi cation of the sections of a business process, whose correct execution depends on some volatile variable, is very important. These sections shoul be guarded upon, so that whenever a modi cation event is received during their execution, an appropriate intervention process is executed, in order to restore the process to a consistent state. However, the task of manual speci cation of these critical sections can become cumbersome and prone to errors, especially for processes with a complex structure, using many shared resources. To facilitate this task, we have developed an algorithm, which automatically computes the appropriate critical sections, given a BP speci cation and some semantics regarding the input-output and the internal state variables of the service operations used by the process. We have shown how this can be applied in a real case-study taken from the Dutch e-government. The results can be presented on a process modelling tool in a graphical way, so as to assist the process designer in the speci cation of the necessary dependency scopes in order to ensure the delivery of correct results by the process.