Cloud computing is fast emerging as a popular choice for a variety of business needs. Providing adequate fault tolerance guarantees to diverse applications is an important challenge. Fault tolerance needs vary from one application to another. Fault tolerance consumes resources. In this paper, we propose fault tolerance to be added as a service, termed here as FTaaS, which can provide both spatial and temporal redundancies. A tenant (who seeks fault tolerance services) can express its intended fault tolerance level as part of the Service Level Agreement (SLA). In this paper, we investigate a general setting, where a tenant can execute in different modes, with different fault tolerance criterion. The task of a provider (who sells fault tolerance services) is to configure his offerings in accordance to the tenants' requirements, in a way which keeps his customers satisfied and his revenue is maximized. We consider several variations of this problem in the paper. We also discuss the other side of the tenant-provider setting, wherein a tenant has multiple providers to choose from, keeping in mind the requirements he has and the cost he has to pay to avail the services. We present formulations of optimization problems related to these in this work.