AperTO - Archivio Istituzionale Open Access dell'Università di Torino
Original Citation:
An Algebraic Theory for Web Service Contracts
Publisher:
Published version:
DOI:10.1007/978-3-642-38613-8_21 Terms of use:
Open Access
(Article begins on next page)
Anyone can freely access the full text of works made available as "Open Access". Works made available under a Creative Commons license can be used according to the terms and conditions of said license. Use of all other works requires consent of the right holder (author or publisher) if not exempted from copyright protection by the applicable law. Availability:
SPRINGER-VERLAG BERLIN
This is a pre print version of the following article:
An Algebraic Theory for Web Service Contracts
Cosimo Laneve1 and Luca Padovani2
1 Universit`a di Bologna – INRIA Focus Team, Italy 2
Universit`a di Torino – Dipartimento di Informatica, Italy
Abstract. We study a natural notion of compliance between clients and services in terms of their bpel (abstract) descriptions. The induced preorder shows interesting connections with the must preorder and has normal form representatives that are parallel-free finite-state activities, called contracts. The preorder also admits the notion of least service contract that is compliant with a client contract, called principal dual contract. Our framework serves as a foundation of Web service tech-nologies for connecting abstract and concrete service definitions and for service discovery.
1
Introduction
Service-oriented technologies and Web services have been proposed as a new way of distributing and organizing complex applications across the Internet. These technologies are nowadays extensively used for delivering cloud computing platforms.
A large effort in the development of Web services has been devoted to their specification, their publication, and their use. In this context, the Business Pro-cess Execution Language for Web Services (bpel for short) has emerged as the de-facto standard for implementing Web service composition and, for this rea-son, it is supported by the toolkits of the main software vendors (Oracle Process Manager, IBM WebSphere, and Microsoft BizTalk).
As regards publication, service descriptions should retain abstract (behav-ioral) definitions, which are separate from the binding to a concrete protocol or endpoint. The current standard is defined by the Web Service Description Lan-guage (wsdl) [10], which specifies the format of the exchanged messages – the schema –, the locations where the interactions are going to occur – the inter-face –, the transfer mechanism to be used (i.e. soap-rpc, or others), and basic service abstractions (one-way/asynchronous and request-response/synchronous patterns of conversations). Since these abstractions are too simple for expressing arbitrary, possibly cyclic protocols of exchanged messages between communicat-ing parties, wsdl is not adequate to verify the behavioral compliance between parties. It is also worth to notice that the attempts, such as uddi (Universal Description, Discovery and Integration) registries [5], provide limited support because registry items only include pointers to the locations of the service ab-stractions, without constraining the way these abstractions are defined or related to the actual implementations (cf. the <tModel> element). In this respect, uddi
registries are almost useless for discovering services; an operation that is per-formed manually by service users and consumers.
The publication of abstract service descriptions, called contracts in the fol-lowing, and the related ability of service searching assume the existence of a formal notion of contract equivalence and, more generally, of a formal theory for reasoning about Web services by means of their contracts. We identify three main goals of a theory of Web service contracts: (1) it should provide a for-mal language for describing Web services at a reasonable level of abstraction and for admitting static correctness verification of client/service protocol im-plementations; (2) it should provide a semantic notion of contract equivalence embodying the principle of safe Web service replacement. Indeed, the lack of a formal characterization of contracts only permits excessively demanding notions of equivalence such as nominal or structural equality; (3) it should provide tools for effectively and efficiently searching Web services in Web service repositories according to their contract.
The aim of this contribution is to provide a suitable theory of contracts for Web services by developing a semantic notion of contract equivalence. In fact, we relax the equivalence into a subcontract preorder, so that Web services exposing “larger” contracts can be safely returned as results of queries for Web services with “smaller” contracts. We will precisely define what “smaller” and “larger” mean, and we will define which safety property we wish to preserve when sub-stituting a service exposing a contract with a service exposing a larger contract. Our investigation abstracts away from the syntactical details of schemas as well as from those aspects that are oriented to the actual implementations, such as the definition of transmission protocols; all these aspects may be easily inte-grated on top of the formalism. We do not commit to a particular interpretation of the actions occurring in contracts either: they can represent different typed channels on which interaction occurs or different types of messages.
To equip contracts with a subcontract preorder, we commit to a testing ap-proach. We define client satisfaction as the ability of the client to successfully complete every interaction with the service; here “successfully” means that the client never gets stuck (this notion is purposefully asymmetric as client’s satis-faction is our main concern). The preorder arises by comparing the sets of clients satisfied by services.
The properties enjoyed by the subcontract preorder are particularly relevant in the context of Web services. Specifically, it is possible to determine, given a client exposing a certain behavior, the smallest (according to subcontract pre-oder) service contract that satisfies the client – the principal dual contract. This contract, acting like a principal type in type systems, guarantees that a query to a Web service registry is answered with the largest possible set of compatible services in the registry’s databases.
Related works. Our contracts are normal forms of τ -less ccs processes, a calculus developed by De Nicola and Hennessy in a number of contributions [13, 15, 18]. The use of formal models to describe communication protocols is not new (see for instance the exchange patterns in ssdl [20], which are based on csp and the
π-calculus), nor is it the use or ccs processes as behavioral types (see [19] and [9]). The subcontract relation . has been introduced in [17]. In [6] the authors have studied a refined version of . that is more suited for orchestrations. The works that are more closely related to ours are by Castagna et al. [8] and the ones on session types, especially [14] by Gay and Hole. The authors of [8] make the assumption that client and service can be mediated by a filter, which prevents potentially dangerous interactions by dynamically changing the interface of the service as it is seen by the client. The present work can be seen as a special case of [8] in which the filter is static and consequently is unnecessary; at the same time, in the present work we also consider divergence, which is not addressed in [8]. With respect to [14] (and systems based on session types) our contract language is much simpler and it can express more general forms of interaction. While the language defined in [14] supports first-class sessions and name passing, it is purposefully tailored so that the transitivity problems mentioned above are directly avoided at the language level. This restricts the subcontract relation in such a way that internal and external choices can never be related (hence, {a, b} : a ⊕ b {a, b} : a + b does not hold).
As regards schemas, which are currently part of bpel contracts, it is worth mentioning that they have been the subject of formal investigation by several research projects [4, 16]. This work aims at pursuing a similar objective, but moving from the description of data to the description of behaviors.
Structure of the paper. In Section 2 we introduce bpel abstract activities and their semantics. In Section 3 we define contracts and detail their relationship with bpel abstract activities. In Section 4 we address the issue of service discovery in repositories. We conclude in Section 5. Due to space limitations, proofs have been omitted; they can be found in the full paper.
2
BPEL and the abstract language
We introduce the basic notions of bpel by means of an example. The xml doc-ument in Figure 1 describes the behavior of an order service that interacts with four other partners, one of them being the customer (purchasing), the others being providers of price (invoicing service), shipment (shipping service), and manufacturing scheduling (scheduling service). The business process is made of activities, which can be either atomic or composite. In this example atomic activities are represented by invocation of operations in other partners (lines 7– 9, 15–18, 22–25), acceptance of messages from other partners, either as incoming requests (line 3) or as responses to previous invocations (lines 10–12 and 19), and sending of responses to clients (line 28). Atomic activities are composed to-gether into so-called structured activities, such as sequential composition (see the sequence fragments) and parallel composition (see the flow fragment at lines 4– 27). In a sequence fragment, all the child activities are executed in the order in which they appear, and each activity begins the execution only after the previous one has completed. In a flow fragment, all the child activities are executed in
1 <process>
2 <sequence>
3 <receive partnerLink="purchasing" operation="sendPurchaseOrder"/>
4 <flow>
5 <links> <link name="ship-to-invoice"/> <link name="ship-to-scheduling"/> </links>
6 <sequence>
7 <invoke partnerLink="shipping" operation="requestShipping">
8 <sources> <source linkName="ship-to-invoice"/> </sources>
9 </invoke>
10 <receive partnerLink="shipping" operation="sendSchedule">
11 <sources> <source linkName="ship-to-scheduling"/> </sources>
12 </receive>
13 </sequence>
14 <sequence>
15 <invoke partnerLink="invoicing" operation="initiatePriceCalculation"/>
16 <invoke partnerLink="invoicing" operation="sendShippingPrice">
17 <targets> <target linkName="ship-to-invoice"/> </targets>
18 </invoke>
19 <receive partnerLink="invoicing" operation="sendInvoice"/>
20 </sequence>
21 <sequence>
22 <invoke partnerLink="scheduling" operation="requestProductionScheduling"/>
23 <invoke partnerLink="scheduling" operation="sendShippingSchedule">
24 <targets> <target linkName="ship-to-scheduling"/> </targets>
25 </invoke>
26 </sequence>
27 </flow>
28 <reply partnerLink="purchasing" operation="sendPurchaseOrder"/>
29 </sequence>
30 </process>
Fig. 1. bpel business process for an e-commerce service.
parallel, and the whole flow activity completes as soon as all the child activities have completed. It is possible to constrain the execution of parallel activities by means of links. In the example, there is a link ship-to-invoice declared at line 5 and used in lines 8 and 17, meaning that the invocation at lines 16–18 cannot take place before the one at lines 7–9. Similarly, the link ship-to-scheduling means that the invocation at lines 23–25 cannot take place before the receive operation at lines 10–12 has completed. Intuitively, the presence of links limits the possible interleaving of the activities in a flow fragment.
Note that bpel includes other conventional constructs not shown in the ex-ample, such as conditional and iterative execution of activities.
To pursue our formal investigation, we will now present an abstract language of processes whose operators correspond to those found in bpel. Since we will focus on the interactions of bpel activities with the external environment, rather than on the actual implementation of business processes, our process language overlooks details regarding internal, unobservable evaluations. For example, the bpel activity
<if>
<condition> bool-expr </condition> activity-True
<else> activity-False </else> </if>
will be abstracted into the process activity-True ⊕ activity-False, meaning that one of the two activities will be performed and the choice will be a
conse-quence of some unspecified internal decision. A similar observation pertains to the <while> activity (see Remark 2.2).
2.1 Syntax of BPEL abstract activities
Let N be a set of names, ranged over by a, b, c, . . . , and N be a disjoint set of co-names, ranged over by a, b, c, . . . ; the term action refers to names and co-names without distinction; actions are ranged over by α, β, . . . . Let a = a. We use ϕ, ψ, . . . to range over (N ∪ N)∗ and r, s, . . . to range over finite sets of actions. Let rdef= {α | α ∈ r}. The syntax of bpel abstract activities is defined by the following grammar:
P, Q, Pi::= 0 (empty)
| a (receive)
| a (invoke)
| P
i∈Iαi; Pi (pick) | P |AQ (flow & link) | P ; Q (sequence) | L
i∈IPi (if)
| P * (while)
Each construct is called with the name of the corresponding bpel construct. The activity 0 represents the completed process, it performs no visible action. The activity a represents the act of waiting for an incoming message. Here we take the point of view that a stands for a particular operation implemented by the process. The activity a represents the act of invoking the operation a
provided by another partner. The activity P
i∈Iαi; Pi represents the act of
waiting for any of the αi operations to be performed, i belonging to a finite set
I. Whichever operation αi is performed, it first disables the remaining ones and
the continuation Pi is executed. If αi = αj and i 6= j, then the choice whether
executing Pi or Pj is implementation dependent. The process P |AQ, where A
is a set of names, represents the parallel composition (flow) of P and Q and the creation of a private set A of link names that will be used by P and Q to
synchronize; an example will be given shortly. The n-ary version QA
i∈1..nPi of
this construct may also be considered: we stick to the binary one for simplicity. The process P ; Q represents the sequential composition of P followed by Q. Again we only provide a binary operator, where the bpel one is n-ary. The
processL
i∈IPi, again with I finite, represents an internal choice performed by
the process, that results into one of the I exclusive continuations Pi. Finally, P *
represents the repetitive execution of process P so long as an internally verified condition is satisfied.
The pick activity P
i∈1..nαi; Pi and the if activity
L
i∈1..nPi will be also
written α1; P1+ · · · + αn; Pn and P1⊕ · · · ⊕ Pn, respectively. In the following we
treat (empty), (receive), and (invoke) as special cases of (pick), while at the same time keeping the formal semantics just as easy. In particular, we write 0
forP
α∈∅α ; Pαand α as an abbreviation forPα∈{α}α ; 0 (tailing 0 are always
Table 1. Legend for the operations of the bpel process in Figure 1. Name Operation a sendPurchaseOrder b requestShipping c sendSchedule d initiatePriceCalculation e sendShippingPrice f sendInvoice g requestProductionScheduling h sendShippingSchedule x ship-to-invoce y ship-to-scheduling
Example 2.1. Table 1 gives short names to the operations used in the business process shown in Figure 1. Then the whole bpel activity can be described by the term
a ;b ; (x |∅c ; y) |{x}d ; x ; e; f |{y}g ; y ; h
; a
where we use names for specifying links. Such names are restricted so that they are not visible from outside. Indeed, they are completely internal to the process
and should not be visible in the process’ contract. ♦
Remark 2.1. The bpel specification defines a number of static analysis require-ments beyond the mere syntactic correctness of processes whose purpose is to “detect any undefined semantics or invalid semantics within a process defini-tion” [2]. Several of these requirements regard the use of links. For example, it is required that no link must cross the boundary of a repeatable construct (while). It is also required that link ends must be used exactly once (hence 0 |{a}a is
invalid because a is never used), and the dependency graph determined by links must be acyclic (hence a.b |{a,b}b.a is invalid because it contains cycles). These
constraints may be implemented by restricting the arguments to the above
ab-stract activities and then using static analysis techniques.
2.2 Operational semantics of BPEL abstract activities
The operational semantics of bpel abstract activities is defined by means of a completion predicate and of a labelled transition system. Let P X, read P has completed, be the least predicate such that
0X P X QX
P |AQX
P X QX P ; QX
Let µ range over actions and the special name ε denote internal moves. The operational semantics of processes is described by the following rules plus the
symmetric of the rules for |. (action) P i∈Iαi; Pi αi −→ Pi (if) L i∈IPi ε −→ Pi (flow) P −→ Pµ 0 µ 6∈ a ∪ a P |AQ µ −→ P0 |AQ (link) P −→ Pα 0 Q−→ Qα 0 α ∈ a ∪ a P |AQ ε −→ P0| AQ0 (seq) P−→ Pµ 0 P ; Q−→ Pµ 0; Q (seq-end) P X Q−→ Qµ 0 P ; Q−→ Qµ 0 (while-end) P *−→ 0ε (while) P−→ Pµ 0 P *−→ Pµ 0 ; P * We briefly describe the rules. The processP
i∈Iαi; Pihas as many α-labelled
transitions as the number of actions in {αi | i ∈ I}. After a visible transition,
only the selected continuation is allowed to execute. The process L
i∈IPi may
internally choose to behave as one of the Pi, with i ∈ I. The process P |A Q
allows P and Q to internally evolve autonomously, or to emit messages, or to synchronize with each other on names in the set A. It completes when both P and Q have completed. The process P ; Q reduces according to the reductions of P first, and of Q when P has completed. Finally, the process P * may either complete in one step by reducing to 0, or it may execute P one more time followed by P *. The choice among the two possibilities is performed internally. Remark 2.2. According to the operational semantics, P * may execute the activ-ity P an arbitrary number of times. This is at odds with concrete bpel activities having P * as abstract counterpart. For example, the bpel activity
<while>
<condition> bool-expr </condition> activity
</while>
executes activity as long as the bool-expr condition is true. Representing such
bpel activity with activity* means overapproximating it. This abstraction is
crucial for the decidability of our theory.
We illustrate the semantics of bpel abstract activities through a couple of examples:
1. (a ⊕ b |{a,b}a ⊕ b) ; c ε
−→ (a |{a,b}a ⊕ b) ; c by (if), (flow), and (seq). By
the same rules, it is possible to have (a |{a,b} a ⊕ b) ; c −→ (a |ε {a,b} b) ; c, which cannot reduce anymore (a |{a,b}b is a deadlocked activity).
2. let Ψdef= 0 ; (0 ⊕ 0)*. Then, according to rules (seq-end), (if), and (while), Ψ−→ Ψ and Ψε −→ 0.ε
Let =⇒ be the reflexive, transitive closure ofε −→ andε =⇒ beα =⇒ε −→α =⇒; letε also P −→ (resp. Pµ =⇒) if there exists Pα 0 such that P −→ Pµ 0 (resp. P α
=⇒ P0); we let P X
µ
A relevant property of our bpel abstract calculus is that the model of every activity is always finite. This result is folklore (the argument is similar to the one for ccs* [7]).
Lemma 2.1. Let Reach(P ) = {Q | there are µ1, . . . , µn with P µ1
−→ · · · µn
−→ Q}. Then, for every activity P , the set Reach(P ) is always finite.
We introduce a number of auxiliary definitions that will be useful in Section 3. By Lemma 2.1 these notions are trivially decidable.
Definition 2.1. We introduce the following notation:
– P ↑ if there is an infinite sequence of ε-transitions P −→ε −→ · · · startingε from P . Let P ↓ if not P ↑.
– init(P )def= {α | P =⇒};α
– we say that P has ready set r, notation P ⇓ r, if P =⇒ Pε 0 and r = init(P0); – let P =⇒. Then P (α)α def=L
P=⇒ε −→Pα 0P
0. We call P (α) the continuation of
P after α.
The above definitions are almost standard, except for P (α) (that we already used in [17]). Intuitively, P (α) represents the residual behavior of P after an action α, from the point of view of the party that is interacting with P . Indeed, the party does not know which, of the possibly multiple, α-labelled branches P has taken. For example (a ; b+a ; c+b ; d)(a) = b⊕c and (a ; b+a ; c+b ; d)(b) = d.
2.3 The compliance preorder
We proceed defining a notion of equivalence between activities that is based on their observable behavior. To this aim, we introduce a special name e for denoting the successful termination of an activity (“e” stands for end). By compliance between a “client” activity T and a “service” activity P we mean that every interaction between T and P where P stops communicating with T is such that T has reached a successfully terminated state.
Definition 2.2 (Compliance). Let AP = {a | a ∈ actions(P ) ∪ actions(P )}
and e /∈ AP. The (client) activity T is compliant with the (service) activity P ,
written T a P , if P |AP T ε =⇒ P0 |AP T 0 implies: 1. if P0|AP T 0 X ε
−→, then {e} ⊆ init(T0), and
2. if P0↑, then {e} = init(T0).
We write P @∼ Q, called compliance preorder, if and only if T a P implies T a Q for every T . Let hdef= @∼ ∩ A∼.
According to the notion of compliance, if the client-service conversation ter-minates, then the client is in a successful state (it will emit an e-name). For example, a ; e + b ; e a a ⊕ b and a ; e ⊕ b ; e a a + b but a ; e ⊕ b ; e 6a a ⊕ b because of the computation a ; e ⊕ b ; e |{a,b}a ⊕ b =⇒ a ; e |{a,b}b−→ where the clientX
waits for an interaction on a in vain. Similarly, the client must reach a successful state if the conversation does not terminate but the divergence is due to the service. In this case, however, every reachable state of the client must be such that the only possible action is e. The practical justification of such a notion of compliance derives from the fact that connection-oriented communication pro-tocols (like those used for interaction with Web services) typically provide for an explicit end-of-connection signal. Consider for example the client behavior e + a ; e. Intuitively this client tries to send a request on the name a, but it can also succeed if the service rejects the request. So e + a ; e a 0 because the client can detect the fact that the service is not ready to interact on a. The same client interacting with a diverging service would have no way to distinguish a service that is taking a long time to accept the request from a service that is perpetually performing internal computations, hence e + a ; e 6a Ψ. As a matter of facts, the above notion of compliance makes Ψ the “smallest service” – the one a client can make the least number of assumptions on (this property will be fundamen-tal in the definition of principal dual contract in Section 4). That is Ψ @∼ P , for every P . As another example, we notice that a ; b + a ; c @∼ a ; (b ⊕ c) since, after interacting on a, a client of the smaller service is not aware of which state the service is in (it can be either b or c). Had we picked only one a-derivative of the smaller contract behavior, we would have failed to relate it with the a-derivative of the larger contract, since both b 6@∼ b ⊕ c and c 6@∼ b ⊕ c.
As by Definition 2.2, it is difficult to understand the general properties of the compliance preorder because of the universal quantification over all (client) activities T . For this reason, it is convenient to provide an alternative charac-terization of @∼ which turns out to be the following:
Definition 2.3. A coinductive compliance is a relation R such that P R Q and P ↓ implies
1. Q↓, and
2. Q ⇓ r implies P ⇓ s for some s ⊆ r, and
3. Q=⇒ implies Pα =⇒ and P (α) R Q(α).α
Let be the largest coinductive compliance relation.
The pre-order corresponds to the must-testing preorder [15] and is also an alternative definition of @∼:
Theorem 2.1. P @∼ Q if and only if P Q.
3
Contracts
In this section we discuss how to associate a behavioral description, called con-tract, to a bpel abstract activity. The ultimate goal is being able to reason about properties of bpel activities by means of the respective contracts.
Contracts use a set of contract names, ranged over C, C0, C1, . . . . A contract
is a tuple
(C1= σ1, . . . , Cn = σn, σ)
where Cj = σjare contract name definitions, σ is the main term, and we assume
that there is no chain of definitions of the form Cn1 = Cn2, Cn2 = Cn3, . . . ,
Cnk = Cn1. The syntax of σj and σ is given by
σ ::= C | α ; σ | σ + σ | σ ⊕ σ
where C ∈ {C1, . . . , Cn}. The contract α ; σ represents sequential composition in
the restricted form of prefixing. The operations + and ⊕ correspond to pick and if of bpel activities, respectively. These operations are assumed to be associa-tive and commutaassocia-tive; therefore we will write σ1+ · · · + σn and σ1⊕ · · · ⊕ σn
without confusion and will sometimes shorten these contracts asP
i∈1..nσi and
L
i∈1..nσi, respectively. The contract name C is used to model recursive
behav-iors such as C = a ; C. In what follows we will leave contract name definitions implicit and identify a contract (C1 = σ1, . . . , Cn = σn, σ) with its main body
σ. We will write cnames(σ) for the set {C1, . . . , Cn} and use the following
abbre-viations:
– 0def= C0, where C0= C0+ C0 represents a terminated activity;
– Ω def= CΩ, where CΩ = CΩ ⊕ CΩ represents divergence, that is a
non-terminating activity.
Note that, even if apparently simpler, the contract language is not a sublan-guage of bpel abstract activities. For example, Ω cannot be written as a term in the syntax of Section 2.1. Nevertheless, in the following, we demonstrate that contracts provide alternative descriptions (with respect to the preorder @∼) to bpel abstract activities.
The operational semantics of contracts is defined by the rules below:
α ; σ−→ σα σ ⊕ ρ−→ σε σ−→ σε 0 σ + ρ−→ σε 0+ ρ σ−→ σα 0 σ + ρ−→ σα 0 C = σ σ−→ σµ 0 C−→ σµ 0
plus the symmetric of rules + and ⊕. Note that + evaluates the branches as long as they can perform invisible actions. This rule is absent in bpel abstract activities because, there, the branches are always guarded by an action. Example 3.1. The Web service conversation language wscl [3] describes con-versations between two parties by means of an activity diagram (Figure 2). The diagram is made of interactions connected with each other by transitions. An interaction is a basic one-way or two-way communication between the client and the server. Two-way communications are just a shorthand for two sequential one-way interactions. Each interaction has a name and a list of document types that can be exchanged during its execution. A transition connects a source interaction
00 110011 00001111 in: Login out: ValidLogin out: InvalidLogin in: Query
out: Catalog in: Purchase out: Accepted out: InvalidPayment out: OutOfStock in: Logout [ValidLogin] [OutOfStock] [InvalidLogin] [InvalidPayment] [Accepted] [OutOfStock] [InvalidPayment]
Fig. 2. Contract of a simple e-commerce service as a wscl diagram.
with a destination interaction. A transition may be labeled by a document type if it is active only when a message of that specific document type was exchanged during the previous interaction.
The diagram in Figure 2 describes the conversation of a service requiring clients to login before they can issue a query. After the query, the service returns a catalog. From this point on, the client can decide whether to purchase an item from the catalog or to logout and leave. In case of purchase, the service may either report that the purchase is successful, or that the item is out-of-stock, or that the client’s payment is refused. By interpreting names as message types, this e-commerce service can be described by the tuple:
( C1= Login ; (InvalidLogin ; C1⊕ ValidLogin ; C2) ,
C2= Query ; Catalog ; (C2+ C3+ C4) , C3= Purchase ; ( Accepted ⊕ InvalidPayment ; (C3+ C4) ⊕ OutOfStock ; (C2+ C4) ) , C4= Logout , C1 )
There is a strict correspondence between unlabeled (respectively, labeled) transitions in Figure 2 and external (respectively, internal) choices in the con-tract. Recursion is used for expressing iteration (the cycles in the figure) so that
the client is given another chance whenever an action fails for some reason. ♦
We can relate bpel abstract activities and contracts by means of the corre-sponding transition systems. To this aim, let X and Y range over bpel abstract activities and contracts. Then, X and Y interact according to the rules
X−→ Xε 0 X k Y−→ Xε 0k Y Y−→ Yε 0 X k Y−→ X k Yε 0 X−→ Xα 0 Y α −→ Y0 X k Y−→ Xε 0k Y0
It is possible to extend the definition of compliance to contracts and, by Defi-nition 2.2, obtain a relation that allows us to compare activities and contracts without distinction, and similarly for . To be precise, the relation X @∼ Y is smaller (in principle) than the relation @∼ given in Definition 2.2 because, as we have said, the contract language is not a sublanguage of that of activities and, therefore, the set of tests that can be used for comparing X and Y is larger. Nonetheless, the process language used in [12] includes both bpel abstract
safely use the same symbol @∼ for both languages. This is a key point in our argument, which will allow us to define, for every activity P , a contract σP such
that P h σP. In particular, let CP be the set of contract name definitions defined
as follows CP = ( Ω if P ↑ L P ⇓r P α∈rα ; CP (α) otherwise
A relevant property of CP is an immediate consequence of Lemma 2.1.
Lemma 3.1. For every P , the set cnames(CP) is finite.
The construction of the contract CP with respect to a bpel abstract activity
is both correct and complete with respect to compliance:
Theorem 3.1. P h CP.
4
Service discovery and dual contracts
We now turn our attention to the problem of querying a database of Web service
contracts. To this aim, the relation @∼ (and the must-testing) turns out to be
too strong (see below). Following [17], we switch to more informative service contracts than what described in Section 3. In particular, we consider pairs i : σ, where i is the interface, i.e. the set of actions performed by the service, and σ is as in Section 3 (it is intended that the names occurring in σ are included into i). It is reasonable to think that a similar extension applies to client contracts: clients, which are defined by bpel activities as well, are abstracted by terms in the language of Section 2 and, in turn, their behavior is defined by a term in the contract language, plus the interface.
Definition 4.1 (Subcontract relation). Let i : σ . j : τ if i ⊆ j and, for every ρ such that actions(ρ) \ {e} ⊆ i and ρ a σ implies ρ a τ . Let ≈ be . ∩ &.
Let us comment on the differences between i : σ . j : τ and σ @∼ τ . We notice that i : σ . j : τ only if i ⊆ j. This apparently natural prerequisite has sub-stantial consequences on the properties of . because it ultimately enables width and depth extensions, which are not possible in the @∼ preorder. For instance, we have {a} : a . {a, b} : a + b whilst a 6@∼ a + b (width extension). Similarly we have {a} : a . {a, b} : a;b whilst a 6@∼ a ; b (depth extension). These extensions are desirable when searching for services, since every service offering more methods than required is a reasonable result of a query. The precise relationship between . and @∼ is expressed by the following statement.
Proposition 4.1. i : σ ≈ j : τ if and only if σ h τ and i = j.
The basic problem for querying Web service repositories is that, given a client k : ρ, one wishes to find all the service contracts i : σ such that actions(ρ)\{e} ⊆ i and ρ a σ. We attack this problem in two steps: first of all, we compute one
particular service contract k \ {e} : Dk
ρ such that ρ a Dkρ; second, we take all
the services in the registry whose contract is larger than this one. In order to maximize the number of service contracts returned as answer to the query, the dual of a (client) contract k : ρ should be a contract k \ {e} : Dk
ρ such that it is
the smallest service contract that satisfies the client contract k : ρ. We call such contract the principal dual contract of k : ρ.
In defining the principal dual contract, it is convenient to restrict the defi-nition to those client’s behaviors ρ that never lead to 0 without emitting e. For example, the behavior a ; e + b describes a client that succeeds if the service pro-poses a, but that fails if the service propro-poses b. As far as querying is concerned, such behavior is completely equivalent to a ; e. As another example, the degen-erate client behavior 0 is such that no service will ever satisfy it. In general, if a client is unable to handle a particular action, like b in the first example, it should simply omit that action from its behavior. We say that a (client) contract k : ρ is canonical if, whenever ρ=⇒ ρϕ 0 is maximal, then ϕ = ϕ0e and e /∈ actions(ϕ0).
For example {a, e} : a ; e, {a} : C, where C = a ; C, and ∅ : Ω are canonical; {a, b, e} : a ; e + b and {a} : C0, where C0= a ⊕ C0, are not canonical.
Observe that Lemma 2.1 also applies to contracts. Therefore it is possible to extend the notions in Definition 2.1, by replacing activities with contracts. Definition 4.2 (Dual contract). Let k : ρ be a canonical contract. The dual of k : ρ is k \ {e} : Dk
ρ where Dkρ is the contract name defined as follows:
Dk ρ def = Ω if init(ρ) = {e} P ρ ⇓ r r\{e} 6= ∅ 0 ⊕ |{z} if e ∈ r L α∈r\{e}α ; Dkρ(α)
+ OTHk\init(ρ) otherwise
where OTHs def = 0 ⊕L α∈sα ; Ω | {z } if s 6= ∅
Few comments about Dk
ρ, when init(ρ) 6= {e}, follow. In this case, the behavior
ρ may autonomously transit to different states, each one offering a particular ready set. Thus the dual behavior leaves the choice to the client: this is the reason for the external choice in the second line. Once the state has been chosen, the client offers to the service a spectrum of possible actions: this is the reason
for the internal choice underneath the sumP.
The contract OTHk\init(ρ)covers all the cases of actions that are allowed by the interface and that are not offered by the client. The point is that the dual opera-tor must compute the principal (read, the smallest) service contract that satisfies the client, and the smallest convergent behavior with respect to a nonempty (fi-nite) interface s is 0 ⊕L
α∈sα ; Ω. The 0 summand accounts for the possibility
that none of the actions in k \ init(ρ) is present. The external choice “+” dis-tributes the proper dual contract over the internal choice of all the actions in k \ init(ρ). For example, D{a,a,e}a;e = a ; Ω + (0 ⊕ a ; Ω). The dual of a divergent
(canonical) client {a} : C, where C = a;e⊕C, is also well defined: D{a,e}C00 = a ; Ω.
We finally observe that the definition also accounts for duals of nonterminating clients, such as {a} : C0, where C0= a ; C0. In this case, D{a}
C0 = a ; D
{a} C0 .
Similarly to the definition of contract names CP, it is possible to prove that
Dk
ρ is well defined.
Lemma 4.1. For every k : ρ, the set cnames(Dk
ρ) is finite.
The property that k \ {e} : Dk
ρ is the least dual contract of k : ρ follows.
Theorem 4.1. Let k : ρ be a canonical contract. Then: 1. ρ a Dk
ρ;
2. if k \ {e} ⊆ s and ρ a σ, then k \ {e} : Dk
ρ . s : σ.
A final remark is about the computational complexity of the discovery al-gorithm. Determining . is EXPTIME-complete in the size of the contracts [1], which has to be multiplied by the number of .-checks (to find a compliant service in the repository) to obtain the overall cost.
5
Conclusions
In this contribution we have studied a formal theory of Web service abstract (be-havioral) definitions as normal forms of a natural semantics for bpel activities. Our abstract definitions may be effectively used in any query-based system for service discovery because they support a notion of principal dual contract. This operation is currently done in an ad hoc fashion using search engines or similar technologies.
Several future research directions stem from this work. On the technical side, a limit of our technique is that bpel activities are “static”, i.e. they cannot create other services on the fly. This constraint implies the finiteness of models and, for this reason, it is possible to effectively associate an abstract description to activities. However, this impacts on scalability, in particular when services adapt to peaks of requests by creating additional services. It is well-known that such an additional feature makes models to be infinite states and requires an approximate inferential process to extract abstract descriptions from activities. Said otherwise, extending our technique to full ccs or π-calculus amounts to defining abstract finite models such that Theorem 3.1 does not hold anymore. For this reason, under- and over-estimations for services and clients, respectively, must be provided.
Another interesting technical issue concerns the extension of our study to other semantics for bpel activities, such as the preorder in [6], or even to weak bisimulation (which has a polynomial computational cost). Perhaps one may use axiomatizations of these equivalences for determining the class of contracts. However it is not clear whether they admit a principal dual contract or not.
It is also interesting to prototyping our theory and experimenting it on some existing repository, such as http://www.service-repository.com/. To this aim we might use tools that have been already developed for the must test-ing, such as the concurrency workbench [11].
References
1. L. Aceto, A. Ingolfsdottir, and J. Srba. The algoritmics of bisimilarity. In D. San-giorgi and J. Rutten, editors, Advanced Topics in Bisimulation and Coinduction, volume 52 of Cambridge Tracts in Theoretical Computer Science, chapter 3, pages 100–172. Cambridge University Press, 2011.
2. A. Alves et al. Web Services Business Process Execution Language Version 2.0, Jan. 2007. http://docs.oasis-open.org/wsbpel/2.0/CS01/wsbpel-v2.0-CS01. html.
3. A. Banerji, C. Bartolini, D. Beringer, V. Chopella, et al. Web Services Conversation Language ( wscl) 1.0, Mar. 2002. http://www.w3.org/TR/2002/ NOTE-wscl10-20020314.
4. V. Benzaken, G. Castagna, and A. Frisch. CDuce: an XML-centric general-purpose language. SIGPLAN Notices, 38(9):51–63, 2003.
5. D. Beringer, H. Kuno, and M. Lemon. Using wscl in a uddi Registry 1.0, 2001. uddi Working Draft Best Practices Document, http://xml.coverpages. org/HP-UDDI-wscl-5-16-01.pdf.
6. M. Bravetti and G. Zavattaro. A theory of contracts for strong service compliance. Mathematical Structures in Computer Science, 19:601–638, 5 2009.
7. N. Busi, M. Gabbrielli, and G. Zavattaro. On the expressive power of recursion, replication and iteration in process calculi. Mathematical Structures in Computer Science, 19(6):1191–1222, 2009.
8. G. Castagna, N. Gesbert, and L. Padovani. A Theory of Contracts for Web Ser-vices. ACM Transactions on Programming Languages and Systems, 31(5), 2009. 9. S. Chaki, S. K. Rajamani, and J. Rehof. Types as models: model checking
message-passing programs. SIGPLAN Not., 37(1):45–57, 2002.
10. E. Christensen, F. Curbera, G. Meredith, and S. Weerawarana. Web Ser-vices Description Language ( wsdl) 1.1, 2001. http://www.w3.org/TR/2001/ NOTE-wsdl-20010315.
11. R. Cleaveland, J. Parrow, and B. Steffen. The concurrency workbench: a semantics-based tool for the verification of concurrent systems. ACM Trans. Program. Lang. Syst., 15(1):36–72, 1993.
12. R. De Nicola and M. Hennessy. Testing equivalences for processes. Theor. Comput. Sci, 34:83–133, 1984.
13. R. De Nicola and M. Hennessy. CCS without τ ’s. In Proceedings of TAP-SOFT’87/CAAP’87, LNCS 249, pages 138–152. Springer, 1987.
14. S. Gay and M. Hole. Subtyping for session types in the π-calculus. Acta Informat-ica, 42(2-3):191–225, 2005.
15. M. Hennessy. Algebraic Theory of Processes. Foundation of Computing. MIT Press, 1988.
16. H. Hosoya and B. C. Pierce. XDuce: A statically typed XML processing language. ACM Trans. Internet Techn., 3(2):117–148, 2003.
17. C. Laneve and L. Padovani. The must preorder revisited – an algebraic theory for web services contracts. In CONCUR’07, LNCS 4703, pages 212–225. Springer, 2007.
18. R. Milner. A Calculus of Communicating Systems. Springer, 1982.
19. H. R. Nielson and F. Nielson. Higher-order concurrent programs with finite com-munication topology (extended abstract). In Proceedings of POPL’94, pages 84–97. ACM Press, 1994.
20. S. Parastatidis and J. Webber. MEP SSDL Protocol Framework, Apr. 2005. http: //ssdl.org.
