With the emergence of cloud computing, users are increasingly using storage services of cloud providers to satisfy their storage needs. However, these cloud providers are not 100% reliable, resulting in periodic service outages. End users require a solution that minimizes the impact of cloud service outages and optimizes the chances of successfully retrieving stored objects in cases of provider failures. In this paper, we propose to build a federated cloud agent, enabling end users to simultaneously deploy storage objects to multiple cloud service providers, based on their unit storage costs and failure probabilities. We study two service provider failure models: the first case assumes that at most one service provider fails at any given time, and the second case assumes that cloud service providers may fail independently with certain probabilities. We cast both scenarios as constrained optimization problems to minimize the overall storage cost while enhancing the chances of recovering all the storage objects in case of service outages. In the experiments, we evaluated the proposed optimal storage schemes against a fixed server deployment strategy and find our schemes can achieve good recovery ratios, while incurring minimal storage costs.