Cloud computing has ushered in a new paradigm with the availability of computing as a service, letting customers share the same physical infrastructure and purchase computing resources on demand (e.g. Amazon EC2 and Windows Azure). The multi-tenancy property of cloud computing offers clients flexibility while creating a unique set of challenges in areas such as reliability and security. In this thesis we study one challenge (SecureCloud) and three opportunities (DNSCloud, WebCloud and SamaritanCloud). In SecureCloud we explore how multi-tenancy, or the sharing of resources across users, can lead to the undermining of privacy and security. Taking Amazon EC2 as an example we identify an important scheduling vulnerability in Virtual Machine Monitors (VMMs). We create an attack scenario and demonstrate how it can be used to steal cycles in the cloud. We also discuss how attacks can be coordinated across the cloud on a collection of VMs. We present a general framework of solutions to combat such attacks. DNSCloud, WebCloud and SamaritanCloud are proposals for new architectures that improve delivery of existing infrastructural services and enable entirely new functionalities. The Domain Name System (DNS) has long been recognized as the Achilles’ heel of the Internet and a variety of new (cache-poisoning and other) attacks surfacing over the past few years have only served to reinforce that notion. We present DNSCloud, a new architecture for providing a more robust DNS service that does not require a forklift upgrade (unlike DNSSEC).