On-the-fly algorithm for the service composition problem

Abstract

Web services are form of middleware to exchange information between systems over a network. With the advent of the age of mobile devices and their diversity, the importance of web services became all the more apparent. Every web service grants certain functionality and can utilize other web services to gain more functionality and more robustness. Such a service that combines the functionality of other services is called a composite service and the process of designing such a service is called a composition. This thesis studies an on-the-fly algorithm that efficiently checks for the possibility of matching a target composition from a community of services. The algorithm proposes that a match for the target service can be found on-the-fly by visiting a select number of service states instead of having to parse the entire state space. Furthermore, On-the-fly can be paired with some heuristics or business rules for faster implementation and higher quality of service. The correctness of the algorithm was proven and the complexity was to be optimal. The implementation on test cases is very promising.