Walid Fdhila
email: fdhilawa@loria.fr

Claude Godart
email: godart@loria.fr

Web service paradigm and related technologies have provided favorable means for the realization of collaborative business processes. From both conceptual and implementation points of view, the business processes are based on a centralized management approach. Nevertheless, it is very well known that the enterprise-wide process management where processes may span multiple organizational units requires particular considerations on scalability, heterogeneity, availability and privacy issues, that in turn, require particular consideration on decentralization. In a previous work [10], we have described a flexible methodology for splitting a centralized process specification into a form that is amenable to a distributed execution. The approach is based on the computation of very basic dependencies between process elements. In this paper, we extend this approach to support advanced patterns such as Loops, Multiple instances and Discriminator, and incorporate the necessary synchronization between the different processing entities. We also detail our interconnection mechanism and explain how to handle control and data dependencies between activities of the different partitions through asynchronous message exchanges. The proposed methodology preserves semantics of the centralized process with a peer-to peer interactions among the derived decentralized processes.

Toward synchronization between decentralized orchestrations of Composite Web Services I. INTRODUCTION

With the emergence of the open standards, Webbased applications have become an intuitive support for Business-to-Business (B2B) and Business-to-Costumer (B2C) processes [START_REF] Weerawarana | Web Services Platform Architecture: SOAP, WSDL, WS-Policy, WS-Addressing, WS-BPEL, WS-Reliable Messaging, and More[END_REF]. Particularly, Service Oriented Architectures (SOA) have the potential to enhance these by allowing autonomous and distributed business processes to interact with each other. Despite the decentralized nature of the context of B2B and B2C interactions, the conception and implementation of a typical business process rely on a centralized execution setting [START_REF]Workflow management coalition: process denition interchange v 1.0 nal[END_REF] which fail to address issues such as high availability, failure resilience and scalability. The relevant research literature on business management confirms that the decentralization is a critical need for several reasons [START_REF] Montagut | The pervasive workflow: A decentralized workflow system supporting long-running transactions[END_REF] [START_REF] Khalaf | E role-based decomposition of business processes using bpel[END_REF][8] [START_REF] Wodtke | The mentor project: Steps toward enterprise-wide workflow management[END_REF][6]:

• scalability which is one of the pressing needs since many concurrent processes or instances of the same process are executed simultaneously, and a centralized architecture can cause a performance bottleneck,

• mutually equitable business relationships where no organization holds the control of the overall process,

• fault tolerance where different parts of a process can be executed even if some components fail,

• decentralization, since the systems are inherently distributed, not lend themselves to centralized control,

• distributing the data to reduce network traffic and improve transfer time as well as concurrence. In addition, especially in processes where large data volumes are transported during the orchestration, overall performance also may benefit from having the execution engines in proximity to the target services, by jointly selecting the providers of the process activities and the providers to store instance data in a way that allows to minimize data transfer during process execution.

In order to deal with the shortcomings of centralized process executions, we have been investigating decentralized orchestrations [START_REF] Fdhila | A flexible approach for automatic process decentralization using dependency tables[END_REF]. In our prior work, we proposed a process decentralization technique to split a composite web service specification into a semantically-equivalent set of partitions. The approach implements both control and data dependencies of the centralized specification with P2P interactions. Data are transferred directly between partitions using asynchronous messaging. This reduces data over the network by sending them directly from their point of generation to their point of consumption. The main advantage of the developed approach is the flexibility that it provides in terms of concepts and structures that it manipulates. This, in turn, allows the extension of the algorithms to the different needs of decentralization. In sharp contrast to previous works, our operation of decentralization computes the abstract process constructs, i.e., workflow patterns [START_REF] Van Der Aalst | Workflow patterns[END_REF]. This methodology separates the implementation details from the high-level reasoning that provides a more complete and generic solution to the decentralization problem. The technique uses a dependency table that resumes direct dependencies between process activities. Next, it generates automatically transitive dependency tables resuming the transitive dependencies between activities having some common properties, i.e., activities invoking the same service or provider. It generates the corresponding sub-processes by specifying their mutual interconnections.

The approach we proposed for decentralization implements only business processes composed of basic patterns (AN Dsplit, ORsplit, AN Djoin,...). However, most of today's processes are complex and may need advanced patterns to implement some repetitive blocs of activities or to instantiate them with multiple instances. For this purpose, we are trying in this paper to extend the previously developed approach to support advanced patterns. The techniques we propose, are complementary to our previous work thereby decentralizing processes with Loops, Multiple instances and Discriminator constructs, and then, provide a more complete solution to the problem. Nevertheless, the flexibility introduced by the derived decentralized processes on the other hand raises new requirements like synchronization between them. For this purpose, we will revise our previously proposed mechanism to synchronize the derived partitions and explain how we translate the connectivity and communication between activities of the initial process to those between activities belonging to different sub-processes. This revision includes messages contents, the interaction patterns used for synchronization and the advantage of patterns replication for message exchanges minimization. It also separates control synchronization from data synchronization and shows how the decentralized derived processes work together through a running example.

The remainder of this paper is structured as follows. Section 2 presents a motivation example. In section 3, we give an approach overview as well as the required definitions. Section 4 explains the different steps to partition Loops, Multiple instances and Discriminator patterns. Synchronization process is detailed in section 5. In section 6, we describe the related work, the issues involved in process decentralization as well as a comparison with our approach. Finally, section 7 summarizes the ideas explained in the paper and outlines some future directions.

II. MOTIVATING EXAMPLE

We present a brief overview of the problem along with our solution mechanism using the following running example. Lets consider a credit approval business process CreditAppr depicted in figure 1. The composite service CreditAppr involves four services: CollectInfo, AssessRisk, Decide, and a Notify service. A customer makes a new credit request to the CreditAppr composite service. The latter invokes the CollectInfo service to know more about the customer. Once the data are available, CreditAppr sends them to AssessRisk who considers whether the risk of the credit is low or high. The risk evaluation is then sent to the Decide service who decides even to approve the credit or not. If the assessment is low then the lowest rate is calculated and a reply is sent to the costumer following approval. If the assessment is high risk then the customer is asked to apply through an alternative process. Customer notification is achieved through the Notify service. It should be noted that control dependencies and data transfer between services are managed centrally by CreditAppr. The latter acts as an intermidiary between all the services and the client. This bottleneck may cause degradation of performance due to large delay between the request and response from and to the client. It may also cause additional traffic in terms of exchanged messages. Together, the four engines perform the role of the centralized CreditAppr. The data produced by a service is routed directly to the service that must consume them. For example, the riskfactor generated by AssessRisk is routed directly to Decide as depicted in Figure 2. In contrast to centralized architecture, decentralized orchestrations are more cooperative. This may lead to increased parallelism and reduced message overhead since fewer messages are sent. The time needed to exchange messages between a partition and its corresponding web service is quite small, since partitions are collocated with their relative web services.

III. APPROACH OVERVIEW

In this Paper, we extend our methodology [START_REF] Fdhila | A flexible approach for automatic process decentralization using dependency tables[END_REF] for decentralizing a process specification characterizing a web service composition to support advanced patterns and detail our interconnection mechanism toward synchronization between derived processes. The developed technique consists in partitioning a composite web service into small partitions each of which has common criteria. The approach is known to be flexible that it doesn't rely on specific decentralization criterion. A criterion characterizes a common property for a set of activities. For instance, if we partition a process upon Providers, each partition will contain only activities invoking the same provider. The criterion choice is an important task for decentralizing efficiently a process. As an example, consider the case of partitioning a process according to the geographically collocated providers, which may result in considerable decrease in the number of messages exchanged between the geographically dispersed providers as we already mentioned in the example introduced in Figure 1. To better understand our decentralization and synchronization mechanisms, we adopt the web services perspective as a criterion. As a result, each partition includes only activities invoking operations of the same service. These partitions are executed independently at distributed locations (preferably collocated with the web services) and can be invoked remotely. They directly interact with each other using asynchronous messaging without any centralized control.

