Automatic Composition of Web Services with Nondeterministic Behavior

Area 09 – Ingegneria industriale e dell'informazione

The promise of Web Service Computing is to utilize Web services as fundamental elements for realizing distributed applications/solutions. In particular, when no available service can satisfy client request, (parts of) available services can be composed and orchestrated in order to satisfy such a request. In this paper, we address the automatic composition when the behavior of the available services is nondeterministic, and hence it is not fully controllable by an orchestrator. The service behavior is modeled by the possible conversations the service can have with its clients. The presence of nondeterministic conversations stemsnaturally when modeling services in which the result of each interaction with its client can not be foreseen. The behavior of the component services is thus only partially controllable, and an orchestrator needs to cope with such partial controllability. We propose an automatic composition synthesis technique, based onreduction to satisfiability in Propositional Dynamic Logic, that is sound, complete and decidable. Moreover, we will characterize the computational complexity of the problem and show that the proposed technique is optimal wrt computational complexity.

SINTESI