Service Oriented Architecture (SOA) support decentralized and loosely coupled applications. In particular, parties make functionality available as a service, which is maintained and controlled independent of a centralized coordinator. Further, loose coupling supports late binding of services, i.e., a service requestor may decide at run-time which service provider to use for that particular collaboration. As a consequence of these decentralized decisions and the lack of a centralized coordinator, a decentralized decision has to be made whether the composed collaboration will be successful, thus will not be deadlocked. In this book a formal workflow model for checking bilateral consistency in a composed collaboration is presented. This approach is extended to multi-lateral consistency checking without centralized coordination. Further, the approach is evaluated by applying the workflow model in the Web Service domain.