The developed approach doesn't presume any particular process modeling language, but simply assumes that the basic elements of a process can be specified in an abstract way to be translated to an executable process language. Throughout this paper, we use the graph based formalism [START_REF] Leymann | Production Workflow -Concepts and Techniques[END_REF] just for clarification reasons to guide the reader through the decentralization and synchronization steps. By definition, a process which specifies a web service composition defines the relationship between service invocations. This relationship may characterize either the control or data flow structure. Our approach takes into consideration both control and data dependencies between the process activities.

The proposed technique assumes that Processes to be decentralized are structured [START_REF] Kiepuszewski | On structured workflow modelling[END_REF]. This means that different activities are structured through control elements such as AND-split, OR-split, AND-join, OR-join..., and for each split element, there is a corresponding join element of the same type. Additionally, the split-join pairs are properly nested. This assumption seems to be reasonable, since many works have already proposed solutions to map an arbitrary process into a structured one [START_REF] Liu | An analysis and taxonomy of unstructured workflows[END_REF], and because most of workflow tools support structured processes.

A. Definitions

In the following, a process P is represented by a directed acyclic graph where nodes are activities and edges are data or control dependencies. Activities are depicted with boxes with the activity name inside and the web service it refers to (see Figure 9). The arcs between boxes describe the dependencies.

1) An activity a∈A consists of a one-way or a bidirectional interaction with a service via the invocation of one of its operations. In conversational compositions, different operations of a service can be invoked with the execution of different activities. The set of activities that refer to the same service s i is denoted A si . A control edge characterizes the mapping relationship while a data edge characterizes the mapping relation of the output and the input values of two activities. Next, we assume that activities have identities such as a i :s j where a i denotes the activity name and s j the invoked service 2) The preset of an activity a i , denoted •a i , is the set of activities which can be executed just before a i and related to it by a control or data dependency.

3) The postset of an activity a i , denoted a i •, is the set of activities which can be executed just after a i and related to it by a control or data dependency.

B. Interaction patterns

To preserve the initial centralized process semantics, the derived decentralized processes should interact with each other to exchange either control or data information. Service interaction patterns [START_REF] Weske | Business Process Management: Concepts, Languages, Architectures[END_REF] aim at filling this gap by proposing small granular types of interactions that can be combined to the derived decentralized processes. In this paper, we use four patterns to express advanced conversations by passing control and data messages in asynchronous way.

1) Send: The send pattern represents a one-way interaction between two participants seen from the perspective of the sender. It is realized by a send task. 2) Receive: The receive pattern also describes a one-way interaction between two participants, but this time seen from the perspective of the receiver. In terms of message buffering behavior of the receiver, two cases can be distinguished. Messages that are not expected are either discarded or stored until a later point of time, when they can be consumed. 3) One-To-Many Send: A participant sends out several messages to other participants in parallel. 4) One-From-Many Receive: Messages can be received from many participants. In particular, one participant waits for messages to arrive from other participants, and each of them can send exactly one message.

IV. PATTERNS DECENTRALIZATION

A. Loop pattern decentralization

A Loop is a point in a process where one or more activities can be executed repeatedly [START_REF] Van Der Aalst | Workflow patterns[END_REF]. It allows for the repeated sequential execution of a specified activity or a sub-process zero or more times providing a nominated condition evaluates to true. We distinguish two types of cycles: arbitrary and structured. The former have more than one entry or exit point, however in the latter the looping structure has a single entry and exit point. In this paper, we consider only structured cycles since we assumed that processes to decentralize are structured. Figure 3 depicts an example of a process including a Loop for three sequential activities invoking different services a 2 :s 2 , a 3 :s 3 and a 4 :s 4 .

The sequence of activities is repeated while the condition Cond is evaluated to true. A given instance of this sequence is enabled only if the previous one is terminated. Once Cond is evaluated to false, a 5 :s 3 can be enabled. Next, we refer to the process example in Figure 3 to explain our decentralization solution for Loops. The resulting decentralized partitions are depicted in figure 4. The process is partitioned according to services, which means that each partition includes only activities invoking the same service. We notice that only partitions including a set of activities inside the Loop of the main process, have a derived While construct with the same condition. Consequently, only P S1 is a Loop free since a 1 is not in the main Loop. We assume that the Loop condition Cond is known directly after a 1 execution. This condition should be sent to partitions which need Cond to execute their local derived Loops P S2 , P S3 and P S4 . For this purpose, we use the previously introduced interaction patterns One-To-Many Send and Receive. Once Cond is received by P S2 , P S3 , P S4 , a simple exclusive choice is enabled to choose either to execute or skip the Loop. If Cond is evaluated to false, then a dummy activity with a zero execution time is enabled. In this case, P S2 and P S4 terminate, while P S3 continues and handles a 5 . Otherwise, if Cond is evaluated to true, then each of P S2 , P S3 and P S4 loops would be enabled as follows:

1) P S3 and P S4 will be blocked on the receive(sync) activity waiting for a synchronization messages, while P S2 executes a 2 . 2) Once a 2 terminates, a synchronization message is sent to P S3 using the Send pattern to enable a 3 execution. Then, P S2 blocks in receive(cond) activity. 3) Once a 3 terminates, a synchronization message is sent to P S4 to enable a 4 execution. Then, P S3 blocks in receive(cond) activity. 4) a 4 executes, then calculates the new value of cond and sends it to P S2 and P S3 . 5) If cond is evaluated to false, then P S4 and P S2 terminates, and P S3 enables a 5 . Otherwise, repeat the four first steps. The send(sync) and receive(sync) activities are used to synchronize activities of different partitions by exchanging control messages. The resulting partitions are structured and preserve the semantics of the centralized process. Our technique for decentralizing Loops is not specific to the introduced example. For instance, if we consider a Loop on a given sub-process. In this case, we begin by partitioning the sub-process itself using our Loop free process partitioning

B. Multiple instances decentralization

The Multiple instances pattern provides a means of creating multiple instances of a given task [START_REF] Van Der Aalst | Workflow patterns[END_REF]. As a result, within a given process instance, multiple instances of a set of activities can be created. These instances are independent of each other and run concurrently. Each of the instances of the multiple instances task that are created must execute within the context of the process instance from which they were started. For example, assume an order process in which an incoming order contains a number of order lines. For each of these order lines, a check activity needs to be executed. We distinguish two types of multiple instances pattern: with and without synchronization. In the latter, there is no requirement to synchronize the instances upon completion. However, in the former, it is necessary to synchronize the task instances at completion before any subsequent tasks can be triggered. An example of the multiple instances without synchronization pattern implementation is shown in Figure 5. The process is composed of five activities invoking four services. After the completion of a 1 :s 1 the number of required instances N is determined, and N instances of the sequence a 2 :s 2 , a 3 :s 3 and a 4 :s 4 are enabled. These instances run concurrently. In this example, no synchronization between instances is needed and then, a 5 :s 3 can be enabled immediately after the multiple instances have been enabled. As a result, a 5 instance can terminate while a 2 , a 3 and a 4 instances of the multiple instances activity are still running. If we consider the case where multiple instances with synchronization pattern is used, a 5 would be enabled only after the completion of all instances of the multiple instances activity. To achieve synchronization in the same example, it is possible to implement a 4 such that once it is completed, it sends an event to some external event queue. Activity a 5 can be proceeded by another activity that consumes the events from the queue and triggers a 5 only if the number of events in the queue is equal to the number of instances of activity a 4 . However, this solution is not supported by all workflow engines. We show later how to deal with multiple instances with synchronization patterns.

