Keywords: Workflow, P2P computing, Program Partitioning, Business Process Management, Dead Path Elimination Workflow, Système d'Information Egal-à-Egal, Partitions des Programmes, La

There has been a great deal of interest in recent years in the use of service oriented approach and relevant standards to implement business processes. Following the concepts of workflow-based process management, the major focus has been on service composition. Not surprisingly, this default composition approach suffers from the limitations of centralized workflow management. It is well recognized that a decentralized execution setting where composed services can establish P2P interactions, is central to a wide range of ubiquitous, mobile, large-scale and secure business process management. A natural way to enable the decentralized execution is to implement the relevant distributed cooperating processes of a centralized process on composed services. In this way, composed services can establish P2P interactions following the semantics of their processes. In this report, we present a generic approach that enables decentralized executions with such cooperating processes. Precisely, we present our method that derives the latter. We focus on the sophisticated control/data flow, conversational aspects and especially Dead Path Elimination that run counter to naive intuition, most of which, we explain using deeper analysis of the algorithms and data structures that we employed.

Introduction

Recent advances in service oriented computing and related standardization efforts have made the realization of B2C and B2B applications not only inexpensively feasible but also increasingly popular. The very recent efforts were spawned primarily from a need to express service compositions unambiguously, and to make compositions amenable to formal manipulations as analogous to classical workflow-based process management and component-oriented computing [START_REF] Weerawarana | Web Services Platform Architecture[END_REF]. WS-BPEL (previously BPEL4WS or BPEL for short) [START_REF]and Siebel Systems. Business Process Execution Language for Web Services, version 1.1[END_REF] which is currently being standardized by OASIS [START_REF]Organization for the advancement of structured information standards (oasis[END_REF] characterizes the current state of art in this field. On the other hand, standard process specifications allow modeled processes to be exchanged between different organizations/tools and executed without major architectural constraints [START_REF] Carzaniga | Designing distributed applications with mobile code paradigms[END_REF].

Typically, a service composition is based on a centralized execution model. This means that composed services do not have direct interconnections with each other.

As the relevant research literature on process management confirms [START_REF] Casati | Adaptive and dynamic service composition in flow[END_REF][5] [START_REF] Yildiz | Enhancing secured service interoperability with decentralized orchestration[END_REF], there are several different motivations to enable decentralized execution settings where composed services can establish P2P interactions. We use the terms decentralized orchestration and decentralized workflow (process) management to describe this mode of operation. Although the latter is not a new idea [START_REF] Alonso | Exotica/fmdc: A workflow management system for mobile and disconnected clients[END_REF][20], previous propositions have not found their widespread applicability in practical settings. Their slow acceptance is often attributed to, among other things, their architectural assumptions on process participants [START_REF] Ben Lakhal | Throws: An architecture for highly available distributed execution of web services compositions[END_REF][16] such as additional software layers. These assumptions become more unreasonable in the Web context as they are contradicting to the autonomy of services.

We believe that the secondary outcome of process specification standards, which is the interchangeability issue of processes between organizations, can make decentralized orchestrations inexpensive and reasonable to provide. Intuitively speaking, a process modeled by an organization can be received and executed easily by another one. From this point of view, if organizations execute relevant processes for the purpose of an overall composition, they can establish P2P interconnections following the semantics of the processes that they execute. At middleware level, this can be implemented with services that are invokable with processes rather than simple input values. The above motivations highlight the problems of arriving at a definition of an accurate operation that derives such processes executed by composed services i.e. how a control or data dependency of the centralized specification can be reestablished and preserved in a decentralized orchestration?

In this report, we describe and exemplify such a method that enables the decentralized orchestration. Our proposition does not attempt to discuss the feasibility of the whole issues of a centralized orchestration in a decentralized one. We discuss the paramount aspects such as Dead Path Elimination (DPE) and we propose corresponding solutions that run counter to naive intuition. Our proposition relies on well-known concepts of inter-organizational processes [START_REF] Wil | Interorganizational workflows: An approach based on message sequence charts and petri nets[END_REF] and workflow literature [START_REF] Leymann | Production Workflow -Concepts and Techniques[END_REF].

INRIA

The remainder of this report is organized as follows: Section 2 presents some preliminary concepts. Section 3 presents a formal process specification model. Section 4 presents the core of our contribution. Section 5 reviews the very related works while last section concludes.

Background

In this section, we review some general concepts of the workflow literature that are relevant to our work and we overview our approach.

Dead Path Elimination

Dead Path Elimination (DPE) is a particular procedure that most centralized workflow management systems support. Basically, it can be explained as follows: In some instances of some process models, some control paths may not be executed due to different transition conditions. If these control paths lead to a join activity, the latter may not be executed as it will wait the termination of all incoming branches [START_REF] Leymann | Production Workflow -Concepts and Techniques[END_REF]. DPE consists of the resolution of such blocking situations.

Example 1 (Simple Dead Path Elimination) Consider the process model depicted in figure 1. The example consists of a claim handling process executed by an insurance company. The first activity is the Inspection that consists of the examination of the claim. According to the outcome of this activity, the claim is reimbursed or refused. If the claim is reimbursed then the Bank Order activity is executed, otherwise this activity is not executed. Prepare Report and Delivery Provisioning activities are executed in both cases. The Prepare Report activity consists of the preparation of inspection results to be archived by the insurance company. The Delivery Provisioning activity prepares a delivery service that will transfer the inspection result to claim's owner. Delivery activity is executed after the termination of all preceding activities. In this example, Delivery activity is the join activity and the path that includes Bank Order may not be executed. For an instance of the process, if the Bank Order activity is not executed, the corresponding join condition from Bank Order to Delivery will never be evaluated. Consequently, this instance will never terminate. DPE deals with this situation by evaluating all incoming transition of Delivery activity.

Inspection

DPE computes recursively transitive closures until join activities and treats all transition conditions. Thus, the incoming transitions of a join activity are always evaluated. Interested are referred to [START_REF] Leymann | Production Workflow -Concepts and Techniques[END_REF] for the formal definition of DPE in centralized workflow management. It is fair to say that DPE procedure is extensively studied in centralized workflow management [START_REF] Leymann | Production Workflow -Concepts and Techniques[END_REF] [START_REF] Wil | Workflow patterns[END_REF]. However, it needs reconciliation in decentralized workflow management.

Decentralized Orchestration

A Decentralized orchestration setting where composed services of a process can establish P2P interconnections can be enabled by several different manners. The most intuitive solution that can enable the decentralization is to implement some additional functionalities on composed services (e.g. [16][22]). Thus, in addition to their advertised behavior, composed services can support necessary explicit coordination features with each other. As we mentioned earlier, this solution can be efficient if composed service support such assumed functionalities. However, it is not reasonable to make architectural assumptions in the Web context as the latter are contradicting to the autonomy of services. Another way to enable decentralized orchestration is to compose services that advertise interfaces that support sophisticated interaction with each other. In this case, the challenge is to check the structural consistency of different service interfaces (e.g. [START_REF] Wombacher | Decentralized consistency checking in cross-organizational workflows[END_REF]). It should be noted that, this kind of decentralized orchestration assumes the presence of services that can interact with each other. Our last consideration of decentralized orchestration, which is also the approach that we adopt in his report, is to have a centralized specification that composes a number services and to derive corresponding cooperative distributed processes of this centralized specification. Thus, each composed service can execute a process that interacts with other services that execute their corresponding processes. This approach assumes that services can receive and execute relevant processes. In contrast to pre-SOA propositions, this assumption is reasonable. Because, services advertise their capabilities that are already implemented by sophisticated processes beyond their interfaces and consequently, they dispose process execution environments. In addition to this assumption, XML based process specifications such as BPEL allow modeled or instantiated processes to be easily exchanged between organizations (services). To get a better understanding of our decentralization approach, let us consider the process depicted in figure 2 . This dependence is expressed with the data edge d 5 . This process can be executed by a centralized process execution engine (orchestrator, e.g. BPWS4J). In a centralized execution, services are isolated from each other. They interact only with a single service that orchestrates them. At this point, it may be of interest to provide a decentralized orchestration setting where services establish direct interconnections. For example, let's take a 3 and a 5 activities that consist of the respective invocations of services s 3 and s 5 . In a decentralized execution s 3 and s 5 can route their outcomes (d 3 and d 2 ) directly to s 16 that is invoked with the execution of a 16 . Similarly, in order to respect the control flow, s 15 invoked with a 15 can inform s 16 about the termination of the operation invoked by a 15 . The same P2P interactions can be considered for all data and control edges. In order to enable such interactions, our approach derives processes to be executed by orchestrated services. The latter are called peer processes. Peer processes are derived from the centralized process specification. The interactions of peer processes are the decentralized implementation of the control and data dependencies of underlying services of the centralized specification.

With this approach, s 3 and s 5 execute respectively their peer processes denoted P s3 and P s5 . The activity that receives the output of a 5 from P s5

Process fragments Figure 3: Motivating example: Decentralized process fragments a 5 . s 15 executes P s15 and sends a control message to s 16 that includes an information about the termination of a 15 . s 16 that executes P s16 includes receiving activities that collect the sent control messages and the data to use as the input of a 16 and executes a 16 . Thus, the semantics of centralized process are preserved with P2P interactions. Figure 3 depicts the decentralized implementation of the above interactions. As we mentioned earlier, the challenge of our work is to derive and deploy peer processes.

Decentralize orchestration must deal with some additional issues that are not extensively studied in the centralized workflow management. As we showed in the above example, the first issue that is taken into account, is different data dependencies of process activities. As centralized workflow management systems are empowered by centralized databases that store and manage process data, the process model does include explicit data dependencies. Data dependencies of the process activities can exist INRIA under different forms. The data dependencies of our modeling include only input and output mappings between different activities. For example, we do not consider concurrent data access of parallel activities. The data dependencies exist along control paths. This means that if there is a data dependency between two activities a i and a j , there is also a control path from a i to a j .

Design Choices and Assumptions

Although we claim to provide a decentralized orchestration setting inexpensive to implement, it is necessary to review some of our general assumptions.

• Asynchronous communication. The underlying communication among orchestrated services is based on asynchronous communication that is the commonly implemented interaction modality over the Web. In this modality, the writing into a asynchronous communication channel is not blocking while the reading from a channel is blocking if the expected data is not available yet. We assume that asynchronous communication channels are perfect. i.e. messages sent along channels are not lost.

• Structured processes. Decentralized processes are structured processes [START_REF] Kiepuszewski | On structured workflow modelling[END_REF]. This means that different activities are structured through control elements such as AND-split, AND-join, OR-split, 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 is a reasonable assumption as it is possible to transform arbitrary processes to their structured equivalent.

Global Soundess

Our method that derives peer processes is based on a well-known criterion that must be considered for cooperating processes. In [START_REF] Wil | Interorganizational workflows: An approach based on message sequence charts and petri nets[END_REF], Van Der Aalst has proposed a simple but powerful correctness criterion (global soundness) for cooperating inter-organizational processes. Basically, this criterion states that each process involved in an asynchronous composition must terminate and upon termination, its asynchronous communication channels must be empty. If all of the composed processes are known, the global soundness can be automatically verified. If a global view of composed processes is not achievable, the same criterion or similar ones that replace the latter can be verified with alternative approaches such as [START_REF] Wombacher | Decentralized consistency checking in cross-organizational workflows[END_REF]. When we provide peer processes, we rely on the original global soundness criterion. In contrast to all previous works in this field, our aim is not to verify the global soundness of existing processes but provide peer processes that will satisfy it. So, intuitively speaking our approach is feasible as the complete centralized specification is known and its corresponding peer processes are produced prior to execution.

Formal process modeling

The operation that derives peer processes that satisfy the global soundness is fairly sophisticated. The complexity of the former is directly related to the complexity of the decentralized process specification that can include control and data edges and conversational activities in various combinations. This section presents a formal process model that is necessary for a rigorous reasoning.

A process that subjects service composition can be considered as a graph-oriented message passing program [START_REF] Weerawarana | Web Services Platform Architecture[END_REF].

Definition 1 (Process) A process, P , is a tuple (A, E c , E d , C), where A is a set of activities, E c is the set of control edges with E c ⊆ (A ∪ C) × (A ∪ C), E d is a set of data edges that interconnect process activities with E d ⊆ (A × A) and C is a set of control
connectors that characterize different transition conditions of control edges.

A process activity a ∈ A consists of a one-way or bi-directional interaction with a precise service. So, each activity refers to its interacted service. The set of activities that refer to the same service s i is noted as A si . A process has a unique start activity that has no predecessors and has a unique final activity with no successors. A control edge from an activity a i to another activity a j means that a j can not be executed until a i has reached the completion state. A data edge exists between two activities if a data is defined by an activity and referenced by another without interleaving the definition of the same data. We limit our considerations with concurrent and selective concurrent branchings that are described with AND-split, AND-join, OR-split and OR-join patterns. In order to express control paths of process activities, we use a precedence relationship denoted <. It is a partial order defined over A×A that characterizes the existence of a control path between two activities. As a first step to reason with the complexity of the decentralization operation, we need to formally define different dependency types that can exist with regard to the expected interactions of underlying services and their peer processes. The model we use for this purpose, extends traditional < to the notions of strong/weak forward and backward orders. In the following notations, OR is used to denote a process fragment that begins with an OR-split and terminates with its corresponding OR-join. For any control connector cc, cc denotes its corresponding split or join connector. Similarly, for an activity a i that precedes a split point, a i denotes an activity that succeeds its corresponding join point and vice-a-versa.

Definition 2 (Strong/Weak Forward and Backward Orders) Let a i and a j denote two activities. There are four possible order relations between them:

• Strong forward order (< s ): The order of a i and a j is a strong forward order (denoted a i < s a j ) if the following hold:

a i <a j , cc ∈ {OR-split} s.t. (a i <cc) ∧ (cc<a j ) ∧ (a j < cc) INRIA • Weak forward order (< w ):
The order of a i and a j is a weak forward order (denoted a i < w a j ) if the following hold: a i <a j , ∃cc ∈ {OR-split} s.t. (a i <cc) ∧ (cc<a j ) ∧ (a j < cc)

• Strong backward order (> s ): The order of a i and a j is a strong backward order (denoted a i > s a j ) if the following hold:

a i <a j , cc ∈ {OR-join} s.t. (a i <cc) ∧ ( cc<a i ) ∧ (cc<a j )
• Weak backward order (> w ): The order of a i and a j is a weak backward order (denoted a i > w a j ) if the following hold:

a i <a j , ∃cc ∈ {OR-join} s.t. (a i <cc) ∧( cc<a i ) ∧(cc<a j )
The above relationships formalize control dependencies of activities that are not directly connected by control edges with their possible pairwise completion states. For example, the weak forward order a 0 < w a 4 means that a 4 may not be executed after a 0 . The weak backward order of a 5 > w a 16 means that at the moment a 16 is executed, a 5 might not have been executed because of the selective path that it is on. Contrary, a 10 < s a 16 and a 10 > s a 16 mean that the execution of a 16 always follows the execution a 10 and vice-a-versa if a 16 is executed, a 10 must have been executed previously.

As second step, we project the weak/strong dependencies on data edges that interconnect activities along the control paths. A data edge that interconnects two activities, has two properties out of four that are strong source/strong target (d ss,st ), strong source/weak target (d ss,wt ), weak source/strong target (d ws,st ) and weak source/weak target (d ws,wt ). Formally, the property of a data edge is defined as below.

Definition 3 (Data edge property

) Let d ∈ E d with a i = source(d) and a j = target(d). d =        d ss,st ⇔ (a i < s a j ) ∧ (a i > s a j ) d ss,wt ⇔ (a i < w a j ) ∧ (a i > s a j ) d ws,st ⇔ (a i < s a j ) ∧ (a i > w a j ) d ws,wt ⇔ (a i < w a j ) ∧ (a i > w a j )
The semantics of these properties can be explained as follows: Let's take d ws,st 2 with source(d 2 )=a 5 and target(d 2 )=a [START_REF] Schuler | Peer-to-peer execution of (transactional) processes[END_REF] . This means that if a 5 is executed, its output is used as one of the inputs of a 16 . Otherwise, the relevant input of a 16 is not initialized. Similarly, for d ss,wt 1 , if a 4 is executed, its input is initialized with the output of a 0 . Otherwise, the output of a 0 is not used. The last step of our formal consideration is the generalization of the incoming and outgoing dependencies of an activity. We associate two sets to each activity in order to gather the source of incoming and the target of outgoing edges.

Definition 4 (Preset)

The preset of an activity a is denoted

•a. •a = {(a j , e) ∈ A×(E c ∪E d ) s.t. source(e) = a j ∧ target(e) = a i }.
The preset activities of an activity a i consists of activities that have outgoing control/data edges that have a i as the target. When activities are gathered in presets and postsets, we denote them as tuples with the relevant data or control edge. For example, •a 16 ={(a 3 , d ws,st 3 ), (a 5 , d ws,st 2), (a 10 , d ss,st 5), (a 11 , d ss,st 4), (a 15 , c)}. Note that we consider control edge pairs that include control connectors as single control edges that interconnect the activities that precede and succeed the connectors. The postset activities of an activity a i consist of activities that have incoming control/data dependencies that have a i as source. For example, a 11 •={(a 16 , d ss,st 4), (a 12 , c)}.

For notational purposes, we use the activity identities to identify preset and postset elements. For example, for (a 16 , d ss,st 4 )∈a 11 •, we denote a 16 ∈a 11 •. The elements of preset and postset are gathered into subsets with respect to the properties of their edges.

•a i,ws , •a i,ss , •a i,wt , •a i,st , a i,c ⊂•a i denote respectively the elements of •a i that consist of data edges with weak/strong sources, weak/strong targets and control dependent activities. For example, •a 16,ss ={(a 10 , d ss,st 5), (a 11 , d ss,st 4 )} and •a 16,c ={(a 15 , c)}. For postset elements, they can be noted such as a 11,c •={(a 12 , c)} and a 11,ws •=∅.

Decentralized Orchestration

Principles of Decentralized Orchestration

Peer processes can be derived by employing various data structures and algorithms. Our method associates the activities of the centralized specification to the peer processes of the services that they refer to. So, the elements of A si are included in the peer process P si that is executed by s i . In order to preserve the semantics of the centralized specification with P2P interactions, the activities dispatched in different peer processes must be wired. Figure 4 depicts a simple wiring example of two control dependent activities across their corresponding peer processes. a 1 and a 2 consist of the respective invocation of s 1 and s 2 . In a decentralized orchestration, a 1 and a 2 are included respectively in P s1 and P s2 that s 1 and s 2 execute. When P s1 executes a 1 , it must inform P s2 about the termination of a 1 . Thus, P s2 can execute a 2 . Consequently, the control dependency of the centralized specification is preserved in a decentralized implementation. In P s1 , the message that must be sent to s 2 is denoted a 1 (t) while the activity that sends this message is denoted a w 1→2 (a 1 (t)) (superscript is used for writing). In fact, a 1 (t) characterizes the completion state of a 1 with a "true" message. The sent message is received with the execution of activity a r 1→2 (a 1 (t)) in P s2 (superscript is used for reading). This intuitive peer process deriving approach works just fine for stateless and simple control interactions. However, the complexity of peer process structuring inevitably arises in more sophisticated processes. For example, let's suppose that a 1 and a 2 are interconnected by a data edge d k and a 1 > w a 2 (cf. figure 5). In P s1 , a 1 may not be executed. In this case, a r 1→2 (d k ) blocks P s2 as it will never read a data sent by P s1 . In order to prevent these kinds of blockage, a r 1→2 (d k ) activity must be skipped in P s2 if it is sure that the expected data will not be received. Similarly, if two activities a 1 :s 1 a 2 :s 2 d k Figure 5: Data dependency along a weak control path a 1 and a 2 are interconnected by a data edge d k and a 1 < w a 2 , the output data of a 1 may not be used as the input of a 2 if the control path that includes a 2 is not executed (cf. figure 6). When P s1 that executes a 1 sends d k to P s2 that executes a 2 , d k may not be consumed and may remain in the communication channel. Consequently, P s1 cannot terminate properly as it disposes an unconsumed data in its communication channel. So, the structuring of peer processes must deal with the particular consequences of different control/data dependencies that can violate the global soundness. More generally, when a data edge with d ws,wt or d ss,wt properties is wired across two peer processes, the sent data may not be consumed if the receiving peer process does not execute the target activity.

Wiring Activities Across Peer Processes and DPE

In order to deal with the above situations that can violate the global soundness, we propose a peer process structuring mechanism that propagates the states of activities that are not executed to relevant peer processes to allow to skip activities that can block them. To formalize interactions of peer processes, we make the following considerations: For each activity that precedes an OR-split point, some of outgoing branches can evaluate to "false". At this point, the DPE procedure is started to allow the activation of the activity that follows the corresponding OR-join. Thus, false transition values are propagated along the paths that are not executed. However, DPE does not influence activities that have incoming data edges with their sources on paths taken by DPE. We propose to extend the DPE mechanism toward such activities. Consequently, they can be informed about the state of activities that are at the source of data edges. The activities that ensure the wiring of process activities across different peer processes and their content are noted as follows: The "true" and "false" values corresponding to the state of an activity a i are denoted respectively a i (t) and a i (f ). As we mentioned above, an activity that sends (resp. receives) a process data or an activity state to (resp. from) another peer process is characterized with the corresponding identities of source and target activities such as a i→j that come before (resp. after) their execution. Receiving activities have r as superscript while sending activities have w . The information carried by the latter is denoted such as a w i→j (a i (t)) , a r i→j (a i (t)), a w i→j (a z (t)), or simply a w i→j (d i ) if it carries a process data d i .

INRIA

Example 2 (Dead path elimination and data dependencies) Figure 7 depicts the motivating example. Activity a 0 precedes an OR-split point that DPE procedure can be triggered for outgoing paths. If the path that goes through a 1 evaluates to false, the activities between a 0 and a 10 are not executed as this path is dead. This means that the output of a 5 is not used as one of the inputs of a 10 . As these activities are executed within different peer processes, they must be wired together to implement underlying dependencies. The peer process that executes a 16 , must execute an activity which receives d 2 from the peer process that is expected to execute a 5 . However, if a 5 is not executed, the receiving activity of a 16 blocks as it never reads any data. Naturally, the peer process of a 16 must be informed about the state of a 5 whether it is executed or not. The question is which peer process informs the peer process of a 16 .

The peer process that executes a 0 can evaluate the path that goes across a 1 to "false". At this point, the peer processes that expects the output of a 5 can be informed.

Moreover, the peer processes including other activities that are on this dead path, must be informed in order to let their peer processes to skip these activities. As the peer process of a 0 evaluates this path, it can inform all of the concerned activities. In figure 7, the red arrows express these dependencies. However, if the transition condition of a 0 and a 1 evaluates to "true", the peer process of a 0 informs only the peer process of a 1 about the evaluation of the transition dependency. Thus, a 1 is executed in its peer process.

Example 3 (Wiring Activities Across Peer Processes and DPE)

Figure 8 shows the same example with the transitions of (a 0 and a 2 ) and (a 0 and a 3 ) that evaluate to "false".

RR n°6131

As one of the inputs of a 16 is initiated by a 3 , the peer process of a 16 must be informed about the state of a 3 which is on a dead path. As the peer process that evaluates transition condition sends relevant messages to the peer processes that must be informed about dead paths, these peer processes must include activities that execute collect the message that can be sent by other peer processes. If we consider that the centralized specification can include nested OR-split and OR-join points, the DPE can be started by different peer processes that execute the activities that precede OR-split points. Consequently, the peer processes that receive DPE information must include relevant activities that can receive these message from different peer processes.

Example 4 (Wiring Activities Across Peer Processes and DPE) Figure 9 depicts the same motivating example. One of the inputs of a 16 is initiated with the output of a 5 . Activity a 5 is preceded by two OR-split points. Thus, DPE that takes a 5 can be triggered by two different peer processes that execute a 0 or a 1 . Consequently, the peer process that executes a 16 can be informed these peer processes. The green arrow characterize these dependencies. It should be noted that the receiving activities are exclusively structured as DPE is triggered once.

Not surprisingly, the challenge of DPE elimination in decentralized process executions consists of structuring peer processes in a such way that they deal with the correct exchange of messages with each other. In order to do so, we examine peer process deriving and structuring within two subsections. The first consists of structuring activities that send messages to other processes. The second consists of structuring activities that collect messages sent by other processes. The structuring mechanism computes each activity a i of the centralized specification and derives relevant process fragments that must be executed before and after a i . The latter are denoted •a i and a i •.

Wiring with Postset Elements

Here, we describe how a peer process behaves after the execution of one of its activities to wire it with its dependent activities. The structure a i • describes a process fragment that the peer process executes following the execution of its activity a i . a i can be an activity that precedes a OR-split point or not. If so, it is the starting point of DPE. In our approach to decentralized orchestration, DPE is achieved with P2P interactions.

The peer process that executes a i informs directly the corresponding peer processes of activities that are on the paths taken by DPE. In the same time, the status of activities that are on the paths taken by DPE are propagated to peer processes that expect their outcome. If a i is not an OR-split activity and its outgoing control edges evaluates to true, its peer process sends "true" control messages to the peer processes of the control dependent postset activities.

Algorithm 1 defines the part of the structuring operation of a i •. In the notations, ⊕, ||, + denote respectively exclusive, concurrent and sequential append operations to a process fragment. for all an ∈ A s.t. ∃a k ∈ •an,ws, cc ∈ {OR-split}, (aj

< a k ) ∧ (a k < b ai) ∧ (cc < a k ) ∧ (ai < cc) ∧ (a k < b cc) do 15: a OR/true j || ← a w i→n (a k (t)) 16:
end for 17: •a n ⊕ a m is denoted, a n and a m are exclusively structured and added concurrently to a i with existing ones. Figure 10 depicts this notation.

f ai• || ← (a w i→j (ai(f )) + a OR/false j ) ⊕ (a w i→j (ai(t)) + a OR/true
The algorithm operates on each activity of the centralized specification. It should be noted that a i • is executed following the execution of a i . If a i is skipped, because it is on a path taken by DPE, the activities of a i • are skipped in the same peer process.

Informally, the algorithm can be described as follows: For each control dependent activity a j that follows a i , two fragments that correspond to "true" and "false" transition conditions of a j are derived. These are characterized as a OR/false j (line 2-8, and line 9-13) (line 14-16). a OR/false j include activities that send "false" messages to peer processes that execute activities that are on the paths taken by DPE (line 4). Moreover, activities that send "false" messages to peer processes that have incoming data edges from the activities of DPE are included in a OR/false j (line 11). a OR/true j includes activities that send "true" messages to peer processes that have incoming data edges from the activities that are not taken by DPE (line 15). Note that, we take nested OR-split/ORjoin fragments into account. These two fragments are structured sequentially after the corresponding "true" and "false" control messages that can be sent to a j . The latter are exclusively structured (line 17). The last step of a i • is sending the outputs of a i to peer processes that expect them (line 20). An unique activity F a i characterizes an empty activity added at the end of a i •. It is wired with the empty start activities of other activities a∈A si that follow a i with respect to their partial order. This operation is detailed in the next subsection.

INRIA a i a m a n a m-1 a n-1
Example 6 (Wiring with postset activities) Let's suppose that activities a 0 and a 11 depicted in figure 11 consist of the invocations of different service s 1 's operations. In P s1 , after the execution of a 0 , one of the paths that go to a 1 and a 2 can evaluate to "false". In P s1 , a 0 is followed by two concurrent branches that are followed by two exclusive branches that correspond "false" and "true" control messages to be sent to peer processes that include a 1 and a 2 . We can denote

a 0 • = [(a w 0→1 (a 0 (t)) + 1) ⊕ (a w 0→1 (a 0 (f )) + 2)] || [(a w 0→2 (a 0 (t)) + 3) ⊕ (a w 0→2 (a 0 (f )) + 4)]+a w 0→4 (d 1 )+ F a 0 .
The activities that send control messages to the peer processes that execute the elements of a 0,c • are followed either by activities that fulfill DPE or inform peer processes about the status of activities that are not on the paths taken by DPE. Thus,

1 = ∅, 2 = [a w 0→4 (a 1 (f ))||a w 0→5 (a 4 (f ))|| a w 0→7 (a 1 (f ))||a w 0→9 (a 5 (f )) ||a w 0→9 (a 8 (f ))] + [a w 0→16 (a 5 (f ))], 3 = [a w 0→10 (a 2 (t))], 4 = [a w 0→6 (a 2 (f )) || a w 0→3 (a 2 (f )) || a w 0→10 (a 3 (f )) || a w 0→10 (a 6 (f ))] + [a w 0→10 (a 2 (f )) || a w 0→16 (a 3 (f ))].
The activity F a 0 is connected to S a 11 . a 11 is the last element in P s1 . If there were other a i ∈ A s1 that a 0 <a i and a i ||a 11 , F a 0 would be inter- connected to their S a i . For a 11 , a 11 • can be denoted as follows: processes that executes a 0 (P s1 ), must send the peer processes that execute the target activities pointed by red arrows if the transition of a 0 and a 1 evaluates to "false".

a 11 • = a w 11→12 (a 11 (t)) + a w 11→16 (d 4 ) + F a 11 .
In contrast to the above example, figure 13 depicts the example if the transition condition of a 0 and a 2 evaluates to "false". The peer processes that execute a 10 and a 16

receive messages as they have incoming data edges coming from the activities that are on the paths taken by DPE.

Wiring with Preset Elements

Wiring with preset activities consists of identifying the behavior of a peer process before executing or skipping an activity a i . The structure •a i describes the corresponding process fragment to an activity a i . First, before executing an activity a i , its peer process must collect the control messages that correspond to the termination of control dependent preset activities of a i . It must be noted that control messages about the termination of control dependent preset activities are always received. According to the content of the latter, a i can be executed or skipped. If a i is executed (because all of the received messages contain "true" values or one of them contain "true" for a i that is a OR-join activity), the input values of a i must be initialized with the outcome of executed preset activities. At this point, the peer process that intends to execute a i , must execute the activities that collect the sent data. In order to do so, it must test the state of source activities. If the source of activities are executed, the activities that collect the relevant data can be executed. Algorithm 2 resumes the operations that structure the elements of •a i . S a i is an empty activity placed at the beginning of •a i to connect the latter with previous elements of the same peer process. The algorithm can be explained as follows:

If a i is on paths that can be taken by DPE, the peer processes that execute activities that precede OR-split points can send the messages that contain "false" message for all elements of •a i,c (line 2-8). If the immediate precedent activity is executed, the "true" message is received only from the peer process that executes it (line 6). The activities that collect status of control dependent preset activities are structured exclusively as there is a single peer process that can send the corresponding message (line 4 and line 6). According to the content of control messages, a i can be executed or skipped. a + i and a - i characterize the beginnings of two exclusive branches that respectively execute or skip a i (line 19). a + i is followed with the execution of fragment a + i . a + i includes activities that collect "false" or "true" messages that can come from the peer processes that can start DPE that the activities of •a i,ws are on (line 9-18). The activities that collect "true" messages are followed by activities that read the sent data (line 14). The last step of •a i is the collection of data that are sent by peer processes that execute the elements of •a i,ss (line [START_REF] Wodtke | The mentor workbench for enterprise-wide workflow management[END_REF][START_REF] Wombacher | Decentralized consistency checking in cross-organizational workflows[END_REF][START_REF] Yan | Swindew -a peer-to-peer based decentralised workflow management system[END_REF]. It should be noted that the latter do not require the execution of activities that test the status of source activities. a - i that corresponds to the start of the exclusive branch that is executed if a i is taken by DPE, is interconnected to F a i . Consequently, this operation enables the following activities of the same process with respect to their partial order.

Example 8 (Wiring with Preset Activities) Let's suppose that a 4 and a 16 depicted in figure 14 consist of the invocations of different s 2 's operations. In P s2 , a 4 is preceded by two OR-split points which means that its path can evaluate to "false" at these two different points. Consequently, the peer processes that execute a 0 or a 1 can send "false" control message for the control dependent preset activities of a 4 . If the path of a 4 is not taken by DPE, the peer process of a 1 sends "true" control message to P s2 . After the reception of control messages, a 4 can be executed or skipped. If it is executed, its inputs must be collected from peer processes that execute source activities. Thus, a + Algorithm 2 Wiring with preset activities Require: ai, Centralized Process Ensure: f

•ai end for 16:

1: f •ai + ← S
f a + i || ← •a OR j 17:
empty( •a OR j )

18: end for that executes a 0 . As •a 4,ws is empty, there is no need to test the source of incoming edges. We can denote

19: f •ai + ← (a + i + f a + i ) ⊕ (a - i
•a 4 = S a 4 + [a r 0→4 (a 1 (f )) ⊕ a r 1→4 (a 1 (f )) ⊕ a r 1→4 (a 1 (t))] + [(a + 4 + a r 04 (d 1 )) ⊕ a - 4 ]
. The activity a - 4 is interconnected to S a 16 . For a 16 , there are four preset activities (a 3 , a 5 , a 10 , a 11 ) that provide inputs to a 16 . Two of them may not be executed (a 3 , a 5 ). Consequently, the "false" status of these activities can be sent to P s2 by the peer processes that can start DPE. The "true" status message can be sent only by the peer process that executes the first OR-split point that precedes the source activity of data dependence. Activities a 10 and a 11 are strong source activities. Consequently, there is no necessity to test their status. The activities that collect d 4 and d 5 are executed before executing a 16 . We can denote •a 16 as follows •a 16 = S a 16 + a r 15→16 (a

15 (t)) + [(a r 0→16 (a 3 (f ))⊕a r 2→16 (a 3 (f ))⊕(a r 2→16 (a 3 (t))+a r 3→16 (d 3 )))||(a r 0→16 (a 5 (f ))⊕a r 1→16 (a 5 (f ))⊕ (a r 1→16 (a 5 (t)) + a r 5→16 (d 2 )))] + [a r 10→16 (d 5 )||a r 11→16 (d 4 )].
In figure 14, the green arrows depict the control messages that can be received by the peer process that executes a 4 (P s2 ) if it is on a path taken by DPE. If the DPE is started by the peer process of a 0 , the former can send a control message to P s2 to allow it to skip a 4 . Similarly, the peer process that executes a 1 can evaluate the path of a 4 to "false", then the peer process of a 4 must receive a control message from the peer process of a 1 and skip a 4 . If the path of a 4 is not taken by DPE, the peer process must wait for a control message to execute a 4 . This message can be only sent by the peer process of a 1 as it is the control dependent activity that precede a 4 in the centralized specification. Again, it should be noted that the activities that collect the messages sent by other peer processes are structured in a way that they do not subject blocking reads. For example, if an activity subject DPE that can be triggered by n different peer processes, the control messages that allow its process to skip this activity, are exclusively structured as there is only one peer process that can send the "false" control messages.

Example 9 (Wiring with preset activities) In figure 15, the green arrows depict the control messages that must collected by the peer processes of a 16 if the source of its incoming data edge d 3 is taken by DPE. If the transition condition of a 0 and a 2 evaluates to "false" then the path from a 0 to a 10 is dead. Consequently, the peer process of a 16 must be informed about the state of a 3 that will not be executed. Similarly, if the transition of a 0 and a 2 evaluates to "true", then the path that includes a 6 can be dead because of the transition of a 2 and a 6 that can evaluate to "false". Consequently, the

Structuring peer processes

If the centralized specification subjects the composition of conversational services, the relevant peer processes of that specification must deal with their partial order or exclusivity. The algorithms that we have presented in the previous sections deal with this issue. In this section, we give some concrete examples.

Example 10 (Structuring) Let's suppose that the activities a 0 and a 11 of figure 11 consist of the invocations of different operation of the same service. Consequently, they are included in the same peer process that that service will execute. With previous algorithms, the relevant process fragments can be derived. They are denoted •a 0 , •a 11 , a 11 • and a 0 •. Each derived fragment begins with an empty activity S a i that precedes •a i and ends with an empty activity F a i that succeeds a i •. When the peer process structured, the partial order of activities are taken into account. In the centralized specification, a 0 precedes a 11 . Consequently, when the process is executed with peer processes, the same order must be preserved. In order to do so, F a 0 is placed before S a 11 in the peer process. Consequently, the activities that collect messages relevant to the activity a 11 can be executed after the termination of the activities that send wiring information of a 0 . Figure 16 Let's suppose that a 0 , a 11 and additionally a 13 must be structured within the same peer process. In order to respect their partial order, S a 11 and S a 13 must succeed F a 0 . However, S a 11 and S a 13 must be concurrent as a 11 and a 13 are concurrent in the centralized specification.

In the above example, all of the activities of the peer process are executed as they are not paths that can be taken by dead paths. However, if structured activities are on paths that can be taken by DPE, their peer processes can be able to skip them. The following example describes a peer process where there are two activities that are on the paths that can be taken by DPE.

Example 11 (Structuring peer process) Let's suppose the activities a 0 , a 6 and a 12 of figure 11 consist of the invocations of different operations that belong to a same service. Activity a 6 is on a path that can be taken by DPE. Consequently, the peer process must skip it if the former is not executed. The peer process of figure 17 depicts the structure of relevant process fragments of a 0 , a 6 and a 12 .

On proper termination

he structuring mechanism that wires peer processes with each other prevents blocking reads. However, it does not guarantee the proper termination of peer processes that have unconsumed data in their asynchronous communication channels. In order to ensure the proper termination, we employ an explicit mechanism that sends termination messages to all peer processes after the termination of the final activity. In order to do so, the peer process that executes the final activity of the centralized specification sends a termination message to all peer processes to terminate current peer process instances that belongs to the same composition. Consequently, the peer processes that must terminate include a corresponding receiving activity that is concurrently placed before their final activity. Thus, whenever a termination message is received from the peer process that executes the final activity, they can remove their unconsumed data and terminate correctly. This path is executed if a6 is taken DPE This path is executed if a6 is not taken DPE . Our approach differs from these propositions mainly because of its focus on the decentralized process and because our approach does not assume the presence of sophisticated software layers on orchestrated services. Our very related work can, in some sense, be considered as process partitioning. Recently, a number of partitioning methods have been proposed for enabling decentralized execution settings. However, they are in their infancy. Baresi et al. [4] and Sadiq et al. [START_REF] Sadiq | Model driven distribution of collaborative business processes[END_REF] consider the decentralization operation from the point of view of control flow. Although, in [START_REF] Khalaf | Role-based decomposition of business processes using bpel[END_REF] Khalaf and Leymann have addressed the partitioning that compute data edges, they do not present the concrete specification of such an operation. Moreover, their partitioning does not aim to establish P2P interconnections. In [START_REF] Gowri Nanda | Decentralizing execution of composite web services[END_REF], Nanda et al. propose a partitioning mechanism for centralized BPEL specifications. However, the authors do not detail how they deal with DPE and conversational aspects. They aim to optimize the interactions of distributed processes without considering their P2P interactions. [START_REF] Atluri | A chinese wall security model for decentralized workflow systems[END_REF] presents a run-time partitioning mechanism that aims to exchange the process between its participants for P2P interconnections. However, the authors assume the presence of a partitioning mechanism implemented by process participants.

Our contribution stands between Orchestration and Choreography initiatives that govern the implementation of service oriented processes. In contrast to orchestration, choreography (championed by WS-CDL [START_REF] Kavantzas | Web Services Choreography Description Language Version 1[END_REF] which is used in conjunction with BPEL) describes the public messages exchanges and interaction rules that occur between multiple service endpoints. Choreography is more P2P in nature than orchestration. The most common use of WS-CDL is the derivation of distributed BPEL stubs from a globally agreed WS-CDL description. However, the agreement of a common choreography and the derivation of BPEL stubs are not implicitly defined. Our approach considers a centralized specification that does not require a global agreement between services and naturally, it enforces the global semantics on local implementations [START_REF] Maria Zaha | Let's dance: A language for service behavior modeling[END_REF]. To sum up, we take advantage of the process standardization efforts in another context.

Discussion

In this report, we have presented an approach that enables decentralized service orchestrations where services can establish P2P interconnections. Our approach deals with decentralization by returning to the need to derive distributed and cooperating peer processes of a centralized specification. We have described a set of formal concepts and algorithms that compute a centralized specification to derive its corresponding peer processes. We focused on sophisticated control/data dependencies and conversational aspects of decentralization that need reconciliation but have not been extensively studied in the relevant literature. Perhaps the most interesting aspect of our work is to benefit from the interchangeability issue of processes that process standardization efforts have brought forward. This in turn strongly argues that the services are capable of receiving and executing peer processes. Although our approach demonstrates how a process can be decentralized, there are many criteria that govern decentralization operation [START_REF] Yildiz | Enhancing secured service interoperability with decentralized orchestration[END_REF][25] [START_REF] Yildiz | Dynamic decentralized service orchestration[END_REF]. We are currently exploring ways to integrate these criteria to our existing contributions. Considerable work of optimization remains on the issues presented in this paper. We intent to implement a more appropriate interaction mechanism that reduces the interactions of peer processes as much as possible while it keeps P2P nature.

Figure 1 :

 1 Figure 1: Dead Path Elimination in Centralized Process Execution

Definition 5 (

 5 Postset) The postset of an activity a is denoted a•. a• = {(a j , e) ∈ A×(E c ∪E d ) s.t. source(e) = a i ∧ target(e) = a j }

Figure 4 :

 4 Figure 4: Wiring example

Figure 6 :

 6 Figure 6: Data dependency along a weak control path

Figure 7 :

 7 Figure 7: DPE example

Figure 8 :

 8 Figure 8: DPE example

Figure 9 :

 9 Figure 9: DPE example

Algorithm 1 1 : 2 : 3 : 9 : 10 :

 1123910 Wiring with postset activities Require: ai, Centralized Process Ensure: f ai• for all aj∈ai,c• do for all an ∈ A -{ b ai} s.t. (an < b ai) ∧ (aj < an) do for all a k ∈ •an,c do for all an ∈ A s.t. ∃a k ∈ •an,ws, aj < a k ∧ a k < b ai do for all a k ∈ •an,ws s.t. (aj < a k ) ∧ (a k < b ai) do 11: a OR/false j || ← a w i→n (a k (f ))

j ) 18 : end for 19 :Example 5 (

 18195 for all aj ∈ ai,st • ∪ai,wt• do Notation example) For example, when a i || ←

Figure 10 :

 10 Figure 10: Structuring of preset activities: Notation example

Figure 11 :Example 7 (

 117 Figure 11: Wiring with postset activities

Figure 12 :Figure 13 :

 1213 Figure 12: Transition of a 0 and a 1 that evaluates to "false"

ai 2 : 3 : 4 : 9 :

 2349 for all aj∈•ai,c do for all a k ∈ A s.t. ∃cc ∈ {OR-split}, c ∈ Ec, c = (a k , cc) ∧ ai < b cc} do for all aj ∈ •ai,ws do 10: for all am ∈ A s.t. ∃cc ∈ {OR-split}, c ∈ Ec, c = (am, cc) ∧ (cc < aj) ∧ (aj < b cc)} do 11:for all an ∈ A s.t. ∃cc, cc ∈ {OR-split}, c ∈ Ec, c = (an, cc) ∧ (cc < aj) ∧ (aj < b cc) ∧ (cc < cc ) ∧ (cc < aj)} do 14: j ⊕ (a r n→i (aj(t)) + a r j→i (d = aj.edge))15:

) 20 :

 20 for all aj ∈ •ai,ss do

