Progress in Web services composition

As a specific form of web service composition, automatic synthesis of web services business protocols aims at solving algorithmically the problem of deriving a mediator that realizes a business protocol (i.e., visible behavior) of a target service using a set of specifications of available services. This problem, and its variants, gave rise to a large number of fundamental research work over the last decade. However, existing works considered this problem under the restriction that the number of instances of an available service that can be involved in a composition is bounded by a constant k which is fixed a priori. We investigate the unbounded variant of this problem using a formal framework in which web service business protocols are described by means of Finite State Machines (FSM).
  • We show that in this context the protocol synthesis problem can be reduced to that of testing simulation preorder between an FSM and an (infinitely) iterated product of FSMs. Existing results regarding close decision problems in the context of the so-called shuffle languages are rather negative and cannot be directly exploited in our context.
  • We prove the decidability of testing simulation in our case of interest. We provide complexity bounds for the general protocol synthesis problem and identify two cases of particular interest, namely loop-free target services and hybrid states-free component services, for which protocol synthesis is shown to be respectively np-compete and exptime.

Simulation in data-centeric business protocols

We consider the problem of analyzing specifications of data-centric services (or artefact-centric business processes). Specifications of such services incorporate data in business protocols. We focus our study on the decidability of the problem of checking the simulation preorder in the framework of the Colombo model. Colombo is a data-centric service that appears, at a first glance, to have a limited expressivity.
  • We show that both simulation and state reachability problems are undecidable. Even worse, these problems remain undecidable in the case of non-communicating, read-only services.