Publications in Service Aggregation and Composition

Articles in Refereed Journals:

1. Ardagna, D., Pernici, B.. Adaptive Service Composition in Flexible Processes. Software Engineering, IEEE Transactions on, Vol. 33, Num. 6, pages 369-384, June 2007.
   Abstract: In advanced service oriented systems, complex applications, described as abstract business processes, can be executed by invoking a number of available Web services. End users can specify different preferences and constraints and service selection can be performed dynamically identifying the best set of services available at runtime. In this paper, we introduce a new modeling approach to the Web service selection problem that is particularly effective for large processes and when QoS constraints are severe. In the model, the Web service selection problem is formalized as a mixed integer linear programming problem, loops peeling is adopted in the optimization, and constraints posed by stateful Web services are considered. Moreover, negotiation techniques are exploited to identify a feasible solution of the problem, if one does not exist. Experimental results compare our method with other solutions proposed in the literature and demonstrate the effectiveness of our approach toward the identification of an optimal solution to the QoS constrained Web service selection problem

2. Roberto Lucchi, Manuel Mazzara. A pi-calculus based semantics for WS-BPEL . Journal of Logic and Algebraic Programming, Vol. 70, Num. 1, pages 96-118, January 2007.
   Abstract: Recently, the term Web services orchestration has been introduced to address some issues related to Web services composition, that is the way of defining a complex service out of simpler ones. Several proposals for describing orchestration for business processes have been presented in the last years and many of these languages make use of concepts as long-running transactions and compensations for coping with error handling. WS-BPEL 2.0, the most credited candidate for becoming a standard, provides three different mechanisms allowing to cope with abnormal situations: exception, event and compensation handling. This complexity makes it difficult to formally define the framework, thus limiting the formal reasoning about the designed applications. In this paper we advocate that three different mechanisms for error handling are not necessary and we formalize a novel orchestration language based on the idea of event notification as the unique error handling mechanism. To this end, we formally define the three BPEL mechanisms in terms of our calculus. It is possible to take advantages of this formal description in two ways. Firstly, this language represents by itself a proposal of simplification for WS-BPEL 2.0 including an unambiguous specification. Secondly, an implementor of an actual WS-BPEL 2.0 orchestration engine could implement simply this single mechanism providing all the remaining ones by compilation. With this attempt we intend to give a concrete contribute towards the improvement of the quality of the BPEL specification, the applicability of BPEL itself and the implementation of real orchestration engines. Finally, as a case study we consider some of the hundreds of open issues met by the WS-BPEL designers and we propose a solution making use of the experience gained developing our algebra.

3. Groenmo, R., Jaeger, M.C.. Model-driven semantic Web service composition. Software Engineering Conference, 2005. APSEC '05. 12th Asia-Pacific, To Appear, December 2005.
   Abstract: As the number of available Web services increases there is a growing demand to realise complex business processes by combining and reusing available Web services. The reuse and combination of services results in a composition of Web services that may also involve services provided in the Internet. With semantically described Web services, an automated matchmaking of capabilities can help identify suitable services. To address the need for semantically defined Web services, OWL-S and WSML have been proposed as competing semantic Web service languages. We show how the proposed semantic Web service languages can be utilized within a model-driven methodology for building composite Web services. In addition we combine the semantic-based discovery with the support for processing QoS requirements to apply a ranking or a selection of the candidates. The methodology describes a process which guides the developer through four phases, starting with the initial modelling, and ending with a new composite service that can be deployed and published to be consumed by other users.

4. Schahram Dustdar, Wolfgang Schreiner. A survey on web services composition. IJWGS, Vol. 1, Num. 1, pages 1-30, 2005.
   Abstract: Due to the web services' heterogeneous nature, which stems from the definition of several XML-based standards to overcome platform and language dependence, web services have become an emerging and promising technology to design and build complex inter-enterprise business applications out of single web-based software components. To establish the existence of a global component market, in order to enforce extensive software reuse, service composition experienced increasing interest in doing a lot of research effort. This paper discusses the urgent need for service composition, the required technologies to perform service composition. It also presents several different composition strategies, based on some currently existing composition platforms and frameworks, re-presenting first implementations of state-of the-art technologies, and gives an outlook to essential future research work.

