The composition of compatible services is central in service orientation. Adapters resolve incompatibilities between services. Adapter synthesis generates an adapter A for two given services N1 and N2. Generally, there exist several different adapters for N1 and N2. In this paper, we suggest a framework to express preference between those adapters. Additionally, we sketch the synthesis of a cost-minimal adapter.
As a running example, we introduce two simple incompatible services, which are depicted in Fig. 1 in a notion similar to BPMN: Boxes are tasks, diamonds are splits and merges. Initialization and termination are represented by circles and bold circles, respectively. The dashed line encapsulates a service. A rounded box on the dashed line is a port, consisting of input and output message types. We further explain syntax and semantics by describing the actual models.
Service N1 has one port with the input message types ANSWER and CANCEL, and the output message types LOGIN, REQUEST, and DONE. Initially N1 sends a LOGIN message. This is modeled as a task named !L, where ! stands for sending, and L stands for LOGIN – we abbreviate the names of the message types. Then, N1 enters a loop. In each iteration, it sends an R (resembled by !R) and waits for an A or a C. If it receives a C, the loop is left. If it receives an A, it decides internally between starting another iteration, or leaving the loop. In the latter case, it sends a D to inform its environment that it is done sending requests. Upon leaving the loop, it terminates. Service N2 serves its environment by receiving a H followed by a P. It then returns a S followed by receiving a G. Initially and after receiving a G, N2 can receive a Q to terminate.
?A !D
LOGIN REQUEST ANSWER DONE CANCEL
HELLO PROBLEM SOLUTION GOODBYE
QUIT
?Q (b) N2 ?H ?P !S Obviously, N1 and N2 are incompatible. Even if one tries to map the interfaces as far as possible (i.e. L 7→ H, R 7→ P, S 7→ A, D 7→ G), the composition deadlocks: After one iteration of the loop, N2 waits for another H, and N1 waits for an A.
There exist different adapters for N1 and N2. Figure 2 depicts two adapters A1 and A2 for our running example. Adapter A1 sends the missing H in each loop iteration. Once N1 decides to be done, it quits N2. In contrast to the previously studied models, A1 executes tasks neither starting with ? nor !, e.g. E1. Such a task is internal, that is, neither sending nor receiving a message. The label E1 refers to a message transformation in Fig. 3(a). We explain this in more detail in the next section. Adapter A2 resolves the incompatibility trivially by sending a C to N1, and a Q to N2.
One might prefer one adapter over the other. For instance, A1 could be preferable because it enforces both services to enter their main part. In contrast to that, A2 simply quits both services, which does not seem very useful. However, one could also prefer A2 over A1, because executing the main part of the services requires many costly message transformations.
E1 !H !P ?S E2 E9 !A E3 ?D !Q (a) A1 ?R ?L E7 ?R E8 E5 !C E4 !Q (b) A2
LOGIN REQUEST ANSWER
DONE
CANCEL
In this section, we propose a general approach to synthesize a cost-minimal
adapter. We first explain the approach in [
We synthesize an adapter for N1 and N2 based on a given specification of elementary activities (SEA). Such an SEA contains all semantical activities an adapter may perform. An elementary activity is a rule of the form x1, . . . , xm 7→ y1, . . . , yn, where x1, . . . , xm, y1, . . . , yn are message types. For each message type xi, a message of that type is consumed, for each message type yj , a message of this type is produced. Message transformations are performed on internal buffers. That is, the adapter stores incoming and intermediate messages locally.
Continuing the running example, Fig. 3(a) shows an SEA {E1, . . . , E9}. We recognize all but one message type from the running example: Message type X is a temporary message to remember that rule E2 has been applied. That is, that at least one S has been translated to an A. Using such intermediate messages is a mechanism to cope with dependencies between rules. We identify which adapter uses which rules. Adapter A1 (Fig. 2(a)) executes E1, E2, E9, and E3. Adapter A2 (Fig. 2(b)) executes E7, E8, E5, and E4. Finally, the adapter Amin (Fig. 3(b)) executes E1, E2, E3, E9, E8, E6, and E4.
One advantage of this approach is that adapter synthesis can be reduced to
partner synthesis. Intuitively, partner synthesis [
We propose to specify costs based on the SEA, because it contains all activities which are known before synthesis. We then follow the above approach and reduce the problem to synthesize a cost-minimal adapter to the problem to synthesize a cost-minimal partner. 4
In this section, we introduce two formal constructs: Cost models and cost functions. A cost model determines how costs are represented, aggregated, and compared. A cost function specifies the costs for executing a rule of the SEA Σ. These cost may resemble monetary costs, for calling a web service, or penalties. Given a cost model and a cost function, the costs of an adapter are well-defined.
Formally, a cost model C = [D, S, ≤] consists of a set D, called domain of C, a function S : D∗ → D, called sequence aggregator function (SAF) of C, and a partial order ≤ on 2D, called set ordering relation (SOR) of C.
A cost function F : Σ → D specifies the cost of executing a single rule a ∈ Σ. We combine a cost function with a cost model to determine the costs of a sequence of rules. Let σ = a1 . . . an ∈ Σ∗. We define the costs of σ as hF , Ci(σ) := S(F (a1) . . . F (an)). Let L, L0 ⊆ Σ∗ be sets of sequences. We define hF , Ci(L) := {hF , Ci(σ) | σ ∈ L}. We define L ≤F L0 iff hF , Ci(L) ≤ hF , Ci(L0).
Let N1 and N2 be incompatible services. The costs of an adapter A w.r.t. F , C, N1, and N2 are then determined by inspecting the terminating runs of the composition of N1, N2, and A. A terminating run results in a common final state of all services. We define hF , C, N, Qi(A) := {hF , Ci(σ|Σ) | σ is a terminating run of N ⊕ A ⊕ Q}, where σ|Σ denotes the restriction of σ to alphabet Σ. For two adapters A, A0, we define A ≤F,N,Q A0 if and only if hF , C, N, Qi(A) ≤F hF , C, N, Qi(A0).
A general limitation of this approach is the fact that costs for a sequence of rule executions are built from the costs of the executions of single rules. One may desire LOGIN REQUEST ANSWER
DONE CANCEL
?L ?R E2 ?S !P !A !G !H ?D E3 !Q E9 ?R E8 E6 !C E4 !Q
HELLO PROBLEM SOLUTION GOODBYE QUIT to express dependencies, for instance, executing rule E = x1, . . . , xm 7→ y1, . . . , yn could be cheaper if a message X was received beforehand. This can be partly realized by intermediate messages. For this case, one would introduce three new rules R = X 7→ X, receivedX , R0 = receivedX 7→ , and E0 = receivedX , x1, . . . , xm 7→ receivedX , y1, . . . , yn. One would apply the appropriate lower costs to E0. An open question is to find the class of dependencies one can express in this way. For example, it is not possible to declare that the costs for executing a rule are reduced by factor two each time.
In the remainder of this section, we discuss two cost models, and apply these cost models to our running example. For that purpose, we define a cost function F based on the SEA in Fig. 3(a). Most of the rules have costs of zero. However, E1 and E1 have costs of 5, because the message content has to be translated to a different format. Rule E5 has a penalty of 30, to symbolize that we do not prefer to send a C to N1. Rule E6 has a lower penalty, because it may only be applied after at least one request has been answered. The idea of this cost model is to compute the total costs of each run, and select the supremum to compare two adapters. Total costs are determined by addition. We prefer an adapter A1 over an adapter A2 if the worst-case total costs of A1 are lower than the worst case total costs of A2. In order to enable analysis, we choose the natural numbers as domain. The advantage is an inherent monotony. We define the cost model T as the cost model with domain DT := N0, the SAF ST (a1 . . . an) := a1 + . . . + an, and SOR X ≤T Y if and only if sup(X) ≤ sup(Y ). Thereby, N0 denotes the set of natural numbers, + denotes integer addition, sup(X) ∈ N0 ∪ {∞} denotes the supremum (least upper bound) of X, and ≤ denotes the natural order on N0 ∪ {∞}.
Comparing the adapters of our running example, we find: A1 7→ {10, 20, 30, . . .}, A2 7→ {30}, Amin 7→ {10, 20}. We prefer Amin, because 20 ≤ 30 ≤ ∞. We believe that it is obvious that Amin is the cost-minimal adapter w.r.t. F, T , N1 and N2. It is impossible to adapt N1 and N2 with less costs, because N1 decides whether it sends another request, or whether it is done. 4.2
A cost model for worst case average costs The disadvantage of cost model T is that all adapers with unbounded worst case total costs are equivalent. That is, we may not distinguish between them. However, there might be services N1 and N2 which are not adaptable by a service with bounded worst case costs. In this case, we would like to be able to distinguish two adapters A1, A2 with unbounded costs. Intuitively, we compare the costs for executing an additional rule in each adapter. We evaluate the average costs of each run (instead of the total costs), and use again the supremum to compare. We prefer an adapter A1 over an adapter A2 if the worst-case average costs of A1 are lower than the worst case average costs of A2. Obviously, this cannot be done in the natural numbers anymore. Hence, we select the non-negative rational numbers as domain. We define the cost model A as the cost model with domain DA := Q0+, the SAF SA(a1 . . . an) := a1+...+an , and SOR X ≤A Y if and only if n sup(X) ≤ sup(Y ). Thereby, Q0+ denotes the set of non-negative rational numbers, + + denotes rational number addition, sup(X) ∈ Q0 ∪ {∞} denotes the supremum + (least upper bound) of X, and ≤ denotes the natural order on Q0 1∪0,{27∞0,}13.00 , . . .},
Comparing the adapters of our running example, we find: A1 7→ { 4 A2 7→ { 340 }, Amin 7→ { 140 , 250 }. We prefer A1, because 3 ≤ 4 ≤ 7.5. 5
For the cost model T , we solved the problem to synthesize a cost-minimal partner
in [
We sketch the synthesis approach. A central concept of the synthesis is the minimal budget of a service N w.r.t. a cost function F . That is, the unique costs of the cost-minimal partner. For T , the minimal budget is either a natural number, or infinite.
In a first step, we find an upper bound b for the minimal budget with the
following property: b is infinite iff the minimal budget is infinite. The upper
1 Marlene is available at http://service-technology.org/marlene [Last accessed on
201214-02]
bound b is found by examining N together with its most-permissive partner.
Intuitively, the most-permissive partner simulates each other partner of N . The
most-permissive partner is computed with the tool Wendy [
If b is finite, we find the cost-minimal partner by iteration: For a given budget k, it is possible to check whether there exists a partner with costs k. If such a partner exists, it can be synthesized. This is realized by first transforming N to a service N k , and then synthesizing a partner for N k . We find the lowest k ≤ b,
F F such that there exists a partner with costs k. This is implemented as a binary search. The resulting partner is by construction cost-minimal.
We implemented this procedure prototypically in Tara2. For other cost models, we do not have a solution yet. 6
Seguel et al. [
In this paper, we described the problem of cost-minimal adaptation. We suggested a framework to express preference between different adapters based on cost models and cost functions. We discussed two cost models: Worst-case total costs, and worst-case average costs. We sketched the synthesis procedure for worst-case total costs.
We stucture our intended future work as follows: (1) Identification and classification of further cost models, (2) solving partner and thus adapter synthesis for other cost models than T , (3) evaluating the complete approach. For (1) we 2 Tara is available at http://service-technology.org/tara [Last accessed on 2012-14-02] plan to further investigate the literature on formalisms which cope with costs in general, for instance, weighted automata. Additionally, we plan to consider results from decision theory. To tackle (2), we will start to develop an algorithm which decides whether one adapter is to be prefered over an other. Then, we extend this result to synthesis of a partner. Part (3) could be realized by a case study with our prototype on real world services.