Figure 14 :

 14 Figure 14: The messages that must be received for a 4 if it is on a path taken by DPE

Figure 16 :

 16 Figure 16: Structuring activities within their peer processes

Figure 17 :

 17 Figure 17: Structuring activities within their peer processes

  . The process which is

	d 1	a 4	a 5			d 2
	a 1				a 9
		a 7	a 8
	a 0
	a 2	d 0	a 10	a 11	a 12	d 4	a 15	a 16	a 17
		a 6		a 13	a 14
		a 3				d 5
			d 3
									INRIA

Figure 2: Motivating example: Centralized process conceived for centralized execution, includes control and data dependencies of process activities. Activities consist of the invocations of different service operations. As we consider conversation-based services, different operations of a service can be invoked with the execution of different activities. Control edges characterize precedence relationships while data edges express input/output data relationships. For example, the output of a 10 is used as an input of a 16

  They include activities that send d 3 and d 2 to s 16 after executing respectively a 3 and

			s 3	Service operation
			P s3
			a 3
	P s15				P s5
	s 15	a 15	termination message of a 15	d 3	a 5	s 5
						The activity that
			P s16			sends the output of a 5 to P s16
			a 16	d 2
			s 16

  INRIApeer process of a 2 must inform the peer process of a 16 about the state of a 3 . Thus, the peer process of a 16 can skip the activity that collects d 3 .

	d 1	a 4	a 5		d 2
	a 1			a 9
		a 7	a 8
	a 0
	a 2	d 0	a 11	a 12	d 4
		a 10			a 15	a 16	a 17
		a 6	a 13	a 14
		a 3			d 5
			d 3

Figure 15: The messges that must be received for a 16 if the source of incoming data dependencies are on paths taken by DPE

RR n°6131

is followed with the execution of an activity that receives the data sent by the peer process INRIA