5. Xiulan Yu, Long Zhang, Ying Li, Ying Chen. WSCE: a flexible Web Service Composition Environment. Web Services, 2004. Proceedings. IEEE International Conference on, To Appear, July 2004.
   Abstract: In this paper, we propose the concepts of virtual partner and inspector into the Web services composition. Virtual partner, as an IT level concept, is a Web service (pseudo Web service) using the same interface with the actual partner but different binding message. A virtual partner can be invoked directly by a business process described by BPEL, so that the BPEL programmer can test both application's functionality and non functionality performance early in the development cycle to avoid any problems in the final runtime, or test the selection of their partners in business level design. The IT virtual partners provide developers with a range of the techniques which let them explore every aspect of their program. Inspector is proposed when using the third-party process engine. An inspector itself is also a Web service. The programmer can register any required output information in it. The IT virtual partner and the inspector concepts have been integrated in our WSCE, a flexible Web Services Composition Environment for a business process. WSCE is a prototype of autonomic modeling and simulation environment. With the help of a third-party BPEL engine, it provides programmer with concepts and tools to facilitate business process programming.

6. Liangzhao Zeng, Benatallah, B., Ngu, A.H.H., Dumas, M., Kalagnanam, J., Chang, H.. QoS-aware middleware for Web services composition. Software Engineering, IEEE Transactions on, Vol. 30, Num. 5, pages 311-327, May 2004.
   Abstract: The paradigmatic shift from a Web of manual interactions to a Web of programmatic interactions driven by Web services is creating unprecedented opportunities for the formation of online business-to-business (B2B) collaborations. In particular, the creation of value-added services by composition of existing ones is gaining a significant momentum. Since many available Web services provide overlapping or identical functionality, albeit with different quality of service (QoS), a choice needs to be made to determine which services are to participate in a given composite service. This paper presents a middleware platform which addresses the issue of selecting Web services for the purpose of their composition in a way that maximizes user satisfaction expressed as utility functions over QoS attributes, while satisfying the constraints set by the user and by the structure of the composite service. Two selection approaches are described and compared: one based on local (task-level) selection of services and the other based on global allocation of tasks to services using integer programming.

7. Mariya Koshkina, Franck van Breugel. Modelling and verifying web service orchestration by means of the concurrency workbench. SIGSOFT Softw. Eng. Notes, Vol. 29, Num. 5, pages 1-10, ACM, 2004.
   Abstract: Verification techniques like model checking, preorder checking and equivalence checking are shown to be relevant to web service orchestration. The Concurrency Workbench of the New Century (CWB) is a verification tool that supports these verification techniques. By means of the Process Algebra Compiler (PAC), the CWB is modified to support the BPE-calculus. The BPE-calculus is a small language, based on BPEL4WS, to express web service orchestration. Both the syntax and the semantics of the BPE-calculus are formally defined. These are subsequently used as input for the PAC. As output, the PAC produces modules that are incorporated into the CWB so that it supports the BPE-calculus and, hence, provides a verification tool for web service orchestration.

8. Milanovic, N., Malek, M.. Current solutions for Web service composition. Internet Computing, IEEE, Vol. 8, Num. 6, pages 51-59, November/December 2004.
   Abstract: Web service composition lets developers create applications on top of service-oriented computing's native description, discovery, and communication capabilities. Such applications are rapidly deployable and offer developers reuse possibilities and users seamless access to a variety of complex services. There are many existing approaches to service composition, ranging from abstract methods to those aiming to be industry standards. The authors describe four key issues for Web service composition.

