Optimal Compensation for Hierarchical Web Services Compositions under Restricted Visibility

Introduction

Web services (Alonso et al., 2004) have gained widespread acceptance in the recent past as the paradigm of choice to implement distributed systems. The most promising aspect of Web services is their composability, i.e., the ability to form new composite services by combining the capabilities of existing (component) services. The existing services may themselves be composite, and this leads to a hierarchical composition. A hierarchical composition is represented as a rooted tree where nodes denote services and the edges represent the parent-child relationship of a service invoking another service.

To make Web services suitable for mission critical applications, recent work has focused on mechanisms to provide extended functionalities like transactions, monitoring, security, etc. for Web services compositions. In this work, we focus on transactional aspects of Web services compositions. Transactions have been very successful in providing fault-tolerance, reliability and robustness to database systems (Weikum & Vossen, 2001). The idea then is to extend the same transactional guarantees to Web services. To achieve this, the transactional mechanisms have to be first adapted to accommodate the distinguishing characteristics of Web services, mainly composability, long-running nature, and privacy and security concerns. Due to their long-running nature, compensation (Garcia-Molina & Salem, 1987) based mechanisms are usually preferred for providing transactional guarantees to Web services (Biswas, 2004). Compensation consists of semantically undoing the effects of an execution, e.g., “Cancel Flight Booking” would be a compensating operation of “Book Flight”.

While compensation based transactional models have been proposed for Web services compositions, most of them consider only one level compositions, in which case, if a service X invokes another service Y, then Y can be compensated by the service provider of Y or by the provider of X. Such compensation schemes, though certainly applicable, are very restricted for hierarchical compositions. We motivate the challenges and possibilities of performing compensation in a hierarchical composition in the section titled ‘Motivational Scenario’.

In a hierarchical composition, any service execution may potentially be compensated by any of its ancestor providers at different levels. (Henceforth, we will not distinguish between a service and a provider of that service, unless explicitly stated.). Basically, providers other than the provider offering a service are also capable of compensating that service, as long as they have the necessary information required for compensation. We formalize the information required for performing compensation both in a provider dependent and independent fashion at different levels of the hierarchy in the section titled ‘Compensation Options’.

Further, given the fact that Web services model real-life activities, it is likely that the compensating operations also have a cost associated with them. As such, it becomes essential to select and perform an optimal compensation option. We accommodate the cost factor in our compensation framework in the section titled ‘Cost of Compensation’.

Unfortunately, the information required to perform compensation may not always be readily available, especially if the compensation provider is different from the initial service provider. In hierarchical compositions, by construction (top-down or bottom-up), knowledge of provider and/or execution details of services is restricted to parent-child pairs of services. Giving unrestricted access (visibility) to every provider is not a practical solution as hierarchical compositions are usually deployed in a cross-organizational setting with very strong privacy and security constraints. Thus, the visibility of a provider may range from very little knowledge to knowledge of execution details of all the services in the hierarchy. We use the Sphere of Visibility (SoV) model (Biswas & Vidyasankar, 2009) in the section titled ‘Sphere of Visibility’ to capture the visibilities of different providers in a hierarchical composition. Further, the visibilities of a group of nodes in a hierarchy may not be independent, but related. We study some specific visibility relationships motivated by real-life scenarios in the section titled ‘Visibility Relationships: Coherence and Correlation’. Finally, we study the effect of visibility restrictions on hierarchical compensation in the sections titled ‘Effect of Visibility Restrictions on Hierarchical Compensation’ and ‘Optimal Compensation under Restricted Visibility’.