=Paper=
{{Paper
|id=None
|storemode=property
|title=Cost-minimal Adapters for Services
|pdfUrl=https://ceur-ws.org/Vol-847/paper2.pdf
|volume=Vol-847
|dblpUrl=https://dblp.org/rec/conf/zeus/Surmeli12
}}
==Cost-minimal Adapters for Services==
https://ceur-ws.org/Vol-847/paper2.pdf
Cost-minimal adapters for services
Jan Sürmeli
Humboldt-Universität zu Berlin, Institut für Informatik,
Unter den Linden 6, 10099 Berlin
suermeli@informatik.hu-berlin.de
Abstract 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.
1 Introduction
We understand a service [6] as a component with an inner process and an interface
for message exchange with other services. The actions of the inner process may be
linked with the interface, declaring which actions receive and send which type of
messages. A central concept of service orientation is the composition of services.
Clearly, it is only feasible to compose compatible services. There exist four core
aspects [5]: Syntactical, behavioral, semantical, and non-functional. In this paper,
we concentrate on weak termination, a behavioral compatibility notion, similar to
soundness [10] in business processes. A set of services is compatible w.r.t. weak
termination, iff the composition of its elements is free of deadlocks and livelocks.
An adapter [12] solves the problem that two services N1 and N2 are incompatible
by mediating between them. An adapter A is a service, such that the set N1 , N2 ,
and A of services is compatible. The idea of adapter synthesis is to automatically
generate an adapter for two services. Generally, there are different adapters
for two services N1 and N2 . In this paper, we propose a framework to express
preference between such adapters by means of cost models and cost functions.
We discuss two cost models. For one cost model, we sketch the synthesis of a
cost-minimal adapter.
2 Running example
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.
!L
!R
?H
?A LOGIN HELLO
?Q ?P
REQUEST PROBLEM
?C
ANSWER SOLUTION
!S
!D DONE GOODBYE
CANCEL QUIT
?G
(a) N1 (b) N2
Figure 1: Running example: Two incompatible services N1 and N2
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.
?L
?R
E1
!H
!P
?S ?R
?L
E2
E7
E9
?R
!A
E8
!G
E5
LOGIN HELLO LOGIN !C HELLO
E3
REQUEST PROBLEM REQUEST PROBLEM
ANSWER ?D SOLUTION ANSWER E4 SOLUTION
DONE GOODBYE DONE GOODBYE
!Q QUIT !Q QUIT
CANCEL CANCEL
(a) A1 (b) A2
Figure 2: Running example: Two adapters A1 and A2
3 General synthesis approach
In this section, we propose a general approach to synthesize a cost-minimal
adapter. We first explain the approach in [2] to synthesize an arbitrary adapter.
Second, we explain how to extend this approach such that it yields a cost-minimal
adapter.
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 [11] solves the problem to find
a compatible service N2 for a given service N1 , called partner of N1 . First, we
create an engine E from the SEA. The engine has three ports, one for each N1
and N2 , and one for a control service. We compose N1 , E, and N2 . We synthesize
a control service C. The composition of E and C serves as an adapter for N1 and
N2 . We shortly discuss the limitations of this approach. It is possible to adapt
more than just two services at once, but only by a central adapter. Additionally,
this approach is adapts single instances of each service. If one desires to adapt n
instances of one service, it is required to treat them each as a different service,
instead. This is obviously infeasible if the number of instances is variable and
not known beforehand.
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 Cost models and cost functions
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 com-
mon 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
?L ?R E1
E2 ?S !P !H
!A !G
Rule name Rule body Costs
?D ?R
E1 L, R 7→ H, P, L 5
E2 S 7→ A, G, X 5 E8
E3
E3 D 7→ Q 0 E6
E4 7→ Q 0 LOGIN
!C
HELLO
E5 7→ C 30 REQUEST !Q PROBLEM
ANSWER E4 SOLUTION
E6 X 7→ C 10
DONE GOODBYE
E7 L 7→ 0 E9 !Q
CANCEL QUIT
E8 R 7→ 0
E9 X 7→ 0
(a) Cost function F (b) Cost-minimal adapter Amin
Figure 3: A cost function F, and a cost-minimal adapter Amin w.r.t. cost function
F, cost model T , and services N1 and N2
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 real-
ized by intermediate messages. For this case, one would introduce three new rules
R = X 7→ X, received X , R0 = received X 7→ , and E 0 = received X , x1 , . . . , xm 7→
received X , y1 , . . . , yn . One would apply the appropriate lower costs to E 0 . 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.
4.1 A cost model for worst case total costs
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 := Q+ 0 , the SAF SA (a1 . . . an ) :=
a1 +...+an
n , and SOR X ≤A Y if and only if
+
sup(X) ≤ sup(Y ). Thereby, Q0 denotes the set of non-negative rational numbers,
+ denotes rational number addition, sup(X) ∈ Q+ 0 ∪ {∞} denotes the supremum
(least upper bound) of X, and ≤ denotes the natural order on Q+ 0 ∪ {∞}.
Comparing the adapters of our running example, we find: A1 7→ { 10 20 30
4 , 7 , 10 , . . .},
30 10 20
A2 7→ { 4 }, Amin 7→ { 4 , 5 }. We prefer A1 , because 3 ≤ 4 ≤ 7.5.
5 Synthesis of cost-minimal adapters
For the cost model T , we solved the problem to synthesize a cost-minimal partner
in [9]. We use the same mechanism to synthesize a cost-minimal adapter: Two
services N1 , N2 , an engine E, and a cost fumction F serve as input. The engine
E may be computed from an SEA by the tool Marlene1 . We first compose N1 ,
N2 , and E to the service N = N1 ⊕ E ⊕ N2 . Then, we synthesize a cost-minimal
partner for N w.r.t. F.
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 2012-
14-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 [3]. If b is infinite,
every partner of N is cost-minimal.
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 NFk , and then synthesizing a partner for NFk . We find the lowest k ≤ b,
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 Related work
Seguel et al. [8] study the problem to create minimal adapters to resolve deadlock
between services. Thereby, minimality is defined w.r.t. to the number of messages
considered. The resulting adapter resolves deadlocks and is minimal w.r.t. mes-
sages. We study the more general criterion of weak termination. We showed that
the minimal adapter is not necessarily cost-minimal. We reduced the synthesis
of a cost-minimal adapter to the synthesis of a cost-minimal partner. Zeng et
al. [13] use integer programming to find an optimal composite service. That is,
an optimal composition of atomic tasks each implemented by a web service. The
services do not communicate based on its state, whereas we consider stateful
services. De Paoli et al. [4] propose a similar approach for WS-BPEL [1] processes.
Both approaches work on well-structured services, whereas we support arbitrary
services. The CLAM framework, introduced by Zengin et al. [14], combines sev-
eral adaptation approaches of different layers in one tool to cope with different
concerns. It remains open how our approach fits into such a framework. In [9],
we presented our results utilizing the partner synthesis by Wolf [11] as a basis.
Instead, one could build our approach on top on other synthesis approaches, for
instance [7].
7 Conclusion
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.
References
1. Alves, A., et al.: Web Services Business Process Execution Language Version 2.0.
OASIS Standard, 11 April 2007, OASIS (Apr 2007)
2. Gierds, C., Mooij, A.J., Wolf, K.: Reducing adapter synthesis to controller synthesis.
IEEE Transactions on Services Computing 99(PrePrints) (2010)
3. Lohmann, N., Weinberg, D.: Wendy: A tool to synthesize partners for services. In:
PETRI NETS 2010. pp. 297–307. LNCS 6128, Springer (2010), tool available at
http://service-technology.org/wendy [Last accessed on 2012-14-02].
4. Paoli, F.D., Lulli, G., Maurino, A.: Design of quality-based composite web services.
In: ICSOC. pp. 153–164 (2006)
5. Papazoglou, M.: What’s in a service? In: Oquendo, F. (ed.) Software Architec-
ture, Lecture Notes in Computer Science, vol. 4758, pp. 11–28. Springer Berlin /
Heidelberg (2007)
6. Papazoglou, M.P.: Web Services: Principles and Technology. Pearson - Prentice
Hall, Essex (Jul 2007)
7. Pistore, M., Traverso, P., Bertoli, P., Marconi, A.: Automated synthesis of composite
bpel4ws web services. In: Proceedings of the IEEE International Conference on
Web Services. pp. 293–301. ICWS ’05, IEEE Computer Society, Washington, DC,
USA (2005)
8. Seguel, R., Eshuis, R., Grefen, P.: Constructing minimal protocol adaptors for
service composition. In: Proceedings of the 4th Workshop on Emerging Web Services
Technology. pp. 29–38. WEWST ’09, ACM, New York, NY, USA (2009)
9. Sürmeli, J.: Synthesizing cost-minimal partners for services. Informatik-Berichte 239,
Humboldt-Universität zu Berlin (2012), http://u.hu-berlin.de/suermeli-techreport,
[Last accessed on 2012-14-02], in publication queue
10. Van Der Aalst, W.M.P.: The application of petri nets to workflow management.
The Journal of Circuits Systems and Computers 8(1), 21–66 (1998)
11. Wolf, K.: Does my service have partners? LNCS ToPNoC 5460(II), 152–171 (Mar
2009), special Issue on Concurrency in Process-Aware Information Systems
12. Yellin, D.M., Strom, R.E.: Protocol specifications and component adaptors. ACM
Trans. Program. Lang. Syst. 19, 292–333 (March 1997)
13. Zeng, L., Benatallah, B., Ngu, A.H.H., Dumas, M., Kalagnanam, J., Chang, H.:
QoS-aware middleware for web services composition. IEEE Trans. Software Eng.
30(5), 311–327 (2004)
14. Zengin, A., Marconi, A., Pistore, M.: Clam: cross-layer adaptation manager for
service-based applications. In: Proceedings of the International Workshop on Quality
Assurance for Service-Based Applications. pp. 21–27. QASBA ’11, ACM, New York,
NY, USA (2011)