9. W. van der Aalst. Don't go with the flow: Web services composition standards exposed. IEEE Intelligent Systems, To Appear, Jan/Feb 2003.
   Abstract: The recently released Business Process Execution Language for Web Services (BPEL4WS) is said to combine the best of other standards for web services composition such as WSFL from IBM and XLANG of Microsoft. BPEL4WS allows for a mixture of block structured and graph structured process models thus making the language expressive at the price of being complex. Although BPEL4WS is not such a bad proposal by itself, it is remarkable how much attention this standard receives while the more fundamental issues and problems such as semantics, expressiveness, and adequacy do not get the attention they deserve. Having a standard is a very good idea. However, there are too many of them and most of them die before becoming mature. A simple indicator of this development is the increasing length of acronyms: PDL, XPDL, BPSS, EDOC, BPML, WSDL, WSCI, ebXML, and BPEL4WS are just some of the acronyms referring to various standards in the domain. Another problem is that these languages typically have no clearly defined semantics. The only way to overcome these problems is to critically evaluate the so-called standards for web services composition, i.e., Don't go with the flow!

Articles in Refereed Conferences:

1. Gero Decker, Oliver Kopp, Frank Leymann, Mathias Weske. BPEL4Chor: Extending BPEL for Modeling Choreographies. ICWS, pages 296-303, 2007.
   Abstract: The Business Process Execution Language (BPEL) is a language to orchestrate web services into a single business process. In a choreography view, several processes are interconnected and their interaction behavior is described from a global perspective. This paper shows how BPEL can be extended for defining choreographies. The proposed extensions (BPEL4Chor) distinguish between three aspects: (i) participant behavior descriptions, i.e. control flow dependencies in each participant, (ii) the participant topology, i.e. the existing participants and their interconnection using message links and (iii) participant groundings, i.e. concrete configurations for data formats and port types. As BPEL itself is used unchanged, the extensions facilitate a seamless integration between service choreographies and orchestrations. The suitability of the extensions is validated by assessing their support for the Service Interaction Patterns.

2. Anca Muscholl, Igor Walukiewicz. A Lower Bound on Web Services Composition. FoSSaCS, pages 274-286, 2007.
   Abstract: A web service is modeled here as a finite state machine. A composition problem for web services is to decide if a given web service can be constructed from a given set of web services; where the construction is understood as a simulation of the specification by a fully asynchronous product of the given services. We show an EXPTIME-lower bound for this problem, thus matching the known upper bound. Our result also applies to richer models of web services, such as the Roman model.

3. Yan-ping Chen, Zeng-zhi Li, Qin-xue Jin, Chuang Wang. Study on QoS Driven Web Services Composition. Frontiers of WWW Research and Development - APWeb 2006, Lecture Notes on Computer Science, Vol. 3841, pages 702-707, Springer Verlag, 2006.
   Abstract: Providing composed Web Services based on the QoS requirements of clients is still an urgent problem to be solved. In this paper, we try to solve this problem. Firstly, we enhanced the current WSDL to describe the QoS of services, and then gave a way to choose the proper pre-exist services based on their QoS.

4. Howard Foster, Sebastian Uchitel, Jeff Magee, Jeff Kramer. LTSA-WS: a tool for model-based verification of web service compositions and choreography. ICSE '06: Proceedings of the 28th international conference on Software engineering, pages 771-774, ACM, 2006.
   Abstract: In this paper we describe a tool for a model-based approach to verifying compositions of web service implementations. The tool supports verification of properties created from design specifications and implementation models to confirm expected results from the viewpoints of both the designer and implementer. Scenarios are modeled in UML, in the form of Message Sequence Charts (MSCs), and then compiled into the Finite State Process (FSP) process algebra to concisely model the required behavior. BPEL4WS implementations are mechanically translated to FSP to allow an equivalence trace verification process to be performed. By providing early design verification and validation, the implementation, testing and deployment of web service compositions can be eased through the understanding of the behavior exhibited by the composition. The approach is implemented as a plug-in for the Eclipse development environment providing cooperating tools for specification, formal modeling, verification and validation of the composition process.

