Extending Substitutability in Composite Services by Allowing Asynchronous Communication with Message Buffers

We study the problem of substitution of components in a composite service, especially in the setting where the substitute is composed in an asynchronous fashion. By asynchronous composition, we mean that the participants in the composition are not required to synchronize on the input/output actions as long as the input to one participant always follows the corresponding output from another. We show that such asynchronous composition can be realized by synchronous composition of the participating components along with an appropriate buffer process. We obtain the condition which, when satisfied by a service Q₁´, allows Q₁´ to act as a correct substitute for Q₁ in a composition of services Q₁ and Q₂. Our work extends prior results on substitutability where the conditions relied on synchronous composition and/or on the structural equivalence between the substitute and the component being replaced.