Figure 6 illustrates our decentralization technique for the multiple instances without synchronization pattern using the process example introduced in Figure 5. The technique is quite similar to that used for Loops, except that the multiple instances of the sequence a 2 , a 3 and a 4 run concurrently. Assume that A i is the ith instance of the sequence a 2 , a 3 and a 4 . In contrast to Loops, A i+1 doesn't need to wait until the completion of A i to be enabled, but runs concurrently.

We assume that the instances number N is known directly after a 1 execution during run time. Then N should be sent to partitions having a derived Multiple instance activity, namely P S2 , P S3 and P S4 . According to N value, P S2 , P S3 , P S4 choose either to execute or skip their multiple instances activities. If N is evaluated to zero, then a dummy activity with a zero execution time is enabled. In this case, P S2 and P S4 terminate, while P S3 continues and handles a 5 .

Otherwise, if N is greater than zero, then each of P S2 , P S3 and P S4 multiple instances activities would be enabled as follows:

1) P S3 and P S4 will be blocked on the receive(sync) activity, while P S2 enables a 2 execution. In the same time, P S2 current instances number i is incremented. If i is less than N, another instance of a 2 is enabled. As a result, N instances of a 2 would run concurrently. 2) For each a 2 instance termination, a synchronization message is sent to P S3 and a new a 3 instance is enabled. This leads to the increment of P S3 local instances number i. If i is equal to N, then a 5 would be enabled even while other instances of the multiple instances activities are still running. 3) For each a 3 instance termination, a synchronization message is sent to P S4 and a new a 4 instance is enabled. Then, P S4 local instances number i is incremented.

Fig. 6. Decentralized Multiple instances pattern

Our technique for decentralizing multiple instances pattern is also not specific to the introduced example. For instance, if we replace a 2 , a 3 and a 4 by a given sub-process to run multiple instances of it. Then we partition the sub-process itself using our basic partitioning technique [START_REF] Fdhila | A flexible approach for automatic process decentralization using dependency tables[END_REF]. Next, we encapsulate the derived partitions into multiple instances patterns and add the corresponding synchronization activities.

In [START_REF] Van Der Aalst | Workflow patterns[END_REF], the authors presented some centralized implementations to synchronized multiple instances with a prior design or run time knowledge patterns. With prior design knowledge, they just replicate the multiple instance activity with a parallel split pattern (AN D split ). Once all activities instances are completed, they synchronize them with a synchronizing pattern (AN D join ). This could be automatically decentralized using our basic algorithms. With a prior run time knowledge, they proposed many implementations such as using Loops to activate instances sequentially or using a combination of AN D split and XOR split . The latter assumes a maximum number of possible instances. According to these implementations, we can use either our technique to partition Loops or our basic partitioning algorithms [START_REF] Fdhila | A flexible approach for automatic process decentralization using dependency tables[END_REF].

C. Discriminator decentralization

The discriminator (known also as 1-out-of-M join) is a point in a process model that waits for one of the incoming branches to complete before activating the subsequent activity [START_REF] Weske | Business Process Management: Concepts, Languages, Architectures[END_REF]. From that moment, it waits for all remaining branches to complete and ignores them. Once all incoming branches have been triggered, it resets itself so that it can be triggered again. For instance, When handling a cardiac arrest, the check breathing and check pulse tasks run in parallel. Once the first of these has completed, the triage task is commenced. Completion of the other task is ignored and does not result in a second instance of the triage task. It should be noted, that all branches must either flow from the Parallel Split to the Structured Discriminator without any splits or joins or they must be structured in form (i.e. balanced splits and joins). An process example implementing a discriminator pattern is depicted in Figure 7. The process is composed of four sub processes namely A, B, C and the sub-process in a box representing the discriminator pattern. Once a 1 terminates, it enables both a 2 and a 3 concurrently. Assuming a 2 terminates first, the discriminator fires and enables a 4 , and possibly subprocess C. When a 3 terminates it would be ignored. Assuming that the process example involves four services s 1 , s 2 , s 3 and s 4 , then partitioning it would result in four partitions (see Figure 8). A si (respectively B si , C si ), represents the derived partition of the sub-process A (respectively B, C), related to the service s i . After A s1 completion, it takes a decision about the branches to enable through the OR-split. The decision is forwarded to the other partitions having the same OR-split using a pattern identifier [START_REF] Fdhila | A flexible approach for automatic process decentralization using dependency tables[END_REF] (this forwarding is not depicted in the example). Assume that the branch including a 1 is enabled and the one including B s1 is skipped. In this case, B s2 , B s3 and B s4 would also be skipped. Once a 1 terminates, a one-to-many send activity is launched and two synchronization messages are sent respectively to P s2 and P s3 enabling a 2 and a 3 concurrently. The first which terminates, send a synchronization message to P s4 and hence, a 4 would be enabled. The second would be ignored when it completes. The proposed algorithm is generic and not specific to this example. It even can handle N-out-of-M join pattern (a generalization of the discriminator) [START_REF] Weske | Business Process Management: Concepts, Languages, Architectures[END_REF], by communicating the number of branches to be enabled N to the discriminator. Due to lack of space, our formal algorithms for partitioning loops, multiple instances and discriminator patterns are not Fig. 9. Process example presented in this paper.

V. SYNCHRONIZATION PROCESS

In this section, we detail how our interconnection mechanism works to synchronize between the derived partitions of a given centralized process, in run-time. First, let us consider the following process example depicted in Figure 9. The graphical description includes control and data dependencies of process activities. The process represents a collaboration between four web services namely s 1 , s 2 , s 3 and s 4 . a i :s j represents an invocation activity of one of s j operations. Each construct has an identifier such as a two corresponding constructs with the same type have the same identifier. For instance, the first OR-split and the last OR-join in the process example have the same identifier id =1. In this example, we use only basic patterns since we have already presented how to handle synchronization within advanced patterns in a decentralized architecture. Synchronization is achieved using send, One-To-Many Send, Receive and Onefrom-many Receive interaction patterns. Figure 10 depicts the derived partitions of the centralized process example as well as a part of the required inter-connections. Interconnection process is explained in [START_REF] Fdhila | A flexible approach for automatic process decentralization using dependency tables[END_REF]. In order to simplify the example, we have omitted interaction activities assuming that for each arrow connecting two partitions, there are send and receive activities respectively at the sender and receiver sides. Further, several arrows coming out from the same activity means a One-To-Many Send, while several arrows converging to the same activity means a One-from-many Receive.

A. Message exchange

Derived decentralized processes, communicate through message exchange using interaction patterns. Messages represent either control or data information. We define a message format as follow: Message (type, a i :P Sm , a j :P Sn , instanceid, inf ormation). Where type specify either if it is control or data message (set to zero or one), a i :P Sm defines interaction activity and partition source, a j :P Sn the interaction activity and partition target, instance-id the instance identifier to make correlation, and inf ormation is either a control decision or a data to transfer. A control decision has the form enable(branch-ids), where branch-ids are the set of branches to enable. For instance, in Figure 10, the message M (0, send 1 :P S1 , receive 1 :P S2 ,12, enable(b1)) represents a control decision taken by P S1 concerning OR-split 1 . When received by P S2 , it enables branch 1 and therefore a 2 . branch 2 and its subsequent activities will be automatically skipped.

B. Control dependency synchronization

In a centralized architecture, a decision for the OR-split 1 should be taken after a 1 termination, to either enable a 2 , a 3 or both of them. In our decentralized architecture, the decision should be transmitted to all partitions having an OR-split 1 (represented by the three dashed arrows C 1 in Figure 10). Next, we explain through a running instance, how our synchronization technique minimizes the messages exchanges number compared to typical approaches. The main Fig. 10. Decentralized process advantage lies in replicating patterns through the corresponding partitions. We remind that two corresponding join and split patterns are replicated only through partitions including activities between them in the centralized process. For instance, a 1 is connected to the decentralized patterns ORsplit 1 instead of its postset a 1 •={a 2 ,a 3 }. To get a better understanding, assume a scenario where a 3 won't be enabled after a 1 execution. 1) Without patterns replication: First, a 1 send two messages to its postset a 1 • to enable a 2 and skip a 3 . Then a 3 send two messages to a 3 •= {a 6 ,a 7 } to be skipped, which in turn send messages to their postsets and so on until reaching a 21 . This leads to 11 synchronization messages inter-partitions. 2) With patterns replication (Figure 10): After a 1 termination, three synchronization messages (C

