Late binding to services in business-to-business operations pose a serious problem for dependable system operation and trust. If third party services are to be trusted they need to be dependable. One way to address the problem is by adding fault tolerance (FT) support to service-oriented systems. However, FT techniques are yet to be adopted in a systematic way within service oriented computing. Current FT frameworks for service-oriented computing are largely protocol-specific, have poor service quality differentiation and poor support for the FT process model. This paper describes a service differentiation-aware, FT framework based on the FT process model that can be used to support service-oriented computing.