Add to ORKGAbstract. We address the problem of ensuring that, when an application execut-ing a service binds to a service that matches required functional properties, both the application and the service can work together, i.e., their composition is con-sistent. Our approach is based on a component algebra for service-oriented com-puting in which the configurations of applications and of services are modelled as asynchronous relational nets typed with logical interfaces. The techniques that we propose allow for the consistency of composition to be guaranteed based on properties of service orchestrations (implementations) and interfaces that can be checked at design time, which is essential for supporting the levels of dynamicity required by run-time s...