Minimum-cost delegation in service composition

The paradigm of automated service composition through the integration of existing services promises a fast and efficient development of new services in cooperative service (e.g., business) environments. Although the “why” part of this paradigm is well understood, many key pieces are missing to utilize the available opportunities. Recently “service communities” where service providers with similar interests can register their services are proposed toward realizing this goal. In these communities, requests for services posed by users can be processed by delegating them to existing services, and orchestrating their executions. We use a service framework similar to the “Roman” model departing from it particularly assuming service requirements are specified in a sequence form. We also extend the framework to integrate activity processing costs into the delegation computation and to have services with bounded storage as opposed to finite storage. We investigate the problem of efficient processing of service requests in service communities and develop polynomial time delegation techniques guaranteeing optimality.