Cloud computing aims to simplify distributed application development by providing location independent access to vast computing resources with services implementing fault tolerance and scalability. As applications and their associated data migrate ̀̀to the cloud,'' or data center hosted deployments, users increasingly depend on the availability and reliability of these services. Not only does downtime inconvenience users who rely on these services for access to their personal data, but it also results in lost revenue and user confidence. To increase availability, services replicate their systems and data at multiple data centers, typically using some form of eventual consistency, which results in complicated application and system designs and limits the types of applications that can use these services. This dissertation argues that strongly consistent cloud computing storage and infrastructure services can both significantly simplify and enable new classes of distributed applications by providing a basis for scalability, reliability, and availability. We propose techniques to enable cross-data center replication based on fine-grained scalable replicated state machines that offer either strong or weak consistency. Building upon these techniques, this dissertation describes how the limiting factor for availability in strongly consistent wide-area replicated services often is the time to recover a replica after a failure. We present a solution to this limitation based on a new protocol that maintains strong consistency while greatly reducing recovery time for wide- area services. Deploying these techniques and protocols for consistent cloud computing requires message routing services capable of performing arbitrary processing based on large amounts of service state. This dissertation presents a new framework for building scalable, programmable, extensible software message routers and middleboxes using commodity hardware. This framework performs favorably compared to a commercial load-balancing switch while its flexible architecture enables the protocols we propose for implementing wide-area strongly consistent replication