CS5412 Spring 2014 Syllabus


Date Topic pdf pptx Comments Readings

Th, Jan 23




(1) Overview of the entire course, topics we’ll cover, the way grading will work, etc. Plus we'll discuss all those XaaS acronyms.  Many people who think they know all about cloud computing basically only know that the X in XaaS can be {I,P,S} and perhaps {BP}! Book: Preface & Intro

Tue, Jan 28

How it works



(2) How cloud client systems work. We’ll look at some typical cloud applications (music or video players, Shazzam) and ask how they do it. Book: Chapter 2, 3

Th, Jan 30

Network routing



(3) BGP, high availability routers, future secure networks. Routing has a key role to play in the cloud. But how does the Internet do routing? What options exist for controlling routing from within a cloud application? We’ll look mostly at BGP but will also discuss the resilient overlay network idea (RON), from MIT. Then we’ll ask how one might make the Internet robust in other dimensions such as security, and how it could support cloud-based routing control.

Book: Chapter 4.

Routers for the Cloud. Can the Internet Achieve 5-Nines Availability? Agapi et. al, IEEE Internet Computing. Volume 15. Issue 5. pp.72 - 77. September, October 2011.

The League of SuperNets, Ken Birman, IEEE Internet Computing, vol. 7, no. 5, 2003, pp. 92-96.

Tue, Feb 4 P2P file sharing and search



(4) Peer-to-peer protocols have transformed the Internet by making it easy for people who don’t know one another to still cooperate to share music or other kinds of files. Underlying this are two aspects: the Internet file transfer protocol (which is trivial) and the ability to search for things in a network where you only know about a few of the members. This latter functionality is often called a “key,value” store and is frequently implemented using a “distributed hash table”. We’ll study CAN and Chord, two widely known examples of DHTs. Book, Chapter 4
Th Feb 6

First and second tier cloud services



(5) We use the term “tier 2” to talk about services that are nearly as elastic and scalable as the ones in tier 1, but have roles focused on caching. Best-known examples include Memcached and Dynamo. We’ll also look briefly at GFS, BigTable, Chubby, Zookeeper, Sinfonia, MapReduce and other services and will see where each lives. We’ll only get detailed for a few of these (it would take too long to cover all of them), but we will try and identify common themes. Interestingly, although these systems run inside the cloud (not in the network, like Chord), many use the same key-value structure as Chord and in fact many evolved from ideas that originated in the P2P networking community! On the other hand, Chord itself is viewed as too slow for use in the tier 2 cloud (for a small DHT with 1000 members, Chord might need 8 or 9 routing hops to find an item, which is very costly). Another issue is that access distributions might be skewed: there could be hot spots. Sec 5.7
Tue Feb 11 Adaptive Overlays for the tier 2 cloud



(6) Motivated by the desire to use a DHT in tier2 to support technologies like the ones mentioned in lecture 5, we'll revisit the pure DHT concept and explore ways of using dynamic adaptation to compensate for skewed access distributions, skewed node-to-node latencies, etc. We’ll look at Beehive (a modified version of Chord that achieves O(c) lookup times for constant c), Pastry (a Plaxton-tree DHT structure that creates flexibility as to which nodes a given node should peer with) and Kelips (a gossip-based DHT with O(1) lookup times).

Book, Chapter 4

Th, Feb 13 Torrents and Tit-for-Tat Incentives.  BAR Gossip



(7) BitTorrent is widely used both in the P2P network world and inside cloud computing data centers. In this lecture, we’ll look closely at BitTorrent, to see exactly how its “tit for tat” concept of fairness works. This will lead us to look at an idea from UT Austin for a scheme they call “BAR” gossip

Book: Chapter 5

BAR Gossip

        February break: February 15-19  
Th Feb 20

Anatomy of a cloud. CAP theorem



