This paper presents an approach for providing a reliable distributed Web Service Execution Engine. Instead of using a Web Service Execution Engine running on a single host to conduct the execution of a composite service, the responsibility of conducting the execution of the composite service has been delegated to the service providers that are chosen to provide the main functionalities of the tasks in the composite service. The operations of the tasks are represented as a set of XML-based notations. The notations are platform independent. Thus, they can be (a) retrieved by service providers based on different platforms, and, (b) interpreted and executed by the service providers. The approach also provides a mechanism for coping with possible failure in the system.