Service adaptation allows two services to interact properly using a mediator or adapter. In service discovery one question is whether an adaptable service exists for a given service, i. e. whether a service exists which can be interacted with properly by using an adapter. We look at a setting where this question boils down to deciding distributed controllability, and we present an idea for changing an algorithm for controller synthesis which answers this question.
S1
Adapter
S2
S1
Adapter Existence of an Adaptable Service: Is there another service and an adapter, such that my service can communicate correctly with this other service using the adapter?
This question actually is not easy to answer. It appears, that we may simply apply an algorithm for service selection in order to pick S2 and an adapter. Service adaptation proposes to create, not to select a mediating service though. As it mainly works on a semantical rather than a functional level adapters are not meant to be stored and be publicly available. Thus the question above would suggest trying to create an adapter for each candidate S2.
Setting. Many newer approaches [
For this approach we may assume to have S1 and at least the transformation rules and thus the engine E given, when looking for a service S2. Checking the Existence of an Adaptable Service then asks for a service S2 for which a controller C exists, such that the composition S1 ⊕ E ⊕ C ⊕ S2 properly terminates. Contribution. We provide an algorithmic idea to abstract from C and then ask for the existence of an S2 using existing work on partner synthesis. As to the best of our knowledge the question for the Existence of an Adaptable Service has not been answered so far. The idea proposed in this paper is a first step in solving the problem.
The ultimate goal is the characterization of all adaptable services. Then, given a candidate in a repository, we could decide, whether an adapter can be computed for this candidate or not. However, this problem will remain for future work. So far, we simply want to be able to check, whether it is possible to find such a candidate, or if no such service exists as the transformation rules are not sufficient for adaptation.
In the following we first introduce service adaptation on a formal level (Sec. 2). Then we briefly discuss the problem of distributed controllability (Sec. 3)—our main question relates to this problem—before giving an idea for solving the problem in the special case of adapters (Sec. 4). Finally we give an outlook (Sec. 5) on how to extend the solution to partially solve the more general case of distributed controllability. 2
In the last couple of years many approaches [
We use previous work [
An open net additionally uses transition labels to express communication via some channel c: a transition may asynchronously send a message (!c), receive a message (?c)—thus restricting firing if c contains no message—, or it may synchronize (#c). Further we provide a set Ω of final markings, indicating in which state a service is allowed to terminate.
The approach for adapter synthesis then can be summarized as follows: let us assume to have given service models S1 and S2 (as open nets) as well as message transformation rules, which can be canonically translated into an open net E (the engine). Each transition of E is synchronously connected to a controller port, thus allowing full control about the application of transformation rules. We then use existing algorithms for controller synthesis for constructing a controller and thus an adapter, if any exists. The controller’s role is to ensure proper termination as transformation rules may not be applied arbitrarily. In the following proper termination is used synonymously to weak termination (viz. it is always possible to reach a final state).
Figure 2 shows our (technical) running example. We use the typical graphical notation for Petri nets. Additionally the dashed line shows the boundary of one open net, places indicating a proper final state are depicted using a double line. Communication labels are written inside a transition (omitting the synchronous labels used for communication in the adapter between the lower engine and the upper controller part). Service S1 (Fig. 2a) receives an initial message (?e), waits for an external choice (either ?b1 or ?b2), sends an appropriate answer (either !t or !c), and returns to its initial state. Service S2 (Fig. 2c) simply sends a message (!m) and waits for a reply (?k); or it may decide to terminate. Within the engine part of the adapter (Fig. 2b) we see the communication with S1 and S2 as well as the transformation rules (r1 to r5). In more detail the rules are: r1 : m 7→ e 1 N. B.: The whole theory could be canonically translated into state machines. However we decided to use Petri nets. !m ?k (a) S1 (b) Adapter (focus on engine) (c) S2 (rename m to e); r2 : 7→ b1 (create b1); r3 : 7→ b2 (create b2); r4 : c 7→ k (rename c to k); and r5 : t 7→ s (rename t to s). As we can see, rules canonically translate into Petri net transitions, where the channel names translate into places. Please note, that there are additional arcs between the engine and controller part that we omitted for sake of simplicity.
Composition of two open nets A and B is realized by introducing a buffer place pc for each asynchronous channel c and adding an arc (t, pc) for each transition t with label !c, an arc (pc, t) for each transition t with label ?c, and each pair of transitions with the same synchronous label #c is merged while preserving their individual presets and postsets (Figure 3 shows an example).
We now want to change the perspective in order to check the Existence of an Adaptable Service: let us assume we only know about service S1 and some transformation rules. Does any service S2 exist, such that S1 and S2 are adaptable given the transformation rules? Regarding Fig. 1a we have given services S1 and E and are looking for services S2 and C (where the latter is of minor importance). Nevertheless in our setting we are actually looking for two services that are not allowed to communicate with each other directly—as S2 and C only communicate with the engine E—but that we can match during construction.
Let us rephrase the problem a bit: given S1 ⊕ E, we are looking for a service S2, such that we can be sure, an appropriate C also exists. 3
The problem we want to solve in the adapter setting—checking for the Existence
of an Adaptable Service—relates to the problem of distributed controllability [
The described problem is known to be solvable for acyclic services [
Although checking the Existence of an Adaptable Service thus relates to a problem suspected to be undecidable, we present an idea for tackling this problem in the special case of adapters. This is possible as the engine of an adapter has a very special structure—every transitions within the engine is under control. The decisions of any controller are very determined, which helps us in predicting a controllers decisions. Thus even in case of cyclic services we can actually decide, whether an adaptable service exists.
In the next section we exploit this fact by actually foretelling some of the controllers decisions and then checking for the Existence of an Adaptable Service using existing algorithms for partner synthesis. 4
In this section we shortly sketch the idea for answering the question, whether a service S2 exists for a given service S1 and a set of transformation rules, such that S1 and S2 are adaptable with respect to the transformation rules.
First of all we have to fix an interface for S2. Otherwise it is not clear, which messages used within the transformation rules are actually meant to be sent or received—which actually is not always clear from the rules. However, in many cases the rules suggest a certain direction and we leave it to future work to find heuristics for allowing more flexibility in choosing the interface.
When trying to find S2 we have to take care of certain points: first, building a central controller (one serving both ports) can be misleading. There exists S1 and E which have a central controller, but no distributed one (e. g., when S2 would need to react on messages exchanged between E and C). An algorithm working on the central controller must be aware of this. Second, as we are 2 Personal communication with Karsten Wolf. Unpublished result. mainly interested in S2 we could abstract from the interface (i. e. remove all communication) between engine and controller. This would respect somehow the independence of S2 and controller C. However, this does not take into account the possibility for design-time coordination of S2 and C, thus failing in finding any S2 in many cases, when actually one exists.
The approach we want to follow is a mixture of both ideas: abstract from the communication between engine and controller, but use information about transitions being part of the engine to decide, whether bad states could be avoided by an yet unknown controller.
The algorithm [
Our algorithm for finding an adaptable service S2 (without generating a corresponding controller part C) can be summarized as follows: Let us have given a service S1 and an engine E representing message transformation rules. Translate the reachability graph of S1 ⊕ E into a communicating automaton. If there is a transition with a controller label—a label for communication between engine E and controller C—which results in a state, where reaching a bad state is unavoidable for any S2, then remove this transition and all states becoming unreachable. If no such further transitions exist, remove all controller labels (making corresponding transitions communicating with the controller part of an adapter internal) and run the algorithm for partner synthesis.
This way we exploit the possibility to rely on a correct decision of C in case it is necessary. As we are only removing transitions where reaching a final state cannot be enforced anymore—neither by S2 or any controller C—communication between engine and controller is not determined and a level of uncertainty remains, which S2 has to cope with (viz. S2 is still not aware of communication between E and C).
Running example: Let us consider the example in Fig. 2. The transition r3 (creating b2) should fire once for every m received, but never a second time. As we know that r3 is part of the engine, we know that a C can decide to fire r3 one time (as a final state is reachable in the example), but never a second time, when no further m was received (as a final state might not be reachable anymore in the example). Thus we remove all transitions related to the second firing of r3. We can see the (partial) result of this operation in Fig. 4. Arcs and labels related to engine transitions are gray, an unavoidable deadlock is indicated by a cross, the removal of arcs by prohibition signs. When we start partner synthesis on the artifact depicted in Fig. 4, then we get as result a service corresponding to the net initially depicted in Fig. 2c. Thus we are able to compute a witness to show that S1 is adaptable provided the given transformation rules. 5
The use of adapters extends the setting of Service-Oriented Architectures by some challenging questions. In the case of service discovery we may not only be interested a (compatible) partner service, but also a partner service usable through an adapter would serve our purposes. Thus the question arises if any adaptable service does exist. In case we regard an adapter as a union of semantical constraints and control flow we have provided an algorithmic idea to answer this question. We have omitted a proof for the correctness of this approach. Surely it highly relies on the very special structure of the engine (unique communication labeling, controller always has complete knowledge about the state of the engine, thus decisions are determined, etc.).
If we want to lift this approach to decide distributed controllability in a more general setting, certain pitfalls are ahead that do not allow to directly apply the idea on arbitrary services. Some major issues are transitions with equal communication labels, a higher degree of uncertainty, and asynchronous communication labels on both ports (asynchronous communication normally needs to be restricted due to undecidability results, what the algorithm is not yet aware of).
Nevertheless we want to refine the algorithm in a way, that if we abstract an arbitrary two-port service S from one port and find a controlling service for the second port, then only because S is distributed controllable. For the adapter setting we want to show on a formal level, that the algorithm actually decides the problem. Thus if S1 ⊕ E is distributed controllable, then the algorithm finds some S2.
Further, we would like to characterize all adaptable service. This would allow us to actually do Service Discovery more efficiently without synthesizing an adapter for each candidate service S2. We could simply match S2 against the characterization.