(8) At every level of the cloud we struggle with deep tradeoffs: rapid response and scalability tend to fight against techniques that provide strong guarantees. Berkeley’s Eric Brewer captured one of these in his CAP theorem, which focuses on tier1 and tier2 and says you can have just two of Consistency, Availability, Fault or Partition Tolerance. We’ll see how CAP applies and how it was proved by Gilbert and Lynch. Although the proof applies only in WAN settings, we’ll also find that CAP has implications in the first tier of a typical cloud computing data center. Book, Sec. 5.3
Tue Feb 25

BASE methodology versus ACID model



(9) Many cloud systems are rejecting the database ACID guarantees in favor of what has come to be known as the BASE methodology, which weakens consistency to enhance responsiveness, but can make mistakes because of the weaker properties that must later (“eventually”) be repaired.

Guest lecture by Theo and Stavros.

Book (BASE is discussed in several chapters, but this lecture draws mostly on the material in the Preface, Introduction and Chapter 5) BASE: An Acid Alternative - ACM Queue. Dan Pritchett, eBar. ACM Queue.

Overcoming the “D” in CAP: Using Isis2 To Build Locally Responsive Cloud Services. K. P. Birman, Q. Huang, D. Freedman. IEEE Internet Computing. Volume 12. pp. 50-58. February 2012.
Th Feb 27 Consistency and time.  Logical and Vector clocks.  Consistent cuts. pdf pptx (10) To reason about stronger forms of consistency, we’ll need some abstractions. One tool that turns be especially useful was created by Leslie Lamport and offers a way to model time in terms of causal relationships. We’ll see how this leads to notions of logical clocks that sometimes make more sense that real clocks. Book, Sec 10.1 and 10.2
Tue Mar 4 2 and 3-phase commit pdf pptx (11)_We’ll look at the famous two and three phase commit protocols, which play a wide range of roles in many kinds of systems. These are used as building blocks, but are also for their own sake. Oddly, it turns out that neither protocol is able to guarantee that progress will occur, although 3PC does better than 2PC. This motivates looking more closely at just when fault-tolerance can be achieved. Section 10.3
Thu Mar 6 Consensus and the FLP theorem pdf pptx (12) We’ll look at a theoretical result most people refer to as the “FLP theorem”. FLP asserts that fault-tolerant consensus is “impossible” in asynchronous systems. What do these terms mean? How is FLP proved? What does FLP mean in practice? Section 11.3
Tue Mar 11 Paxos pdf pptx (13) This lecture will present the “basic” Paxos protocol. Paxos is a powerful protocol for managing replicated data and widely used in cloud computing systems. The Chubby lock service mentioned in lecture 7 runs on top of Paxos. Chapter 11
Thu Mar 13 Atomic multicast with Virtual Synchrony guarantees (Isis2) pdf pptx (14) We’ll review the virtual synchrony model, a less stringent way to implement replication that brings complexity not seen in Paxos, but also gains performance advantages in doing so. Isis2 employs the virtual synchrony model, but also supports Paxos (called SafeSend within the system). Chapters 11-14
Tue Mar 18 Atomic multicast: How much durability is needed? pdf pptx (15) We’ll look at the question of weak versus strong durability as it arises when applying Isis2 to replicate data in tier-1 services. Here, we’ll look at the question of how durable a multicast needs to be if the corresponding data is managed in-memory and there isn’t any way to preserve state across node failures and restarts (i.e. there is only soft-state). Book, Section 14.3.

You may also want to remind yourself of this paper, which we discussed on February 21: Overcoming the “D” in CAP: Using Isis2 To Build Locally Responsive Cloud Services. K. P. Birman, Q. Huang, D. Freedman. IEEE Internet Computing. Volume 12. pp. 50-58. February 2012
Thu Mar 20

Atomic multicast: How much ordering is needed?

Also: a quick look at a few other features of Isis2

pdf pptx (16) We’ll take a short guided tour of the Isis2 system. As a starting point we'll see that in addition to various durability properties, Isis2 offers many ordering options. Not every system needs the strongest and most costly ordering guarantees, and by picking the right protocol to match a use case, one can gain big speedups: you ideally want to pay for what you need. In the time remaining, we'll then review many of the other features of the system.  All of this adds up to. our theme: "too many options"!  But we'll also see that you can use the system without using more than a tiny subset of the features. Isis2 is a substantial system, like an operating system for distributed computing, and the fancy features are really for advanced users. Chapter 15
Tue Mar 25 Transactional model, ACID pdf pptx (17) We’ll look more closely at the ACID model mentioned in Lecture 10 and how it works. ACID is the standard way to think about database consistency. Chapter 20
Thu Mar 27 Implementing transactional services pdf pptx

