Service-oriented computing is a new paradigm where applications run over global computational networks and are formed by services discovered and bound at run-time through the intervention of a middleware. Asynchronous Relational Nets (ARNs) were presented by Fiadeiro and Lopes with the aim of formalising the elements of an interface theory for service-oriented software designs. The semantics of ARNs was originally given in terms of sequences of sets of actions corresponding to the behaviour of the service. Later, they were given an institutionbased semantics where signatures are ARNs and models are morphisms into ground networks, that have no dependencies on external services. In this work, we propose a full operational semantics capable of reflecting the dynamic nature of service execution by making explicit the reconfigurations that take place at run-time as the result of the discovery and binding of required services. This provides us a refined view of the execution of ARNs based upon which a specialized variant of linear temporal logic can be used to express, and even to verify through standard modelchecking techniques, properties concerning the behaviour of ARNs that are more complex than those considered before.