In a network of services, external and internal decisions, asynchronous message exchange, and concurrency induce complex interaction protocols. In this paper we introduce the notion of a message pro le of a service that is modeled as a special kind of Petri net. The message pro le is obtained solely from properties of the given net without requiring knowledge of interacting nets. It provides insight into the interactional behavior of the service. The information may then be used to enhance existing service analysis techniques as well as to verify the service model on a message basis.
The central part of the evolving paradigm of Service-Oriented Computing (SOC)
are services. A service represents a self-contained software unit that o ers an
encapsulated functionality over a well-de ned interface. The promising goal of a
SOC architecture is to ensure for each participating service to be loosely coupled
with another service with little e ort [
In general, a service is not designed to be used stand-alone. It is the stateful
interaction of di erent services that adds signi cant value to SOC. Therefore,
with respect to SOC, we are interested in whether every service instance will
eventually terminate in a well-de ned state with no useless (dead) activities
being pending. This idea has already been formalized as usability in [
In a network of two or more services, external and internal decisions,
asynchronous communication, and concurrency induce complex interaction protocols.
In this paper, we introduce techniques that can be used to create a message
prole of a given service S. This pro le may then serve as a guide for a controller
C with respect to which messages may be sent to S as well as how often S
accepts a particular message. The message pro le is gained from analyzing the
open net model of S. Thus, knowledge of C is not required. With the help of the
behavioral properties stored in the message pro le, we are able to characterize
possible controllers. So, we can exclude certain controllers before-hand which
enhances established methods such as partner synthesis [
This paper is structured as follows. First, we brie y introduce open nets and controllability notions in Sect. 2. In Sect. 3, we present techniques to build up the message pro le and show how it can be obtained by analysis of an open net. Finally, we conclude our results in Sect. 4. 2
We model services with open nets [
Figure 1 depicts our example open net N1. The net has got ve input places, namely a, b, c, d, e and one output place F. The initial marking of N1 is [p0] (depicted as a black token on place p0) and the set of nal markings is f[p2]; [p7]g. We can easily see that from [p0] N1 is not able to reach a di erent marking unless there is an additional token either on input place a, b or e. A token on an input/ output place represents a message. The open net N1 is able to send a message to the output place and to receive messages from its input places. Therefore, we are able to model the interaction between di erent open nets and thus have a formal notion for modeling the interaction of services.
The interaction of two di erent open nets N and C is expressed by their composition N C which is obtained by merging every input place of one open net with the equally labeled output place of the other net (if that one is present).
Intuitively, controllability of an open net N means that N can properly interact with some other net. So, N is controllable if there exists an open net C, such that the composed open net N C ful lls certain properties. Throughout a b t9 t2 p1 p2
p6
t1
p7
p8
t10
this paper we will call C a controller of N . We distinguish between DF-, WT-,
and RI-controllers based on the following notions [
Deadlock-Freedom (DF) states that all deadlocks of the composition N
C are nal states of N C and Weak-Termination (WT) (equal to
LivelockFreedom) speci es that from every marking of N C a nal marking of N C
is reachable. The property of open nets called responsiveness [
Controllability is only decidable for those open nets whose reachability graph
of the inner net is nite [
In this section, we introduce techniques that analyze the net N in order to create a message pro le of N . All methods avoid state space exploration and do not require knowledge of a controller C of N .
In the message pro le we store di erent kinds of information { how often a speci c message can be received, dependencies between messages, and which messages are not to be sent to N by a controller.
Intuitively, there are two requirements for an arbitrary service S to receive a message x: (1) S is in a state in which it accepts x, (2) a message x has been sent by controller C already. These requirements can easily be mapped to an open net N . Thus, (1) a receiving transition for x is enabled in the inner of N and (2) a token is available on the corresponding input place.
When analyzing a receiving transition t in the inner of N one less precondition for t to be enabled has to hold { the edge to its corresponding input place has been removed. Thus ring t does not depend on the number of tokens on that input place any more. So, we conclude that t can not re more frequently in N C than in the inner of N . Knowing how many times a receiving transition res in the inner of N can thus lead to insights regarding the receiving behavior of N in N C. A ring limit for a transition t is a natural number n such that there exists no path in the reachability graph with t occurring more than n times.
There exist methods to compute the ring limit of a transition in a Petri net that avoid state space exploration. Currently, we are looking for an approach that ts best w.r.t. to the open net models of real processes. In this paper, usage of the term ring limit will refer to some ring limit determined by an arbitrary method. In the inner of our example open net N1 (Fig. 1) 1 is a ring limit for ft0,t1,t2,t3,t9,t10g and 1 for transitions ft4,t5,t6,t7g.
We can use the ring limit for receiving transitions in the inner of the net as a basis and as an additional constraint for the creation of the message pro le without requiring any knowledge about C. 3.1
The idea behind the receiving limit n of a message x is to determine how often x can be received by a service N at most, i.e. how often a receiving transition for x res in N C. As we aim at being as general and controller-independent as possible, we make use of the ring limit for receiving transitions in the inner of N .
We calculate the receiving limit of message a of the example net N1 (Fig. 1). The only receiving transition for message a is t0. The ring limit for t0 is 1. Obviously, there is no guarantee that N1 will actually receive a, but it is safe to say that N1 will receive a only up to once. We set the receiving limit for a to 1.
Let us take a look at transitions t4 and t6 with t4 = t6 = fp3g. Due to the cycle, the ring limits for both t4 and t6 are 1. Thus, we cannot determine a nite number for the receiving limit of message d. So, we set it to 1.
In N1 there exists exactly one receiving transition for each input place. Generally, for a message x, we set the receiving limit to the sum of the ring limits of all receiving transitions of x. If there exists no receiving transition for x, the receiving limit is 0 { N does not accept x in any marking. If we set the receiving limit for x to 1, there are two possible reasons { (1) There exists no bound for N receiving x. Or, (2) we can not narrow down a nite number for such a bound. Either way, a receiving limit of 1 does not allow further conclusions. Finding a nite receiving limit n for a message x proves to be very useful. Although n might not be precise, as there is no guarantee that x will be received exactly n times, it is always safe to say that sending x more than n times leads to x being ignored. Therefore, we can conclude that every RI-controller respects the receiving limit of each message. Thus, we include it in the message pro le. Summarizing, the receiving limits of the example net N1 are a:1,b:1,c:1,d:1,e:1. 3.2
So far, the message pro le consists of a static number { the receiving limit for each input message, only. In an open net N , however, there might exist dependencies between messages that in uence the actual acceptance of them. From the structure of N we are able to extract con icting receiving transitions. The set of external one-time decisions contains all messages that these transitions receive, fx; y; zg. Basically, a controller C in uences the further course of N by sending a message x, for instance. Because fx; y; zg are in con ict, messages fy; zg will now be ignored by N . We include such a set of messages into the message pro le.
We will take a look at the open net N1 of Fig. 1 again. Examining the transitions t0, t3 and t8 in the inner of N1, we can easily see that there exists a con ict between them: t0 = t3 = t8. The decision between t0, t3 and t8 is non-deterministic in the inner of N1. But, considering the interface, the choice is made by the controller { by sending one of the messages fa; c; eg. Assume message a is received by N1. Then, no marking is reachable where one of ft0; t3; t8g is enabled again. Thus, sending message c or e would result in N1 ignoring that message.
In general, we construct such a set of messages M of an open net N as follows. We start by nding a set of receiving transitions that are in con ict with each other in the inner of N , set D. Then, we remove all transitions with a ring limit of 0 from D, set D0. From the receiving transitions in D0 we extract the corresponding messages, set M . Set M does not necessarily re ect a global situation. Hence, we check whether the receiving limit of every message m 2 M is 1. This way we ensure that there exists no receiving transition t 2 T n D for m. If that condition does not hold for a message, we remove it from M . We repeat that process until the condition holds for each message of M . The resulting set is now globally valid. So, sending more than one message from M always leads to N ignoring at least one message. Therefore, no RI-Controller sends more than one message from M which we include in the message pro le. The set of con icting messages fa; c; eg forms an external one-time decision of N1. 3.3
Internal decisions describe dependencies between receiving transitions and internal or sending transitions. They potentially induce that messages cannot be received. Based on the receiving limit we can decide if such a con ict leads to ignored messages or not.
We look at t1 and the internal transition t2 in N1 (Fig. 1). In the inner of N1, we nd t1 = t2 = fp1g. Suppose marking m with m(p1) = m(b) = 1. The decision between ring t1 or t2 is non-deterministic. Thus, we call t1 blocked by an internal transition. The ring limits are t1:1,t2:1. Once t 2 ft1; t2g res, no marking m0 is reachable such that any t0 2 ft1; t2g is enabled. Hence, N1 decides non-deterministically between ignoring and receiving b .
For transitions t4 and t6 a similar pattern holds in the inner of N1, t4 = t6. The di erence is, that whenever one of ft4; t6g res, a marking will be reached in which both transitions are enabled again. Assume now a message d is sent to N1 { even if t6 is red consecutively, d can still be received in any reachable marking.
More generally, a receiving transition t is blocked by an internal or sending transition t0 if t0 t holds in the inner of N . We call a a message x blocked by an internal decision if (1) we nd a nite receiving limit for x and (2) each receiving transition for x is either blocked or has a ring limit of 0. No RIcontroller sends x. DF-controllers might send x, but then the composition will always contain a livelock. We include an according set of messages in the message pro le. For N1 only message b is blocked by an internal decision, since condition (1) does not hold for message d. 3.4
De cient modeling, modi cation of an existing service or deliberate design of error conditions can lead to a structure, where the postset of an internal place (neither an input nor an output place) of the underlying open net N is either empty or consists of transitions with a ring limit of 0 in the inner of N . If such a place is not marked in any nal marking, ring a transition in its preset traps N in a state from which no nal state is reachable. We show under which circumstances messages can be tagged as trap messages in the message pro le.
Examining place p8 in the example open net N1 (Fig. 1), we notice that from any marking m with m(p8) > 0 there will be no marking m0 reachable with m0(p8) = 0. Additionally, mf (p8) = 0 for each nal marking mf . Because of p8 = ft10g, transition t10 should never re. We call m a trap marking, p8 a trap place and t10 a trap transition. We propagate this property. Because t10 = fp6g, we conclude that a token on p6 induces ring of t10 and thus to trapping the net. Thus, p6 is a trap place and all transitions of p6 (= ft8g) are trap transitions. So, transition t8 is a trap transition. t8 is also a receiving transition for message e. Since there exists no other receiving transition for message e, it is obvious that sending message e will either lead N1 into a trap state (if t8 res) or it leads N1 to ignore message e (if t8 does not re). Therefore message e is not sent by any WT-controller.
To make sure that a speci c message m is to blame for leading to a trap marking, we analyze its receiving transitions and check if each of them is either a trap transition or has a ring limit of 0. In that case, we tag m as a trap message in the message pro le. In N1, only message e is a trap message. With the help of the example open net N1 (Fig. 1) we have shown that we are able to gain knowledge about the interactional behavior directly from the inner of N1 without knowing any controller C or building up the reachability graph of N1 C. We now know that any RI-Controller C sends messages a and c not more than once and completely avoids to send messages b and e. After having sent a message x 2 fa; c; eg, C sends no more messages from fa; c; eg.
Currently, we work on a prototypical implementation of our results. We explore solutions for nding ring limits for transitions. Further, we improve our analysis methods and work on combining the methods to accomplish synergy e ects. So far, we only focus on receiving messages. It is also possible to extend the message pro le not only by further dependencies between receiving messages, but to include information about sending messages as well. Regarding that, we aim at developing a concept of compatibility of message pro les of two services in order to improve matching of two services.