(18) How can ACID-based systems be implemented? We’ll look at some basic mechanisms and will also touch upon snapshot isolation, an approach popular in cloud settings.

        Spring Break: March 29-April 6  
Tue, Apr 8

Bimodal Multicast.
Astrolabe. Notion of “information diameter” of a system

pdf pptx (19) This starts a series of “single topic” lectures (the numbering skips because we covered lecture 19 early). Bimodal Multicast is a reliable multicast built using gossip. Astrolabe is a technology used at Amazon.com for scalable monitoring, data mining and aggregation in cloud settings. An amusing bug that was introduced by a well-intentioned optimization leads us to think about the “information distance” between nodes in the system and sheds light on how gossip mechanisms work when scaled up. Chapter 21
Thu Apr 10 Building complex overlay networks using Gossip pdf pptx (20) We'll look at the work on the T-Man system at the University of Bologna.  T-Man slide set. (and as a pdf)
Tue Apr 15 The RealTime Cloud pdf pptx (21) In this lecture we'll talk about cloud computing systems that have real-time goals and the notion of a real-time QoS guarantee for a data distribution service that has associated state.  Our focus will be on work IBM did in 1995 for a new air traffic control system that was being created in the US at that time (in fact the project failed, but the reasons are very instructive) Chapter 23
Thu Apr 17 Information Retrieval in the Facebook cloud pdf pptx

(22) This lecture will focus on technologies used within the Facebook cloud.  We'll look at the ways that Facebook uses caching to accelerate worldwide photo retrieval, and then we'll dive deeper and look at the TAO subsystem it uses to track relationships and the Haystack storage backend system.

There are some nice published papers on this material.  The first part of the lecture is drawn from a paper at SOSP 2013, and then the second part on a paper from OSDI 2012 and from NDSI 2013.
Tue Apr 22 Security concerns for consolidated systems. Synthetic diversity. pdf pptx (23) Cloud security worries are a big barrier to adoption.  The paper we’ll discuss was written by Professors Schneider and Birman as a report on a study looking at these tradeoffs. Dangers of monocultures paper.
Thu Apr 24 Future cloud I: Computing on encrypted data pdf  

(24) One very new idea, still very much considered research, imagines that we might upload data to the cloud in an encrypted form and then compute on the data without actually decrypting it. We'll look at a cutting-edge idea that tackles this question, with surprisingly successful results (but also some limitations).

Chapter 19. The core idea we'll discuss in this lecture is from a set of papers that you can read on the website maintained by the main author, Raluca AdaPopa
Tue Apr 29

Future cloud II: Cloud virtualization

pdf pptx (25) We all know that virtualization plays a huge role in modern cloud settings but that virtual machine migration isn't really exploited very much. We'll talk about work by Hakim Weatherspoon and a team at IBM in which cloud virtualization is combined with migration to to let an application access sensitive files that you don’t trust the cloud to host. Hakim's approach also allows you to create a virtual image that includes resources like devices that actually live on remote machines. XenBlanket paper
Thu May 1

The cloud value proposition.

pdf pptx (26)  The cloud "Value Proposition".  We'll discuss some of the major business models for cloud enterprises to try and understand what determines value in the cloud.  This turns out to be a much trickier question than you might have expected.  
Tue May 6 Demos day: Please sign up for a good time when you can show us your work.  We would like each project or team to have a poster on the overall system and also be shown to us running on whatever machines you find convenient to use.  We can be a little flexible about the day for demos; no problem if you prefer Wednesday or Friday, and we could consider other dates too.  Talk to the TAs if you have a special need to do the demo on some non-standard day.  We normally need 15 minutes per project and want all team members to please attend.