Technical Reports
HPL-2010-191
Click here for full text:
Finding the Optimal Representation for Service Composition Using the Theory of Regions
Wang, Yin; Nazeem, Ahmed; Swaminathan, Ram
HP Laboratories
HPL-2010-191
Keyword(s): Workflow, Service Composition, Automaton, Petri net, Theory of Regions
Abstract: Service composition has received significant attention in the research community, but the focus has been on service semantics and composition algorithms, and the problem of representation of the composition outcome has been largely ignored. Ad hoc workflows are often employed, which typically sacrifice alternative paths and parallelism for the sake of simple representation. In this paper, we show how theory of regions, which was originally developed to derive Petri nets from finite state automata, can be applied to find the optimal representation of composition. To apply the theory, we first propose an automaton-based composition framework that incorporates most existing composition techniques without changing the service semantics or its description language. Then based on the special requirements of the composition representation, we develop our own Petri net synthesis algorithm that combines the benefits of two well known algorithms from the theory of regions. More specifically, our algorithm converts an automaton to an unlabeled Petri net, whenever such a conversion exists, and reduces the number of places in the net. We demonstrate that workflow-based representation can limit the concurrency even for simple input/output based service composition, while our Petri net-based representation is optimal in terms of flexibility and parallelism. Our experimental evaluations include a case study on composing Google Checkout Service, and the study on Oracle BPEL samples, for which our algorithm obtains better concurrent representations for almost all non-trivial cases.
10 Pages
External Posting Date: February 4, 2011 [Fulltext]. Approved for External Publication
Internal Posting Date: November 21, 2010 [Fulltext]