Cloud platforms are increasingly being used for hosting a broad diversity of services from traditional e-commerce applications to interactive web-based IDEs and crowdsourcing systems. However, the proliferation of offers by cloud providers raises several challenges. Developers will not only have to deploy applications for a specific cloud, but will also have to consider migrating services from one cloud to another, and to manage distributed applications spanning multiple clouds. In order to address these challenges, we present a federated multi-cloud PaaS infrastructure that is based on three foundations: i) an open service model used to design and implement both our multi-cloud PaaS and the SaaS applications running on top of it, ii) a configurable architecture of the federated PaaS, and iii) some infrastructure services for managing both our multi-cloud PaaS and the SaaS applications. We report on the deployment of this cloud-based infrastructure on top of thirteen existing IaaS/PaaS.