C. Data dependency synchronization

Data dependency characterizes the mapping relation of the output and the input values of two activities. We state two problems: sending data to an activity which won't be activated later and waiting for a data from an activity which won't be activated. In the first scenario, the data should be transmitted from the partition source to its destination. The message won't be consumed, but stored in the destination buffer until it expires. In the second scenario, we identified two solutions. A trivial one is that for each skipped activity which has a data dependency, a notification message should be sent by the partition it belongs to, to the activity waiting for the data. This may lead to an extra number of messages. So, we suggest to use data routing tables DRT for each activity followed by an OR-split or XOR-split. A data routing table, is a table resuming data dependencies between a set of activities. For instance, consider the process example and the case where a 3 won't be executed. Assuming that a 1 is the activity which takes the decision (OR-split 1 ), then P S1 should maintain a DRT 1 . The latter includes the activities {a 8 :s 1 , a 18 :s 4 , a 7 :s 3 , a 23 :s 2 } and the data variable names {d 3 , d 4 , d 6 }. This means that only dependencies between activities inside the < ORsplit 1 , OR-join 1 > and activities outside are considered. In this case, P S1 will send a single message to P S2 to notify it for the skip of d 4 and d 6 . This mechanism, reduces considerably message exchanges between partitions. Also, no messages between skipped dependent activities inside < ORsplit 1 , OR-join 1 > would be exchanged.

D. Process execution

During runtime, activities must respect all their preconditions and postconditions before and after execution. Preconditions are control and data connections with each of its preset activities whereas postconditions are control and data connections with each of its postset activities (i.e. in Figure 10, preconditions of a 4 are C 1 , C 2 and d 1 ). For a given instance, a partition completes its role in the collaboration when it reaches EF activity. An instance execution terminates when all partitions reach EF for the same instance. The proposed technique for decentralization using patterns replication, make synchronization easier and minimizes message exchanges between partitions.

VI. RELATED WORK

In recent years, several approaches and architectures for decentralized process execution have been proposed. In the context of process partitioning, [21][8] are the first works that take on the challenge of partitioning BPEL processes. These contributions use program partitioning techniques in order to reduce the communication costs between derived process fragments. It's not clear how they deal with propagating DPE across process fragments and what subset of BPEL they support.

[15][14] present a similar approach to the decentralization focusing on the P2P interactions. Their contribution take on the formalization of the decentralized interactions from a conceptual point of view. Nevertheless, they present some specific BPEL examples rather than an overall approach that can decentralize any sophisticated process. [START_REF] Sadiq | Model driven distribution of collaborative business processes[END_REF] presents a similar approach to the decentralization of the control flow without considering data dependencies of process activities. Similar process partitioning approaches have been applied to different needs such as the implementation of secure interactions [START_REF] Atluri | A decentralized execution model for inter-organizational workflows[END_REF] or the decentralized exception handling [START_REF] Chafle | Handling faults in decentralized orchestration of composite web services[END_REF].

[19] developped a formal approach based on automata that takes as an input the existing services, the goal service, the costs and produces as an output a set of decentralized choreographers that realize the goal service using the existing services. The approach is based on I/O-automata representation of services and goal, and identifies appropriate choreography scheme using the notion of universal service, simulation relation and a path-cost computation for a graph. This work does not focus on the decomposition of global processes and it is not clear how they deal with loops, discriminator and multiple instance patterns.

In [START_REF] Yildiz | Towards decentralized service orchestrations[END_REF][30] [START_REF] Yildiz | Synchronization solutions for decentralized service orchestrations[END_REF], the decentralization of processes has been studied in an abstract manner by extending the dead path elimination operation of workflow management systems. The decentralization focuses on the preservation of the centralized specification by preventing possible blocking situations.

Another approach to the decentralization concerns the implementation of additional applications to support the required interactions without embedding them into decentralized processes. ObjectFlow [START_REF] Hsu | Objectflow: Towards a process management infrastructure[END_REF] uses a graph-based workflow definition model. Steps are executed by agents coordinated by a (potentially) distributed workflow engine which however accesses a centralized DBMS to store workflow states. In METEOR2 [START_REF] Sheth | Supporting state-wide immunisation tracking using multi-paradigm workflow technology[END_REF], process scheduling is distributed among various task managers. In Mentor [START_REF] Wodtke | The mentor project: Steps toward enterprise-wide workflow management[END_REF], workflows are modeled using state-charts which are partitioned to each involved processing entitiy (PE). Each PE-specific state-chart is executed locally on the PE workstation. Another example that support the decentralized execution without partitioning centralized specifications is Self-Serv [START_REF] Benatallah | The self-serv environment for web services composition[END_REF]. In Self-Serv, the interactions of composed services are implicitly encoded within the processes.

In the context of Web services, [START_REF] Kavantzas | Web services choreography description language version 1[END_REF] introduce the Web Services Choreography Description Language which has not received much attention, similarly to [START_REF] Arkin | Web service choreography interface (wsci)[END_REF]. The organization for the Advancement of Structured Information Standards puts forward the ebXML standard for business collaboration [START_REF] Jean-Jacques Dubray | ebXML Business Process Specification Schema Technical Specification v2[END_REF]. More recently, service interaction patterns have been introduced in [START_REF] Barros | Service interaction patterns[END_REF], and the language Let's Dance was introduced in [START_REF] Zaha | Let's dance: A language for service behavior modeling[END_REF]. The relationship between a global public process choreography and the private orchestrations is investigated in [START_REF] Van Der Aalst | The p2p approach to interorganizational workflows[END_REF] based on work on process inheritance as introduced in [START_REF] Basten | Inheritance of behavior[END_REF]. The equivalence of process models, using their observable behavior, is studied in [START_REF] Van Der Aalst | Process equivalence: Comparing two process models based on observed behavior[END_REF]. The relationship between compatibility notions in process choreography and consistency of process implementations with regards to behavioral interfaces is studied in [START_REF] Decker | Behavioral consistency for b2b process integration[END_REF].

The developed techniques are often good for dealing with a particular aspect of decentralization rather than providing a generic and flexible manipulation setting required for process decentralization. The common limitation of the current decentralization approaches is their dependencies on the underlying process specification. They can deal with how the decentralized processes must be synchronized with the relevant messages of the low-level specification but they cannot address the fundamental questions about the decentralization of the combined control and data dependencies. Consequently, this becomes a major limitation for the use of these systems in different cases which are not explicitly specified in their decentralization mechanism. Also, most of the proposed approaches stop short in answering to how they handle loops, multiple instances and discriminator patterns in decentralized processes. The main advantage of the developed approach is the flexibility that it provides in terms of concepts and structures that it manipulates. This, in turn, allows the extension of the algorithms to the different needs of decentral-ization. In sharp contrast to previous works, our operation of decentralization computes the abstract process constructs, i.e., workflow patterns [START_REF] Van Der Aalst | Workflow patterns[END_REF]. This methodology separates the implementation details from the high-level reasoning that provides a more complete and generic solution to the decentralization problem.

VII. CONCLUSION