5. Mohsen Rouached, Olivier Perrin, Claude Godart. Towards Formal Verification of Web Service Composition. Business Process Management, pages 257-273, 2006.
   Abstract: Web services composition is an emerging paradigm for enabling application integration within and across organizational boundaries. Current Web services composition proposals, such as BPML, WSBPEL, WSCI, and OWL-S, provide solutions for describing the control and data flows in Web service composition. However, such proposals remain at the descriptive level, without providing any kind of mechanisms or tool support for analysis and verification. Therefore, there is a growing interest for the verification techniques which enable designers to test and repair design errors even before actual running of the service, or allow designers to detect erroneous properties and formally verify whether the service process design does have certain desired properties. In this paper, we propose to verify Web services composition using an event driven approach. We assume Web services that are coordinated by a composition process expressed in WSBPEL and we use Event Calculus to specify the properties and requirements to be monitored.

6. Aysu Betin-Can, Tevfik Bultan, Xiang Fu. Design for verification for asynchronously communicating Web services. WWW, pages 750-759, 2005.
   Abstract: We present a design for verification approach to developing reliable web services. We focus on composite web services which consist of asynchronously communicating peers. Our goal is to automatically verify properties of interactions among such peers. We propose a design pattern that eases the development of such web services and enables a modular, assume-guarantee style verification strategy. In the proposed design pattern, each peer is associated with a behavioral interface description which specifies how that peer will interact with other peers. Using these peer interfaces we automatically generate BPEL specifications to publish for interoperability. Assuming that the participating peers behave according to their interfaces, we verify safety and liveness properties about the global behavior of the composite web service during behavior verification. During interface verification, we check that each peer implementation conforms to its interface. Using the modularity in the proposed design pattern, we are able to perform the interface verification of each peer and the behavior verification as separate steps. Our experiments show that, using this modular approach, one can automatically and efficiently verify web service implementations.

7. Gerardo Canfora, Massimiliano Di Penta, Raffaele Esposito, Maria Luisa Villani. An approach for QoS-aware service composition based on genetic algorithms. GECCO '05: Proceedings of the 2005 conference on Genetic and evolutionary computation, pages 1069-1075, ACM, 2005.
   Abstract: Web services are rapidly changing the landscape of software engineering. One of the most interesting challenges introduced by web services is represented by Quality Of Service (QoS)-aware composition and late-binding. This allows to bind, at run-time, a service-oriented system with a set of services that, among those providing the required features, meet some non-functional constraints, and optimize criteria such as the overall cost or response time. In other words, QoS-aware composition can be modeled as an optimization problem.We propose to adopt Genetic Algorithms to this aim. Genetic Algorithms, while being slower than integer programming, represent a more scalable choice, and are more suitable to handle generic QoS attributes. The paper describes our approach and its applicability, advantages and weaknesses, discussing results of some numerical simulations.

8. Gerardo Canfora, Massimiliano Di Penta, Raffaele Esposito, Maria Luisa Villani. QoS-Aware Replanning of Composite Web Services. ICWS '05: Proceedings of the IEEE International Conference on Web Services, pages 121-129, IEEE Computer Society, 2005.
   Abstract: Run-time service discovery and late-binding constitute some ofthe most challenging issues of service-oriented software engineering.For late-binding to be effective in the case of composite services,a QoS-aware composition mechanism is needed. This meansdetermining the set of services that, once composed, not only willperform the required functionality, but also will best contribute toachieve the level of QoS promised in Service Level Agreements (SLAs). However, QoS-aware composition relies on estimated QoS values and workflow execution paths previously obtained using a monitoring mechanism. At run-time, the actual QoS valuesmay deviate from the estimations, or the execution path may not bethe one foreseen. These changes could increase the risk of breakingSLAs and obtaining a poor QoS. Such a risk could be avoided byreplanning the service bindings of the workflow slice still to be executed. This paper proposes an approach to trigger and perform compositeservice replanning during execution. An evaluation has been performedsimulating execution and replanning on a set of composite serviceworkflows.

