Automatic composition of prototocol-based Web services
Ramy Ragab Hassen · 2009
Web services enable flexible integration and interoperability of autonomous, heterogeneous and distributed applications. A core challenge for the web services technology is the development of techniques and tools for automatically generating composite servicess by taking into account their behavioral properties (e.g. business protocols). In this thesis, we focus on the problem of automatic composition of web services. We consider web services described by their business protocols which are formalized as finite states machines. Previous works on this problem dealt with the particular case where the number of instances of each component service is bounded and fixed a priori. We tackle the general case of the protocol synthesis problem where the number of instances of each component service that can be used in a composition is not bounded a priori. More precisely, we consider the following problem: 'given a set of n available web service protocols P1, . . . , Pn and a new target protocol PT , can the behavior described by PT be synthesized by combining the behaviors described by the available protocols?'. In order to cope with this problem, we first propose a formal framework for the composition synthesis based on both the simulation preorder and the shuffle closure of finite states machines. We prove its decidability through a sound and complete composition algorithm. Then, we conduct a complexity analysis of the composition problem. More precisely, we provide upper and lower bounds on the problem complexity. We also focus on several particular cases of this general problem. Finally, we implement a composition prototype within the framework of the ServiceMosaic platform.