A key challenge facing the designers of serviceoriented applications is ensuring that the autonomous services that make up these distributed applications always finish in consistent states despite application-level failures and other exceptional events. This paper addresses this problem by first describing the relationship between internal service states, messages and application protocols and then shows how this relationship transforms the problem of ensuring consistent outcomes into a correctness problem that can be addressed with established protocol verification tools.