The next generation of Platforms as a Service (PaaS) for cloud providers demand consistency, availability, and simpler programming abstractions, such as transactional consistency. Obtaining these three properties simultaneously is, however, a significant challenge. In CumuloNimbo, we propose to achieve this goal by building a stackable and modular execution platform that can be installed as a service and provides the same degree of consistency as current service-oriented platforms, however, at much higher, Internet-level, scale. Current PaaS systems sacrifice data consistency for scalability, thus increasing the complexity of building applications on top of such platforms when strong consistency guarantees are necessary. Providing such guarantees at the application level requires hiring highly-skilled programmers, which is often costly and prohibitive, especially for SMEs. As a result, many newly developed applications are unable to guarantee consistency appropriately, which quickly becomes visible to end users as flaws in the application. CumuloNimbo will develop a new Platform as a Service that will provide high scalability, at the 100+ service-nodes level, without sacrificing data consistency and simple programming abstractions. The targeted PaaS will be a transactional multi-tier software stack for cloud computing providing the same functionality to current, software multi-tier stacks, such as Java EE. Providing scalability without sacrificing consistency is a major breakthrough that will enable European stakeholders in service platforms to position in the cloud computing market with a competitive advantage.