CS5412 Spring 2014 Syllabus
| Date | Topic | pptx | Comments | Readings | ||
|
Th, Jan 23 |
Introduction |
(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. |
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 |
pptx
|
(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 |
|||
| 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. | 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 | 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 | 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 | 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) | 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? | 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 |
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 | 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 | 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. |
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 | 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 | 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 | 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. | 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 |
(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 |
|
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. |
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. | |||||