Tevfik Bultan,
Xiang Fu,
Richard Hull, and
Jianwen Su
Conversation Specification: A New Approach to
Design and Analysis of E-Service Composition
Proceedings of 12th International World Wide Web Conference (WWW),
May 21-23, 2003
This paper introduces a framework for modeling and specifying
the global behavior of e-service compositions.
Under this framework, peers (individual e-services) communicate
through asynchronous messages and
each peer maintains a queue for incoming messages.
A global "watcher" keeps track of messages as they occur.
We propose and study a central notion of a "conversation",
which is a sequence of (classes of) messages observed
by the watcher.
We consider the case where the peers are represented
by Mealy machines (finite state machines with input and output).
The sets of conversations exhibit unexpected behaviors.
For example, there exists a composite e-service based on Mealy
peers whose set of conversations is not context free (and not
regular).
(The set of conversations is always context sensitive.)
One cause for this is the queuing of messages;
we introduce an operator "prepone" that simulates
queue delays from a global perspective and
show that the set of conversations of each Mealy e-service
is closed under prepone.
We illustrate that the global prepone fails to
completely capture the queue delay effects and
refine prepone to a "local" version on conversations
seen by individual peers.
On the other hand,
Mealy implementations of a composite e-service will always
generate conversations whose "projections" are consistent
with individual e-services.
We use projection-join to reflect such situations.
However,
there are still Mealy peers whose set of conversations is not
the local prepone and projection-join closure of any regular language.
Therefore, we propose conversation specifications as a formalism
to define the conversations allowed by an e-service composition.
We give two technical results concerning the
interplay between the local behaviors of Mealy peers and
the global behaviors of their compositions.
One result shows that for each regular language L,
its local prepone and projection-join closure
corresponds to the set of conversations by some Mealy peers
effectively constructed from L.
The second result gives a condition on the shape of a composition
which guarantees that the set of conversations that can be
realized is the local prepone and projection-join closure of a
regular language.