9. Casey K. Fung, Patrick C. K. Hung, Guijun Wang, Richard C. Linger, Gwendolyn H. Walton. A Study of Service Composition with QoS Management. ICWS, pages 717-724, 2005.
   Abstract: Quality of service (QoS) management in compositions of services requires careful consideration of QoS characteristics of the services and effective QoS management in their execution. A Web service is a software system that supports interoperable application-to-application interaction over the Internet. Web services are based on a set of XML standards such as simple object access protocol (SOAP). The interactions of SOAP messages between Web services form the theoretical model of SOAP message exchange patterns (MEP). Web Services Business Process Execution Language (WSBPEL) defines an interoperable integration model that facilitates automated process integration in intra- and inter-corporate environments. A service-level agreement (SLA) is a formal contract between a Web services requestor and provider guaranteeing quantifiable issues at defined levels only through mutual concessions. Based on a prior research work on message detail record (MDR), this paper further proposes a SOAP message tracking model for supporting QoS end-to-end management in the context of WSBPEL and SLA. This paper motivates the study of QoS management in a Web service composition framework with the evolution of a distributed toolkit in an industrial setting.

10. Hai Huang, Wei-Tek Tsai, Raymond Paul, Yinong Chen. Automated Model Checking and Testing for Composite Web Services.. 8th IEEE International Symposium on Object-Oriented Real-Time Distributed Computing (ISORC 2005), pages 300-307, IEEE Computer Society, 2005.
    Abstract: Web Services form a new distributed computing paradigm. Collaborative verification and validation are important when Web Services from differen vendors are integrated together to carry out a coherent task. This paper presents a new approach to verify Web Services by model checking the proces model of OWL-S (Web Ontology Language for Web Services) and to validate them by the test cases automatically generated in the model checking process. We extend the BLAST, a model checker tha handles control flow model naturally, to handle the concurrency in OWL-S. We also propose enhancement in OWL-S and PDDL (Planning Domain Definition Language) to facilitate the automated test case generation. Experiments on realistic examples are provided to illustrate the process.

11. Michael C. Jaeger, Gero Mühl, Sebastian Golze. QoS-Aware Composition of Web Services: A Look at Selection Algorithms. ICWS, pages 807-808, 2005.
    Abstract: When a composition of Web services is designed, available services are put together to form a defined flow of executions. In a discovery process, a trader proposes available Web services as potential candidates. In a succeeding selection, for each task a trader chooses one candidate to form the optimal composition due to selection criteria. This paper discusses how the selection can consider different quality-of-service (QoS) categories to determine the most suitable candidates for the composition. If more than one category is used for optimisation, a multi-dimensional optimisation problem arises. This mentions similarities to similar combinatorial problems. Then, possible solutions are proposed and their performance is evaluated.

12. Rohit Aggarwal, Kunal Verma, John A. Miller, William Milnor. Constraint Driven Web Service Composition in METEOR-S. IEEE SCC, pages 23-30, 2004.
    Abstract: Creating Web processes using Web service technology gives us the opportunity for selecting new services which best suit our need at the moment. Doing this automatically would require us to quantify our criteria for selection. In addition, there are challenging issues of correctness and optimality. We present a Constraint Driven Web Service Composition tool in METEOR-S, which allows the process designers to bind Web Services to an abstract process, based on business and process constraints and generate an executable process. Our approach is to reduce much of the service composition problem to a constraint satisfaction problem. It uses a multi-phase approach for constraint analysis. This work was done as part of the METEOR-S framework, which aims to support the complete lifecycle of semantic Web processes.

13. Jinghai Rao, Xiaomeng Su. A Survey of Automated Web Service Composition Methods. SWSWPC, pages 43-54, 2004.
    Abstract: In todays Web, Web services are created and updated on the fly. Its already beyond the human ability to analysis them and generate the composition plan manually. A number of approaches have been proposed to tackle that problem. Most of them are inspired by the researches in cross-enterprise workflow and AI planning. This paper gives an overview of recent research efforts of automatic Web service composition both from the workflow and AI planning research community.

14. Howard Foster, Sebastián Uchitel, Jeff Magee, Jeff Kramer. Model-based Verification of Web Service Compositions.. 18th IEEE International Conference on Automated Software Engineering (ASE 2003) , pages 152-163, IEEE Computer Society, 2003.
    Abstract: In this paper we discuss a model-based approach to verifying web service compositions for web service implementations. The approach supports verification against specification models and assigns semantics to the behavior of implementation models so as to confirm expected results for both the designer and implementer. Specifications of the design are modeled in UML, in the form of Message Sequence Charts (MSCs), and mechanically compiled into the Finite State Process notation (FSP) to concisely describe and reason about the concurrent programs. Implementations are mechanically translated to FSP to allow a trace equivalence verification process to be performed. By providing early design verification, the implementation, testing and deployment of web service compositions can be eased through the understanding of the differences, limitations and undesirable traces allowed by the composition. The approach is supported by a suite of cooperating tools for specification, formal modeling and trace animation of the composition workflow.

