Degree Type


Date of Award


Degree Name

Master of Science


Computer Science

First Advisor

Samik Basu


Web services are programs that are self-contained, self-describing, interoperable, platform-independent, and accessible over a network. These properties allow several Web services to be combined together to form a Web service composition. However, when a component service within a Web service composition becomes unavailable or unusable, it is necessary to identify a substitute service that can replace the failed component while preserving the original functionality of the composition. This is the problem of Web service substitution.

Most existing work that addresses this problem requires strict functional equivalence between the original component and its substitute. In contrast, Pathak et al. have shown in 2007 that it is sufficient for a substitute service to provide the same functionality with respect to the rest of the composition as the component it is replacing. Pathak et al. apply a technique called quotienting to determine the portion of the composition's overall functionality that is satisfied by the original component. The quotienting operation yields the property that must be satisfied by a substitute for that component.

While the use of quotienting allows more possible substitute services to be accepted, it is possible to relax the substitutability condition even further by considering asynchronous communication between component services within the Web service composition model. Our work accomplishes this task by providing a formal framework for representing asynchronous communication within a Web service composition. In our framework, the asynchronous communication is encapsulated in a buffer process, which stores each message until a component is ready to consume it. We prove the correctness of our solution, describe our implementation, and discuss some directions for future research.


Copyright Owner

Zachary James Oster



Date Available


File Format


File Size

74 pages