This paper has presented an extension to our approach to the flexible decentralization of process specifications. The developed approach is applicable to a wide variety of service composition standards that follow the process management approach such as WS-BPEL. In contrast to previous works that take on the process decentralization approaches, our methodology separates the implementation details from the high-level reasoning that provides a more complete and generic solution. In addition to the basic constructs like XOR, AND, OR (split and join), sequence... It also takes into consideration advanced patterns such as Loops, Multiple instances and discriminator. The flexibility introduced by decentralized processes on the other hand raises new requirements like synchronization between them. In this sense, we proposed a mechanism toward synchronization through message exchange using interaction patterns. Further, we would like to implement the introduced methodology on a web service composition language to enable a quantitative evaluation of the approach in terms of message exchanges, and add security aspects between the decentralized process specifications.

Fig. 1 .

 1 Fig. 1. Centralized Credit Approval process Figure 2 depicts a possible decentralized execution setting for the same process. The CreditAppr is partitioned into four components that are executed by four distributed engines.Together, the four engines perform the role of the centralized CreditAppr. The data produced by a service is routed directly to the service that must consume them. For example, the riskfactor generated by AssessRisk is routed directly to Decide as depicted in Figure2. In contrast to centralized architecture, decentralized orchestrations are more cooperative. This may lead to increased parallelism and reduced message overhead since fewer messages are sent. The time needed to exchange messages between a partition and its corresponding web service is quite small, since partitions are collocated with their relative web services.

Fig. 2 .

 2 Fig. 2. Decentralized Credit Approval process

Fig. 3 .

 3 Fig. 3. process including a While pattern

Fig. 4 .

 4 Fig. 4. Decentralized While pattern

Fig. 5 .

 5 Fig. 5. Multiple instances pattern

Fig. 7 .

 7 Fig. 7. Discriminator pattern

Fig. 8 .

 8 Fig. 8. Decentralized discriminator pattern

  1 ) are sent to P S2 , P S3 and P S4 . Messages contain a control decision taken by P S1 concerning OR-split 1 and enabling only branch 1 (a 2 ). When received, each partition would skip locally all subsequent activities of branch 2 . Therefore, only three inter-partition messages are needed to synchronize this first part of the process execution. Now, assume that all subsequent activities of branch 1 are executed (until a 20 ). Thanks to our technique, P S1 knows in advance that it has to wait for only one control message (from a 20 ) to enable a 22 , since it is preceded by OR-join 1 . Hence, a 21 doesn't need to inform a 22 that it was skipped.


Walid Fdhila

Ustun Yildiz

Claude Godart
email: godart@loria.fryildiz@cs.ucdavis.edu

A flexible approach for automatic process decentralization using dependency tables

Web service paradigm and related technologies have provided favorable means for the realization of collaborative business processes. From both conceptual and implementation points of view, the business processes are based on a centralized management approach. Nevertheless, it is very well known that the enterprise-wide process management where processes may span multiple organizational units requires particular considerations on scalability, heterogeneity, availability and privacy issues, that in turn, require particular consideration on decentralization. In this paper, our aim is to reconcile the decentralization of processes as a step towards the enterprise-wide solutions. We propose a methodology for transforming a centralized process specification into a form that is amenable to a distributed execution and to incorporate the necessary synchronization between different processing entities. The proposed technique has the advantage of being flexible that it computes the abstract constructs and provides a generalized approach to the decentralization of processes.

Introduction

With the emergence of the open standards, Webbased applications have become an intuitive support for Business-to-Business (B2B) and Business-to-Costumer (B2C) processes [START_REF] Weerawarana | Web Services Platform Architecture: SOAP, WSDL, WS[END_REF]. Particularly, Service Oriented Architectures (SOA) have the potential to enhance these by allowing autonomous and distributed business processes to interact with each other. Despite the decentralized nature of the context of B2B and B2C interactions, the conception and implementation of a typical business process rely on a centralized execution setting [START_REF]Workflow management coalition: process denition interchange v 1.0 nal[END_REF]. The relevant research literature on business management confirms that the decentralization is a critical need for several reasons [START_REF] Montagut | The pervasive workflow: A decentralized workflow system supporting long-running transactions[END_REF] [START_REF] Khalaf | E role-based decomposition of business processes using bpel[END_REF][8] [START_REF] Wodtke | The mentor project: Steps toward enterprise-wide workflow management[END_REF][6]:

• scalability which is one of the pressing needs since many concurrent processes or instances of the same process are executed simultaneously, and a centralized architecture can cause a performance bottleneck, • mutually equitable business relationships where no organization holds the control of the overall process, • fault tolerance where different parts of a process can be executed even if some components fail, • decentralization, since the systems are inherently distributed, not lend themselves to centralized control, • distributing the data to reduce network traffic and improve transfer time as well as concurrence.

Although the decentralization fulfills most of the critical needs of collaborative business processes, it stops short in answering to the basic primitives of an execution setting such as the message routing between business partners to respect control dependencies. In the context of process decentralization, the existing works have differences and similarities in many different and strange ways, and modeling these accurately is difficult [START_REF] Montagut | The pervasive workflow: A decentralized workflow system supporting long-running transactions[END_REF][14] [START_REF] Chafle | Decentralized orchestration of composite web services[END_REF]. The developed techniques are often good for dealing with a particular aspect of decentralization rather than providing a generic and flexible manipulation setting required for process decentralization. The common limitation of the current decentralization approaches is their dependencies on the underlying process specification. They can deal with how the decentralized processes must be synchronized with the relevant messages of the low-level specification but they cannot address the fundamental questions about the decentralization of the combined control and data dependencies. Consequently, this becomes a major limitation for the use of these systems in different cases which are not explicitly specified in their decentralization mechanism.

In order to deal with the shortcomings of centralized process executions, we propose in this paper, a process decentralization technique that creates multiple sub-processes that interact with each other and thus, implements the dependencies of the centralized specification with P2P interactions. The main advantage of the developed approach is the flexibility that it provides in terms of concepts and structures that it manipulates. This, in turn, allows the extension of the algorithms to the different needs of decentralization. In sharp contrast to previous works, our operation of decentralization computes the abstract process constructs, i.e., workflow patterns [START_REF] Van Der Aalst | Workflow patterns[END_REF]. This methodology separates the implementation details from the high-level reasoning that provides a more complete and generic solution to the decentralization problem. The technique uses a dependency table that resumes direct dependencies between the process activities. Next, it generates automatically transitive dependency tables resuming the transitive dependencies between activities having some common properties, i.e., activities invoking the same service. It generates the corresponding sub-processes by specifying their mutual interconnections. Furthermore, we demonstrate the translation of the connectivity and communication between activities of the initial process to those between activities belonging to different sub-processes. We show also the reduction of the communication costs. The approach preserves also the semantics of the initial process specification.

The remainder of this paper is structured as follows. Section 2 describes the background and the issues involved in process decentralization. In section 3, we detail our approach and explain the different steps for getting the partitioned sub-processes. Approach flexibility is discussed in section 4. Finally, section 5 summarizes the ideas explained in the paper and outlines some future directions.

Related Work

In recent years, several approaches and architectures for decentralized process execution have been proposed. In the context of process partitioning, [18][8] are the first works that take on the challenge of partitioning BPEL processes. These contributions use program partitioning techniques in order to reduce the communication costs between derived process fragments. [START_REF] Khalaf | E role-based decomposition of business processes using bpel[END_REF][13] present a similar approach to the decentralization focusing on the P2P interactions. Their contribution take on the formalization of the decentralized interactions from a conceptual point of view. Nevertheless, they present some specific BPEL examples rather than an overall approach that can decentralize any sophisticated process. [START_REF] Sadiq | Model driven distribution of collaborative business processes[END_REF] presents a similar approach to the decentralization of the control flow without considering data dependencies of process activities. Similar process partitioning approaches have been applied to different needs such as the implementation of secure interactions [START_REF] Atluri | A decentralized execution model for inter-organizational workflows[END_REF] or the decentralized exception handling [START_REF] Chafle | Handling faults in decentralized orchestration of composite web services[END_REF]. In [START_REF] Yildiz | Towards decentralized service orchestrations[END_REF][26], the decentralization of processes has been studied in an abstract manner by extending the dead path elimination operation of workflow management systems. The decentralization focuses on the preservation of the centralized specification by preventing possible blocking situations.

