Web Services (WSs) that provide transactional properties are useful to guarantee reliable Composite WSs (CWSs) execution. In this paper, we propose a framework for efficient, fault tolerant, and correct distributed execution of Transactional CWSs (TCWSs). Our framework relies on WSs replacement and on a compensation protocol to support forward and backward recovery. We represent a TCWS and its corresponding backward recovery process by Colored Petri-Nets (CPNs) and, to ensure correct execution and compensation flows, unfolding processes of the CPNs are followed. We formalize the TCWS execution and recovery processes based on CPN properties. We also present the framework architecture and execution and recovery algorithms. Copyright 2011 ACM.