Conversation Specification: A New Approach to Design and Analysis of E-Service Composition

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 has 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 regular nor context free. (The set of conversations is always context sensitive.) One cause for this is the queuing of messages; we introduce an operator "prepone" that essentially simulates queue delays. 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 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 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 prepone and projection-join closure of a regular language.