Another approach to the decentralization concerns the implementation of additional applications to support the required interactions without embedding them into decentralized processes. ObjectFlow [START_REF] Hsu | Objectflow: Towards a process management infrastructure[END_REF] uses a graph-based workflow definition model. Steps are executed by agents coordinated by a (potentially) distributed workflow engine which however accesses a centralized DBMS to store workflow states. In METEOR2 [START_REF] Sheth | Supporting state-wide immunisation tracking using multiparadigm workflow technology[END_REF], process scheduling is distributed among various task managers. In Mentor [START_REF] Wodtke | The mentor project: Steps toward enterprise-wide workflow management[END_REF], workflows are modeled using state-charts which are partitioned to each involved processing entitiy (PE). Each PE-specific statechart is executed locally on the PE workstation. Another example that support the decentralized execution without partitioning centralized specifications is Self-Serv [START_REF] Benatallah | The self-serv environment for web services composition[END_REF]. In Self-Serv, the interactions of composed services are implicitly encoded within the processes.

In the context of Web services, [START_REF] Kavantzas | Web services choreography description language version 1[END_REF] introduce the Web Services Choreography Description Language which has not received much attention, similarly to [START_REF] Arkin | Web service choreography interface (wsci)[END_REF]. The organization for the Advancement of Structured Information Standards puts forward the ebXML standard for business collaboration [START_REF] Jean-Jacques Dubray | ebXML Business Process Specification Schema Technical Specification v2[END_REF]. More recently, service interaction patterns have been introduced in [START_REF] Barros | Service interaction patterns[END_REF], and the language Let's Dance was introduced in [START_REF] Zaha | Let's dance: A language for service behavior modeling[END_REF]. The relationship between a global public process choreography and the private orchestrations is investigated in [START_REF] Van Der Aalst | The p2p approach to interorganizational workflows[END_REF] based on work on process inheritance as introduced in [START_REF] Basten | Inheritance of behavior[END_REF]. The equivalence of process models, using their observable behavior, is studied in [START_REF] Van Der Aalst | Process equivalence: Comparing two process models based on observed behavior[END_REF]. The relationship between compatibility notions in process choreography and consistency of process implementations with regards to behavioral interfaces is studied in [START_REF] Decker | Behavioral consistency for b2b process integration[END_REF].

Process Decentralization

In this section, we present our methodology for decentralizing a process specification characterizing a web service composition. Generally, a process is specified in an abstract way (e.g, using a graph based formalism) and mapped onto the architecture model level. We don't presume any particular process modeling approach, but simply assume that the basic elements of a process can be specified in an abstract way to be translated to an executable process language (i.e., process structure in terms of atomic activities and sub-processes, dependencies between the steps of a process, etc). Throughout this paper, we use the graph based formalism just for clarification reasons to guide the reader through the decentralization steps [START_REF] Leymann | Production Workflow -Concepts and Techniques[END_REF]. By definition, a process which specifies a web service composition defines the relationship between service invocations. This relationship may characterize either the control or data flow structure. Our approach takes into consideration both control and data dependencies between the process activities. Before explaining the steps to achieve decentralization, we consider some assumptions and introduce some preliminary definitions.

• Assumption: Processes to be decentralized are structured [START_REF] Kiepuszewski | On structured workflow modelling[END_REF]. This means that different activities are structured through control elements such as ANDsplit, OR-split, AND-join, OR-join..., and for each split element, there is a corresponding join element of the same type. Additionally, the split-join pairs are properly nested. A process activity a∈A consists of a one-way or a bidirectional interaction with a service via the invocation of one of its operations. In conversational compositions, different operations of a service can be invoked with the execution of different activities. The set of activities that refer to the same service s i is denoted A si . A control edge characterizes the mapping relationship while a data edge characterizes the mapping relation of the output and the input values of two activities. S P is the set of services of a process P.

Definition 2 (Activity) an activity a i ∈P is a tuple (In, Out, s) where In⊂D is the set of a i 's inputs, Out ⊂ D is the set of a i 's outputs, s ∈ S is the invoked service by a i

Activities are related to each other and are dependent on each other. These dependencies are intra-process. Dependencies may also exist across processes and are referred to as inter-process dependencies.

Definition 3 (Preset)

The preset of an activity a i , denoted •a i , is the set of activities which can be executed just before a i and related to it by a control or data dependency.

•a i = {a j ∈ A|∃e ji ∈ E c ∪ E d s.t. source(e ji ) = a j ∧ target(e ji ) = a i } Definition 4 (Postset)
The postset of an activity a i , denoted a i •, is the set of activities which can be executed just after a i and related to it by a control or data dependency.

a i • = {a j ∈ A|∃e ij ∈ E c ∪ E d s.t. source(e ij ) = a i ∧ target(e ij ) = a j }
A process is represented by a directed acyclic graph where nodes are activities and edges are data or control dependencies. Activities are depicted with boxes with the activity name inside and the web service it refers to. The arcs between boxes describe the dependencies. This leads to a well defined chronological execution of the activities. Next, we give an overview of the basic mechanisms of our method for the partitioning of process specifications.

Overview of the decentralization approach

The partitioning transforms the centralized process into behaviorally equivalent distributed sub-processes each of which related to a service. These partitions are executed independently at distributed locations (preferably collocated with the web services) and can be invoked remotely. They directly interact with each other using asynchronous messaging without any centralized control. The approach consists of four steps each explained in detail in the next sections, and guided by an illustrative example (cf. Fig. 2). The following is structured according to these steps, and for each step concepts and notations are introduced when required. The combinations of different dependencies between activities are analyzed, and the composite web service specification is partitioned using our program analysis technique. The number of final partitions depends on the number of invoked web services in the process. In other words, the decentralization can be considered as a projection of the initial process P i on other plans P Si each related to a service (cf. Fig. 1). Hence, each plan will contain a sub-process composed of activities invoking the same service as well as the transitive dependencies between them. Additional activities are added to maintain the semantics of the initial process and optimization techniques are applied. For instance, the sub-process related to s 1 is depicted by the projection of the initial process P I on the plan P S1 . To get a better understanding of the importance of decentralization in practice, let us consider the following process example depicted in figure 2. The graphical description includes control and data dependencies of process activities. Activities have identities such as a i :s j where a i denotes the activity

s 1 EF EI - seq - - - - - - - - a 1 - - OR 1sp OR 1sp - - - - - - a 2 - - - - - - - - - - a 3 - - - - OR 3sp - - - - - a 6 - - - - AN D 1sp - - - - a 12 - - - - - - AN D 1j - - - ... a 18 - - - - - - - OR 3j - - a 21 - - - - - - - - OR 1j - a 22 - - - - - - - - - seq
name and s j the invoked service. We consider that services are known in advance.

Building Direct Dependency Tables (DCDT and DDDT)

The first step of our approach consists in building two tables DCDT (Direct Control Dependency Table ) and DDDT (Direct Data Dependency Table) resuming all direct control and data dependencies between the activities. In other words, for each two activities which are control or data dependent, we note the patterns linking them. Each pattern has an identifier such as two corresponding join and split patterns with the same type have the same identifier (i.e. in fig. 2, OR 2sp and OR 2j 1 have the same identifier 2). In the table, lines and columns are process activities a i ∈P. The intersection between two activities corresponds to the con-1 OR j = OR join and ORsp = OR split trol or data patterns between them if they exist. Table 1 resumes the control dependencies between process activities introduced in figure 2. We notice two extra activities EI and EF representing respectively the process initiating and ending activities. Their usability is that when partitioning the process, some sub-processes may have more than one activity in parallel initiating or ending them. In order to obtain structured sub-processes, and for a synchronization purpose, we add those two activities.

