document: 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 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 , its local prepone and projection-join closure corresponds to the set of conversations by some Mealy peers effectively constructed from . 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 .
doc_bio_tags: B I O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O