Cloud computing is being increasingly adopted by individuals, organizations, and governments. However, as the computations that are offloaded to the cloud expand to societal-critical services, the dependability requirements of cloud services become much higher, and we need to ensure that the infrastructure that supports these services is ready to meet these requirements. In particular, this proposal tackles the challenges that arise from two distinctive characteristic of the cloud infrastructure.The first is that non-crash faults, despite being considered highly unlikely by the designers of traditional systems, become commonplace at the scale and complexity of the cloud infrastructure. We argue that the current ad-hoc methods for handling these faults are insufficient, and that the only principled approach of assuming Byzantine faults is too pessimistic. Therefore, we call for a new systematic approach to tolerating non-crash, non-adversarial faults. This requires the definition of a new fault model, and the construction of a series of building blocks and key protocol elements that enable the construction of fault-tolerant cloud services.The second issue is that to meet their scalability requirements, cloud services spread their state across multiple data centers, and direct users to the closest one. This raises the issue that not all operations can be executed optimistically, without being aware of concurrent operations over the same data, and thus multiple levels of consistency must coexist. However, this puts the onus of reasoning about which behaviors are allowed under such a hybrid consistency model on the programmer of the service. We propose a systematic solution to this problem, which includes a novel consistency model that allows for developing highly scalable services that are fast when possible and consistent when necessary, and a labeling methodology to guide the programmer in deciding which operations can run at each consistency level.