For example to build the table DCDT , we parse the process from EI until EF , and for each activity in the path we identify the control pattern linking it to each of its postset elements. If the pattern is a split-element we give it a new label. Otherwise (join-element), we look for the corresponding split-element and give it the same label. It should be noted that many patterns may link two control dependent activities. Table 1 is interpreted as follows:

• line i : represents a k , its postset and the control patterns linking them. For example, in line 2 the execution of a 1 which invokes the service S 1 implies the execution of both or one of the activities a 2 and a 3 which invoke respectively S 2 and S 3 . • column j : represents a k , its preset and the control patterns linking them. For example, in column 5 the execution of a 6 may or not begin after the termination of a 3 since they are related by an OR-split. • (line i , column j ): corresponds to the control patterns, if they exist, that link activity a k to a l .

Building Transitive Control Dependency Tables (TCDT)

This step is an important phase in our approach as it considers the selection of the decentralization criteria (i.e. by services, by providers, by organizations...). In the following, we begin by decentralizing processes based on services. This means that every service will have a relative sub-process containing activities invoking it. We call the sub-process related to a service S i as P si . Obviously, each sub-process must preserve a part of the initial process semantics. To cope with this, we infer from the direct Control dependencies table DCDT, the transitive control dependencies between activities invoking the same service. Next, we build a sub-process containing those activities and linked with the transitive patterns. This means that two transitively dependent activities are linked with the set of patterns which mainly exist in the path between them in the initial process (i.e. in Fig. 2, the transitive dependency between a 1 and a 8 is the path OR 1sp -OR 2sp -OR 4sp ).

In this phase, we build a Transitive Control Dependency Table for each sub-process P Si . To build the TCDTs, we proceed as follows: For each service, we select the set A Si of all activities invoking it, and we add EI and EF activities. For example, for the service S1 we have A S1 ={EI, a 1 , a 8 , a 15 , a 22 , EF }. We build a table T CDT i containing these activities in both lines and columns. As we don't know the order of precedence of those activities, we begin by EI and look for its transitive dependent activities a j such as a j ∈A Si . To achieve this, we look in the DCDT for the postset of EI. If there is at least one activity a k in EI• such as a k / ∈A Si , then we look for a k • and continue until we find an activity a l ∈A Si . For example, the transitive dependent activities of a 1 for P S1 are a 8 , a 15 and a 22 . In the same time, we have to save all control patterns linking an activity a i to each of its transitive dependent activities and notice them in the table TCDT (i.e. the control patterns that link a 8 to a 22 are OR4j, OR2j, OR1j). It may exist several control pattern paths which link two transitively dependent activities (i.e. a 1 is related to a 22 by four control paths). Algorithm 1 gives a formal overview of the way we build TCDTs. The output of this algorithm is a TCDT for each service or sub-process. An example for the TCDT of

Building sub-processes

In this section, we show how to build a sub-process for each T CDT Sj we obtained in the last step. Each sub-process represents the control flow between activities invoking the same service. Algorithm 2 explains formally how to proceed to achieve this. For a control connector ctr, ctr characterizes corresponding split or join connector of the same type. For example if ctr is an OR j , ctr is an OR sp that corresponds to ctr in the process model. First, we optimize ). We also delete, for a given T CDT Sj , paths which contain two corresponding AN D Ksp and AN D Kj which have an acitvity a i ∈A Sj between them (i.e. in T CDT S1 we delete the fourth path linking a 1 to a 22 since between AN D 2sp and AN D 2j we cannot pass by a 14 to a 22 without executing a 15 which ∈ A S1 ).

Schema 3 explains the optimization process. The bold arrows characterize the transitive dependencies between activities invoking the service S 1 . The two boxes represent the patterns to delete from the paths T link 1-22 (b) and T link 1-22 (c) since a 10 , a 11 , a 12 and a 13 / ∈A S1 . Also the path T link 1-22 (d) has to be deleted since it passes by a 19 which executes only if a 15 is executed and a 15 ∈ A S1 . This link is replaced by T link 1-15 and T link 15-22 . This optimization process avoids having unusable synchronization points.

Once optimization is achieved, for each T CDT Sj we build the corresponding sub-process by connecting its composing activities by the set of control flow patterns represented by T CDT Sj (a i , a k ). The sub-process building algorithm is ascendent which means that we begin by EI until reaching EF . In each step we look for the transitive postset of the current activity and the correspondent control path linking it to each of this postset elements. To continue with the same example, the resulting sub-process P S1 is depicted in the figure 4. Activities named a f ictive k are activities which execution time is zero, and used to synchronize and maintain the semantics of the process. To resume, the output of this step is a sub-process for each service and which will be executed by a separate engine.

Interconnecting sub-processes