15. Rania Khalaf, Frank Leymann. On Web Services Aggregation. TES, pages 1-13, 2003.
    Abstract: The Web services framework is enabling applications from different providers to be offered as services that can be used and composed in a loosely-coupled manner. Subsequently, the aggregation of services to form composite applications and maximize reuse is key. While choreography has received the most attention, services often need to be aggregated in a much less constrained manner. As a number of different mechanisms emerge to create these aggregations, their relation to each other and to prior work is useful when deciding how to create an aggregation, as well as in extending the models themselves and proposing new ones. In this paper, we discuss Web services aggregation by presenting a first-step classification based on the approaches taken by the different proposed aggregation techniques. Finally, a number of models are presented that are created from combinations of the above.

16. Srini Narayanan, Sheila A. McIlraith. Simulation, verification and automated composition of web services. WWW '02: Proceedings of the 11th international conference on World Wide Web, pages 77-88, ACM, 2002.
    Abstract: Web services - Web-accessible programs and devices - are a key application area for the Semantic Web. With the proliferation of Web services and the evolution towards the Semantic Web comes the opportunity to automate various Web services tasks. Our objective is to enable markup and automated reasoning technology to describe, simulate, compose, test, and verify compositions of Web services. We take as our starting point the DAML-S DAML+OIL ontology for describing the capabilities of Web services. We define the semantics for a relevant subset of DAML-S in terms of a first-order logical language. With the semantics in hand, we encode our service descriptions in a Petri Net formalism and provide decision procedures for Web service simulation, verification and composition. We also provide an analysis of the complexity of these tasks under different restrictions to the DAML-S composite services we can describe. Finally, we present an implementation of our analysis techniques. This implementation takes as input a DAML-S description of a Web service, automatically generates a Petri Net and performs the desired analysis. Such a tool has broad applicability both as a back end to existing manual Web service composition tools, and as a stand-alone tool for Web service developers.

Books and Monographs:

1. J. Cardoso. Quality of Service and Semantic Composition of Workflows. Ph.D. Thesis, University of Georgia, 2002.
   Abstract: Workflow management systems (WfMSs) have been used to support a variety of business processes. As organizations adopt new working models, such as e-commerce, new challenges arise for workflow systems. These challenges include support for the adequate management of quality of service (QoS) and the development of new solutions to facilitate the composition of workflow applications involving Web services. The good management of QoS directly impacts the success of organizations participating in e- commerce activities by better fulfilling customer expectations and achieving customer satisfaction. To enable adequate QoS management, research is required to develop mechanisms that specify, compute, monitor, and control the QoS of the products or services to be delivered. The composition of workflows to model e-service applications differs from the design of traditional workflows due to the number of Web services available during the composition process and to their heterogeneity. Two main problems need to be solved: how to efficiently discover Web services and how to facilitate their interoperability. To enhance WfMSs with QoS management, we have developed a QoS model that allows for the description of nonfunctional aspects of workflow components, from a quality of service perspective. To automatically compute the overall QoS of a workflow, we have developed a mathematical model and implemented an algorithm (SWR algorithm). Our QoS model and mathematical model have been validated with the deployment and execution of a set of production workflows in the area of genetics. The analysis of the collected data proves that our models provide a suitable framework for estimating, predicting, and analyzing the QoS of production workflows. To support, facilitate, and assist the composition of workflows involving Web services, we present a solution based on ontologies. We have developed an algorithm that workflow systems and discovery mechanisms can use to find Web services with desired interfaces and operational metrics, and to assist designers in resolving heterogeneity issues among Web services. Our approach provides an important solution to enhance Web service discovery and interoperability.