Contract-based discovery of Web services modulo simple orchestrators

Web services are distributed processes with a public description of their behavior, or contract. The availability of repositories of Web service descriptions enables interesting forms of dynamic Web service discovery, such as searching for Web services exposing a specified contract. This calls for a formal notion of contract equivalence satisfying two contrasting goals: being as coarse as possible so as to favor Web services reuse, and guaranteeing successful client/service interaction. We study an equivalence relation that achieves both goals under the assumption that client/service interactions may be mediated by simple orchestrators. In the framework we develop, orchestrators play the role of proofs (in the Curry-Howard sense) justifying an equivalence relation between contracts. This makes it possible to automatically synthesize orchestrators out of Web services contracts.