In this section, we present how to translate the connectivity and communication between activities of the initial process to that between activities belonging to different subprocesses. Both data and control dependencies are taken into consideration. For each activity a i of the initial process, we look from the DCDT for the control dependencies with its postset. According to the patterns linking a i with each of a i • elements, we choose the right connection. In the last three sections, most patterns are taken into consideration. However, in the synchronization phase, we consider only the basic patterns such as AN D sp , AN D j , OR sp , OR j , XOR sp , XOR j and Sequence. Algorithm 3 gives a formal overview of the interconnection process. For a control connector ctr, ctr• is the first activity following ctr. While a ictr • represents the postset of a i through ctr (i.e. in Fig. 2, if a 4 doesn't exist (a 2 {OR 2sp OR 4sp } )• ={a 8 ,a 9 }). First, we

Figure 5. sub-processes interconnection

synchronize the control flow between activities belonging to different sub-processes. We distinguish two cases treated by the algorithm: (i) when two activities a i and a j are linked by only one control pattern, (ii) and when they are linked by a set of control patterns. Next, we consider data flow connections. Data dependent activities are activities which exchange data. For instance, in fig. 2, a 4 needs the data d 1 from a 1 to be executed. As a 1 and a 4 belong to different sub-processes P S1 and P S4 , we have to connect them. The connection is a message exchange where a 1 is the sender and a 4 is the receiver (cf. Fig. 5).

Figure 5 illustrates a part of the interconnection of subprocesses P S1 , P S2 , P S3 and P S4 issued from the decentralization of the process introduced in figure 2. In each of the four sub-processes, we note the presence of OR 1sp which depends on the decision taken by a 1 . Hence, the presence of three dashed arrows C 1 connecting a 1 to each of these patterns. The advantage of connecting a 1 to the patterns instead of a 1 •={a 2 ,a 3 } is the minimization of the exchanged messages number. Typically, if we connect a 1 only to a 1 • and consider that a 3 won't be executed during runtime. In this case, a 3 must inform a 6 and a 7 to be skipped, which may be in other sub-processes and in turn, have to inform their postsets and so on. This leads to a huge number of unusable synchronization messages. However, the other sub processes knew already that a 3 won't be executed as they had received the decision of a 1 . For example, the reception of C 1 by P S3 and P S2 just before OR 1sp causes automatically the non-execution of a 3 and all its next activities until OR 1j in P S3 and a 6 and its next activities in P S2 . Therefore, a 3 doesn't need to inform a 3 • of its non-execution, which in turn, doesn't inform (a 3 •)• and this reduces considerably inter-sub-processes message exchanges. If we consider that a 22 / ∈P S1 , and not preceded by OR 1sp , then we have to connect a 1 to a 22 = OR 1sp •. Because a 22 has to know the number of control messages it has to wait to be executed. Therefore, if a 3 is not executed then a 22 knows in advance that it won't receive a message from a 21 (cf. Fig. 2). The same scenario is done with a 2 ∈P S2 as it is followed by OR 2sp (connexion C 2 in fig 5).

If an activity a i is connected to its postset by Seq, AN D sp , or a set of join-elements then we simply connect a i to a i •. Thanks to our synchronization mechanism, each of a i • knows in advance if it has to wait or not for a message from a i . The last scenario is when a i is connected to a i • by a set of split-elements ctr. In this case, if there is no OR sp in ctr then we simply connect a i to a i •. Otherwise, we connect a i to each OR idsp ∈ctr and we add a connection between a i and OR idsp • if it exists. Note that an OR idsp may belong to many sub-processes in the same time.

During runtime, activities must respect all their preconditions and postconditions before and after execution. Preconditions are control and data connections with each of its preset activities whereas postconditions are control and data connections with each of its postset activities (i.e. in fig. 5, preconditions of a 4 are C 1 , C 2 and d 1 ). Dependent activities may be on other sites or sub-processes. As we mentioned earlier, a connection may be as a message exchange. The latter may be skipped during execution (i.e. in fig 2, if a 3 is not executed, there is no data transfer between a 6 and a 21 since both of them won't be executed.) In some cases, a message must be sent even if the activity is not executed. For instance, even if a 3 is not executed, a 15 must inform a 22 to not wait for d 6 since a 22 execution doesn't depend on a 3 execution. Each message must hold an instance identifier to make correlation between process instances.

In the last three sections we presented techniques to partition a process according to services. This assumes that all business partners or services are assigned to activities before the process instantiation. However, in some cases, the business partners that take part in the instance of a given process may not be known in advance, but selected at runtime. Besides, corporations may operate across organizational boundaries. Consequently, collaborations involve several autonomous organizations which share the same public business process. Partitioning the latter, over the organizations involved, optimizes the flow of work and gives them more autonomy to create or modify the process at any time. To cope with these requirements, other decentralization criteria should be considered. This means that the decentralization is not done according to services, but according to organizations. This approach requires the generation of a sub-process for each organization rather than the generation of a sub-process for each service. This reduces the number of synchronization messages, since the number of sub-processes decreases. It also features the runtime assignment of business partners to process activities in order to provide the adequate flexibility to support dynamic collaborations of business partners. Furthermore, it can improve security conditions such as privacy, since each organi-zation controls its proper process. As a result, the extension of the approach to the different organizational needs demonstrates its flexibility. For the above example, the same algorithms can be simply implemented by grouping activities belonging to the same organization. Hence, instead of building a TCDT for each service, we can build a TCDT for each organization and then the corresponding sub-process. This requires the modification of the same algorithms introduced in section 3. Within the algorithms, the modification of services S j by another criterion (for instance organizations O j or providers P j ...) is enough to switch from one decentralization criterion to another. The decentralization based on services or providers is more suitable when only one organization is involved in the business process. The decentralization according to providers may be more efficient than to services, if the set of services involved in the process that a provider supports, is located on the same site.

Conclusion

This paper has presented an approach to the flexible decentralization of process specifications. The developed approach is applicable to a wide variety of service composition standards that follow the process management approach such as WS-BPEL. In contrast to previous works that take on the process decentralization approaches, our approach is based on the computation of very basic dependencies between process elements that provides a considerable level of understanding and also the flexibility for further manipulation. The computation of basic dependencies have led, in turn, to the re-implementation of the semantics of a centralized specification with peer-to-peer interactions among the derived decentralized process specifications. In addition to the simplicity, the flexibility allows the efficient re-instanciation of the algorithms for the different needs of decentralization and also dynamic collaborations where services are discovered at runtime. We are planning to extend the current approach to support advanced patterns and fault handlers. Our future work includes implementation of the introduced methodology on a web service composition language and a quantitative evaluation of the approach in terms of message exchanges. Another challenge is to take into consideration security aspects between the decentralized process specifications.

Definition 1 (

 1 Process) A process, P , is a tuple (A, D, E c , E d , S P ) where A is a set of activities, D is the set of data, E c is a set of control edges with E c ⊂ A×A×Conds(D), E d is a set of data edges with E d ⊂ A×A×D and S P is a set of web services invoked by the the process activities.

Figure 1 .

 1 Figure 1. Process projection

Figure 2 .

 2 Figure 2. Motivating example

Figure 3 .

 3 Figure 3. Optimization process for P S1

Figure 4 .

 4 Figure 4. sub-process P S1 of service S1

Algorithm 3 :

 3 Sub-processes interconnectionRequire: -DCDT // Direct Control

Table 1 . Direct Control Dependency Table DCDT EI

 1

a 1 : s 1 a 2 : s 2 a 3 : s 3 a 6 : s 2 a 12 : s 9 ... a 18 : s 10 a 21 : s 6 a 22 :

Algorithm 1 :

 1 Transitive Control Dependency Tables Building Require: -DCDT // Direct Control dependency Table -S // set of services invoked by the process -AS j // set of activities invoking service S j for each service Sj∈S do Create T CDTS j // card(AS j )×card(AS j ) TCDT for each service Sj ∈S the service S1 is resumed in the table 2 which is interpreted as follows: • line i : represents the transitive postset of a k and the set of control flow patterns linking them. The transitive postset of a 1 is {a 8 , a 15 , a 22 } • column j : represents the transitive preset of a k and the set of control flow patterns linking them. The transitive preset of a 22 is {a 1 , a 8 , a 15 } • (line i , column j ): corresponds to the set of control flow patterns that links activity a k to a l if it exists.

	Current activity ← EI
	Current set←{EI}
	while Current set ={∅} do
	Delete Current activity from Current set
	P ostset ← (Current activity)•
	T Dep set ←{∅}
	for each ai∈ P ostset do
	Ctra i ← DCDT (Current activity,ai)
	Add (ai, Ctra

i ) to T Dep set repeat for each (ai, Ctra i ) ∈ T Dep set do if ai∈AS j then Add Ctra i to T CDTS j (Current activity,ai) if ai / ∈Current set and ai =EF then Add ai to Current set else for each a k ∈(ai)• do Ctra k ←Ctra i +DCDT (ai, a k ) if (ai, Ctra i ) / ∈ T Dep set then Add(ai,Ctra i ) to T Dep set Delete (ai, Ctra i ) from T Dep set until T Dep set = {∅} Current activity← First elem(Current set) Result:

Table 2 . Transitive Control Dependency Table for service S1 :

 2 OR 1sp , OR 2sp , OR 5sp , OR 5j , OR 2j , OR 1j -OR 1sp , OR 3sp , AND 1sp , AND 1j , OR 3j , OR 1j OR 1sp , OR 3sp , AND 2sp , AND 2j , OR 3j , OR 1j

	T CDT S1

CDT

  Sj , by deleting every two corresponding split and join patterns having no activities a i ∈A Sj between them (i.e. in table 2 corresponding to T CDT S1 we delete OR 5sp and OR 5j since a 10 and a 11 / ∈A S1

  Dependency Table -DADT // Direct Data Dependency Table -The set of sub-processes for each ai ∈A do // Control dependencies interconnection CT Ra i ← {∅} for each aj∈ (ai)• in DCDT sas aj / ∈Ps a i do if ctra ij / ∈ CT Ra i then CT Ra i ← CT Ra i S ctra ij for each ctr∈CT Ra i do if ctr∈ {Seq, AN Dsp} S set of join-elements then connect(ai, ai ctr •) if ctr = ORsp id or ctr=XORsp id then for each Ps k sas ∃ ctr k = ctr do connect(ai, ctr k ) connect(ai, ctr•) if ctr is a set of split-elements then if ∃ ORsp id ∈ ctr then connect(ai, ai ctr •) else for each ORsp id ∈ ctr do for each Ps k / ∃ ctr k = ORsp id do connect(ai, ctr k ) connect(ai, ORsp id •)

	// data dependencies interconnection
	Lookup in DADT for ai•
	connect (ai, ai•)
	Result: Interconnected sub-processes