Flow composition languages permit the construction of long-running transactions from collections of independent atomic services. Due to environmental limitations, such transac-

tions usually cannot be made to conform to standard ACID semantics. We propose set consistency, a powerful, yet intuitive, notion of consistency for long-running transactions.

Set consistency considers the collection of permanent (non-intermittent) changes made by a process, when viewed at the end of its execution. Consistency requirements for such collections of changes are specified as predicates over the atomic actions of a process. Set consistency generalizes self-cancellation, a standard consistency requirement for long-running transactions, where failed processes are responsible for undoing any partially completed work. Set consistency can also express strictly stronger requirements, such as mutual exclusion or dependency. We show that the set consistency verification problem for processes is co-NP complete and present an algorithm for verifying set consistency by reduction to propositional validity. We have implemented this algorithm and demonstrate the value and tractability of our approach on three real-world case studies. In each case, the consistency requirements can be verified within a second, demonstrating