Automatic Failure Recovery in Protocol-Based Web Service Composition

In a protocol-based Web service composition, a set of available component services collaborate together in order to provide a new composite service. An execution of the composite corresponds to a sequence of delegations to component services. Thus, the runtime unavailability of one or more components may result in a failed execution of the composite. Therefore, it is necessary to establish a recovery mechanism that allows the composite service to overcome the occurred failure. In this work, we study the automatic recovery problem in the protocol-based Web service composition. A recovery is a process migrating the failed execution into an alternative execution of the composite that we call a recovery execution. The recovery execution should be able to reach a final state. The recovery problem consists in finding the best recovery execution(s) among those available. The best recovery execution must be attainable from the failed execution with a minimal number of visible compensations with respect to the client. For a given recovery execution, we prove in this work that the decision problem associated with computing the number of invisibly-compensated transitions is NP-complete.