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.