=Paper=
{{Paper
|id=Vol-161/paper-8
|storemode=property
|title=On Temporal Abstractions of Web Service Protocols
|pdfUrl=https://ceur-ws.org/Vol-161/FORUM_07.pdf
|volume=Vol-161
|dblpUrl=https://dblp.org/rec/conf/caise/BenatallahCPT05
}}
==On Temporal Abstractions of Web Service Protocols==
https://ceur-ws.org/Vol-161/FORUM_07.pdf
39
On Temporal Abstractions of Web Service
Protocols
Boualem Benatallah1 , Fabio Casati2 , Julien Ponge3, and Farouk Toumani3
1
CSE, UNSW, Sydney NSW 2052, Australia (boualem@cse.unsw.edu.au)
2
Hewlett-Packard Laboratories, Palo Alto, CA, 94304 USA (casati@hpl.hp.com)
3
LIMOS, UBP Clermont-Ferrand, France ({ponge,ftoumani}@isima.fr)
1 Introduction
Web services are increasingly gaining acceptance as a framework for facilitating
application-to-application interactions within and across enterprises. They pro-
vide abstractions and technologies for exposing enterprise applications as services
and make them accessible programmatically through standardized interfaces.
However, tools supporting service development today provide little support for
high level modeling and analysis of abstractions at higher level of services stack,
and in particular there is little support for protocol modeling and management.
We believe that indeed protocol modeling and management will be key in sup-
porting Web service development and interaction, and that developing formal
models and a protocol algebra will have a positive impact similar to the one that
the relational model and the relational algebra had in database technology.
When developing our framework for service protocols modeling, analysis, and
management [1, 2], we identified the need for representing temporal abstractions
in protocol descriptions. In particular, our analysis of the characteristics and re-
quirements of service protocols in terms of description languages, we found that,
in addition to message choreography constraints, protocol specification languages
need to cater for time-sensitive conversations (i.e., conversations that are charac-
terized by temporal constraints on when an operation must or can be invoked).
For example, a protocol may specify that a purchase order message is accepted
only if it is received within 24 hours after a quotation has been received. In this
paper, we discuss the augmentation of business protocols with specifications of
temporal abstractions (called timed protocols). Then we motivate, through ex-
amples, a need for analyzing timed protocol specifications, and specifically for
identifying if and under what conditions two services, characterized by certain
timed protocols, can interact. Technical details are given in an extended version
of this paper [3] where a formal timed business protocol model is presented and
operators that enable characterizing compatibility and replaceability classes for
timed protocols are described.
2 Modeling temporal abstractions in business protocols
In our approach, business protocols are modeled as deterministic finite state
machines, where the states represent the different phases in which a service may
Proceedings of the CAiSE'05 Forum - O. Belo, J. Eder, J. Falcão e Cunha, O. Pastor (Eds.)
© Faculdade de Engenharia da Universidade do Porto, Portugal 2005 - ISBN 972-752-078-2
40 Boualem Benatallah, Fabio Casati, Julien Ponge, Farouk Toumani
go through during its interaction with a requestor. Transitions are triggered by
messages sent by the requestor to the provider or vice versa (hence, transitions
are labeled with either input or output messages). As an example, Figure 1 shows
a graphical representation of a protocol P that describes the external behavior
of an order management service that allows users to buy some kinds of goods.
Each transition is labeled with a message name followed by the message polarity,
that is, whether the message is incoming (plus sign) or outgoing (minus sign)
[4]4 .
addToCart(+) removeFromCart(+)
searchGoods(+)
login(+)
Start Logged Searching
searchGoods(+)
cancellation searchGoods(+) quoteRequest(+)
deadline
expired order(+)
Uncancellable Cancellable Quoted
2880min
cancel(+) expired 4320min
deliver(−)
explicit transition initial state
cancel(+)
Delivered Canceled implicit transition final state
Fig. 1. A sample timed business protocol P.
In our previous work on protocol modeling [1], we identified that catering
for temporal abstractions in protocol descriptions is an important requirement.
In particular, our analysis of the characteristics and requirements of service
protocols in terms of description languages, we found that, although most state
transitions occur due to explicit operation invocations, there are cases in which
transitions occur without an explicit invocation by requesters. We refer to these
transitions as implicit transitions. The large majority of implicit transitions are
due to timing issues (deadline expirations). For example, many services allow
requestors to reserve a resource or to perform certain actions (invoke certain
operations) only within a time window, after which these operations cannot
be performed any more. For example, consider again the protocol P of Figure 1.
This protocol specifies that when the service enters the state Quoted, a quotation
is valid only for 3 days (equal to 4320 minutes), a time interval within which
the user can order the selected goods (operation order). After this period of
time, the conversation moves to the final state canceled, denoting that the server
has canceled the order (implicit transition expired with a temporal constraint
4320min). Note that the implicit transition expired imposes time constraints on
all transitions that can be fired from state Quoted (i.e., the operations order,
searchGoods and cancel), as once it fires it leads the conversation to a state from
which those operations are not allowed. An analogous reasoning can be applied
to transition Cancellation deadline expired.
We use the term timed busisness protocol (or timed protocol for short) to
denote a business protocol whose definition contains timed transitions. The se-
4
In this paper, we use the notation m(+) (respectively, m(−)) to denote that m is
an input (respectively, output) message.
41
mantics of timed protocols is based on the notion of timed traces. For example,
consider an execution of a service S that supports a protocol P of figure 1. We use
the expression (searchGoods(+),1) to denote the occurence of the message search-
Goods at an instant t=1. t represents the elapsed time since the beginning of the
execution of S. A timed trace of a protocol is then defined as a sequence of such
pairs. As an example, the sequence of pairs (login(+),0) . (searchGoods(+),1) .
(addToCart(+),3) . (quoteRequest(+),7) . (cancel(+),120)) is a timed trace which
is compliant with the protocol P.
3 Compatibility and replaceability in timed protocols
This section discusses the problem and motivates the need for timed protocol
analysis (and specifically compatibility and replaceability analysis). Once ser-
vices are endowed with protocol specifications, protocol management operators
can be identified to perform the following type of analysis: (1) compatibility
analysis refers to checking if the protocol of a requestor and of a provider are
compatible, that is, if conversations can take place between the services, and
(2)replaceability analysis refers to checking if a service provider R can replace
another service provider S from a protocol standpoint, that is, if R can support
the same conversation that S supports.
For both compatibility and replaceability, we have defined classes to identify
different levels of compatibility and replaceability, as well as operators that can
be applied to protocol definition to asses the level of compatibility and replace-
ability [2]. In the sequel, we discuss the novel opportunities and needs that timed
protocols bring in this regard.
Compatibility in timed protocols We present several examples related to protocol
compatibility (resp., replaceability) analysis, starting from a simple case to more
complex ones. Consider protocol P depicted on Figure 1 and its reversed protocol
P’ obtained from P by reversing the polarity of the messages (i.e., input messages
becomes outputs and vice versa). P’ can interact correctly with P in the sense
that, considering a given interaction between these two protocols, whenever P’
sends a message at an instant t, the protocol P could receive it and vice versa.
For example, protocol P’ supports the following complete timed trace: (login(-
),0) . (searchGoods(-),1) . (addToCart(-),2) . (quoteRequest(-),3) . (cancel(-),4) In
this trace, cancel is the only operation whose temporal availability is restricted
since both P and P’ have an implicit transition that is fired 4320 minutes after
having entered the Quoted state. In the previous trace the cancel message is sent
by P’ only 1 minute after the quotation has been performed, hence the message
is legal.
We now illustrate a simple example of incompatibility between two proto-
cols. Consider a protocol P’ that supports the following timed trace: (login(-),0)
. (searchGoods(-),1) . (addToCart(-),2) . (quoteRequest(-),3) . (cancel(-),4350).
During such an execution, P’ cannot interact correctly with the protocol P of
42 Boualem Benatallah, Fabio Casati, Julien Ponge, Farouk Toumani
Figure 1. Indeed, P’ will fire the operation cancel 7347 minutes after the quo-
tation has been performed, which is more than the 4320 minutes allowed by P
(i.e., P has already moved to the Canceled state).
The previous cases were simple to check because it was sufficient to compare
pairs of states locally. The following example illustrates a more complex case.
Consider the protocols P and P’ depicted on Figure 2. Unlike the previous exam-
b(−)
x(+) a(+)
start s0 s1 s2 s3 s5
(P) c(+)
i: 540min
b(+)
c(−)
x(−) a(−) b(+)
start’ s0’ s3’ s4’ s1’ s5’ s6’
(P’)
i1: 240min
i2: 300min i3: 240min
b(+)
s2’ s7’ s8’
Fig. 2. Two compatible timed protocols.
ples, the two protocols have very different shapes. For instance, we can observe
that after the execution of the operation x the protocols P and P’ move, respec-
tively, to the states s0 and s0 . These states do not offer the same operations
(at least if we consider the operations that are defined explicitly at these two
states). The state s0 provides the operations a, b and c while the state s0 only
provides the operations a and b. Consequently, focusing compatibility checking
only on these two states is not enough. Indeed the operation c for example may
be available for a client interacting with this service after 240 minutes. This is
due to the presence of an implicit transition i1 that automatically leads a service
to the state s0 from which c can be fired. Note that to check if protocol P and
P’ are compatible we need also to consider all the states that are automatically
(implicitly) reachable from a given state. In our case, checking if s0 and s0 are
compatible implies that we also consider s1 and s2 since they can be reached from
s0 through i1 and i2 . More precisely, we need to make explicit all the operations,
and their associated timing constraints, that are available at these states. For
example, as given below, looking to the implicit transitions, we can derive the
temporal availabilities of the operations at the states s0 and s0 .
⎧ ⎧
⎨ a : [0min, 540min] ⎨ a : [0min, 240min]
(P) b : [0min, 540min] (P ) b : [0min, 780min]
⎩ ⎩
c : [0min, 540min] c : [240min, 540min]
Operation a will be performed by P’ during a temporal window where P is
ready to accept the message fired by P’. The same is true for c. The case of b is
different since it is P that sends the message. The temporal window defined by P’
for receiving the related message is wider than the one used for P to send it, thus
P’ is ready to receive a message b fired by P. We see that conversations can take
place between P and P’ as the messages can be exchanged during the allowed
temporal slices defined by each protocol. However the compatibility between s 0
43
and s0 is not obvious since several other states have to be taken into account to
get to the conclusion that a compatibility is effectively possible. However, note
that compatibility is dependent on timing. In fact, not all conversations that
can be generated by the client (P) can be supported by the provider (P’). If the
client implementation is such that the client sends a message c right away after
a message x, then it will cause the provider to respond with a fault message.
a(+) b(−)
(P) s0 s1 s2
i: 3min
s4’
a(−) b(+)
s0’ s1’ s2’
(P’)
s3’
c(+)
a(−) b(+) c(+)
s0" s1" s2" s3"
(P")
Fig. 3. Another compatibility problem illustrated.
Finally, the following example shows that implicit transitions can also influ-
ence the identification of final states and this naturally impacts compatibility
analysis. Let’s consider the 3 protocols P, P’ and P” depicted on Figure 3. We
can observe that when interacting with P’ or P”, the protocol P will reach its
final state after executing the operations a and b while P’ and P” both remain
at intermediary states (respectively, the states s2 and s2 ). Clearly, this is not a
problem for P’ as this protocol is able to automatically reach a final state from
the state s2 , and hence, its terminates correctly the conversation. Therefore, the
interaction of P with P’ is correct. However, P and P” are not compatible since
P” remains in an intermediary state and will not be able to terminate correctly
its execution (i.e., to reach a final state).
The above discussion has emphasized the need for a new compatibility class,
called time-dependent compatibility. Protocols P and P’ have time-dependent
compatibility if they are compatible only when they exchange messages following
certain time constraints. Hence, time-dependent compatibility is a kind of partial
compatibility. Note that an implementation of a client may be able to read the
service provider’s protocol and time its interaction so that messages are sent
when allowed. The discussion of such “adaptive” implementations is outside the
scope of this paper, since as mentioned here we limit to protocol analysis without
discussing service implementation and compliance.
Correspondingly, the discussion has also emphasized the need for operators
that identify these time constraints resulting from the joint compatibility analysis
of the two protocols, as shown earlier.
Replaceability in timed protocols We now turn our attention to the replaceability
problem. We will provide less examples here as the previous section has already
given an indication of the issues that can arise.
Consider protocols P and P’ depicted on Figure 4. Like previously, the two
states s0 and s0 do not offer directly the same operations as a is not available
44 Boualem Benatallah, Fabio Casati, Julien Ponge, Farouk Toumani
i1: 10min
b(+) b(+)
x(+) a(−) c(+)
(P) start s0 s5 s6 s1 s7 s8
i2: 10min i4: 5min
a(−) b(+)
s2 s9 s10 s3 s11 s4
b(+) i3: 15min
i: 35min
x(+) a(−)
start’ s0’ s1’ b(+) s2’ s3’
(P’)
Fig. 4. A protocol P that can replace P’.
from s0 while it is from s0 for instance. Again, let’s have a look at the states that
are implicitely reachable from s0 and s0 to compute the temporal availabilities
of the operations:
⎧ ⎧
⎨ a : [0min, 10min], [20min, 35min] ⎨ a : [0min, 35min]
(P) b : [0min, 40min] (P ) b : [0min, 35min]
⎩ ⎩
c : [10min, 20min] c: ∅
Protocol P can handle messages x, a and b from a client that is compatible with
P’ by looking at the temporal constraints. However P has an extra operation c.
This operation being a message reception, it does not cause a problem. Indeed,
a requestor or P’ does not know about c since P’ does not support it. Thus, they
will never attempt to fire it. Finally, P can well replace P’ by looking at s0 and
s0 .
4 Discussion and Conclusions
In this paper, we build upon our earlier work on service protocols modeling,
analysis, and management [1, 2] to cater for temporal abstractions in business
protocols. In the extended version [3], we provide a formal characterization of
compatibility and replaceability classes for timed business protocols as well as
operators for analyzing these classes. This work is part of a larger framework sup-
ported by a CASE tool, partially implemented, that manages the entire service
development lifecycle. The objective of the framework is to provide a compre-
hensive methodology and platform that can facilitate large-scale interoperation
of Web services and substantially reduce the service development effort.
References
1. Benatallah, B., Casati, F., Toumani, F.: Web Service Conversation Modeling: A
Cornerstone for e-Business Automation. IEEE Internet Computing 6 (2004)
2. Benatallah, B., Casati, F., Toumani, F.: Analysis and management of web services
protocols. In: Procs of ER’04, Shanghai, China. (2004)
3. Benatallah, B., Casati, F., Ponge, J., Toumani, F.: On temporal abstractions of
web services protocols (extended version). Technical report, http://www.isima.
fr/ponge/research.shtml#TR-BCPT05a (2005)
4. Yellin, D., Storm, R.: Protocol Specifications and Component Adaptors. ACM
Trans. Program. Lang. Syst. 19 (1997) 292–333