Automatic Composition of Web Services with Nondeterministic Behavior

Technical Report, Dipartimento di Informatica e Sistemistica, Università di Roma "La Sapienza". Technical Report 5-2006 2006.

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 stems naturally 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 on reduction 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.

@techreport{TR-DIS-2006-05,
   title = "Automatic Composition of Web Services with Nondeterministic
Behavior",
   year = "2006",
   author = "Daniela Berardi and Diego Calvanese and De Giacomo, Giuseppe
and Massimo Mecella",
   institution = "Dipartimento di Informatica e Sistemistica, Università
di Roma "La Sapienza"",
   number = "5-2006",
}