Course pages 2016–17
Advanced Topics in Computer Systems
The slides I gave in the introductory lecture are here.
Schedule & Reading List
We'll meet in for two hours every Tuesday during Lent term (starting on January 24th, 2017). The time-slot is 16.00—18.00, although realistically speaking we'll aim to start at 16.05 and be done by 17.55.
Each week we will generally have 3 presentations from students. Presentations should be about 15—18 minutes long; we'll have 2 presentations (and discussion) to start, then have a short break, and have the final presentation(s) and more discussion.
The paper schedule for this year is given below. The associated presentation schedule, which has been generated at random, is here. Please be sure to check that you know which papers you are presenting, what kind of flavour of presentation you should write, and in which slot (date and time) you are presenting.
Week 1: Introduction: Reflections on Systems Design
- Hints for Computer Systems Design (Revised), Lampson. 1983. ACM SOSP 1983, pp.33—48. DOI (original); URL (revised version).
- The role of motherhood in the pop art of system programming, Neumann. 1969. ACM SOSP 1969, pp.13—18. DOI.
- Theory and practice in operating system design, Needham and Hartley. 1969. ACM SOSP 1969, pp.8—12. DOI.
Week 2: OS Structures
- The UNIX time-sharing system, Ritchie and Thompson. 1974. Commun. ACM 17(7):365—375. DOI. Revised version of paper appearing at ACM SOSP 1973.
- Exokernel: an operating system architecture for application-level resource management, Engler et al. 1995. ACM SOSP 1995, pp.251—266. DOI.
- Unikernels: Library Operating Systems for the Cloud, Madhavapeddy et al. 2013. ACM ASPLOS 2013, pp.461—472. DOI.
Week 3: Virtualisation
- Xen and the Art of Virtualization, Barham et al. 2003. ACM SOSP 2003, pp.164—177. DOI.
- Container-based operating system virtualization: a scalable, high-performance alternative to hypervisors, Soltesz et al. 2007. ACM EuroSys 2007, pp.275—287. DOI.
- Light-Weight Contexts: An OS Abstraction for Safety and Performance, Litton et al. 2016. USENIX OSDI 2016, pp.49—64. URL.
Week 4: Consensus [ w/ Heidi Howard ]
- The Chubby lock service for loosely-coupled distributed systems, Burrows. 2006. USENIX OSDI 2006, pp.335—350. URL.
- In Search of an Understandable Consensus Algorithm, Ongaro and Ousterhout. 2014. USENIX ATC 2014, pp.305—319. URL.
- ZooKeeper: Wait-free coordination for Internet-scale systems, Hunt et al. 2010. USENIX ATC 2010. URL.
Background
- Paxos Made Moderately Complex, van Renesse and Altinbuken. 2015. ACM Comput. Surv. 47(3). DOI.
- Separating agreement from execution for byzantine fault tolerant services, Yin et al. 2003. ACM SOSP 2003, pp.253—267. DOI.
Week 5: Cluster Scheduling
- Large-scale cluster management at Google with Borg, Verma et al. 2015. ACM EuroSys 2015. DOI.
- Fuxi: a fault-tolerant resource management and job scheduling system at Internet scale, Zhang et al. 2014. Proc. VLDB Endow. 7(13):1393—1404. DOI.
- Firmament: Fast, Centralized Cluster Scheduling at Scale, Gog et al. 2016. USENIX OSDI 2016, pp.99—115. URL
Week 6: Data Intensive Computing
- MapReduce: Simplified Data Processing on Large Clusters, Dean and Ghemawat. 2004. USENIX OSDI 2004. URL.
- Dryad: Distributed Data Parallel Programming from Sequential Building Blocks, Isard et al. 2007. ACM EuroSys 2007, pp.59—72. DOI.
- Pregel: A System for Large-Scale Graph Processing, Malewicz et al. 2010. ACM SIGMOD 2010, pp.135—146. DOI.
Week 7: Privacy
- CryptDB: Protecting Confidentiality with Encrypted Query Processing, Popa et al. 2011. ACM SOSP 2011, pp.85—100. DOI.
- Hails: Protecting Data Privacy in Untrusted Web Applications, Giffin et al. 2012. USENIX OSDI 2012, pp.47—60. URL.
- Ryoan: A Distributed Sandbox for Untrusted Computation on Secret Data, Hunt et al. 2016. USENIX OSDI 2016, pp.533—549. URL.
Week 8: Bugs
- KLEE: Unassisted and Automatic Generation of High-Coverage Tests for Complex Systems Programs, Cadar et al. 2008. USENIX OSDI 2008, pp.209—224. URL.
- Fast Byte-Granularity Software Fault Isolation, Castro et al. 2009. ACM SOSP 2009, pp.45—58. DOI.
- Pivot Tracing: Dynamic Causal Monitoring for Distributed Systems, Mace et al. 2015. ACM SOSP 2015, pp.378—393. DOI.
Presentations
When giving a presentation, you must at least cover:
- What is the background and context of the paper? What motivated the authors? What else was going on in the research community at the time? How have things changed since? These last two questions will obviously be more relevant for older papers.
- What does the paper actually say? What's the problem they tried to solve? What are the key ideas from the paper? What did the authors actually do? What were the results? Here you are trying to outline the paper in general; don't spend too much time on the results or the evaluation: instead focus on what the authors conclude, and how justified you think they are.
- What you think about the paper? What's good and what's bad? What things do you feel should have been discussed more thoroughly? What are the key takeaways? What is the likely impact, or what was the actual impact? Here you are actually giving your judgement on the paper.
In this course we're actually going to have three “flavours” of presentation; Advocate, Balanced, and Critical. These should all follow roughly the same structure described above: all must present the work fairly. However an Advocate would emphasise the good points and perhaps spend less time on the negatives, while the Critic would do the opposite. The Advocate is essentially playing the role of the original author, and is trying to “sell” the work to the audience. A Critic, on the other hand, is trying to convince the audience that the paper is not really as good as painted! Finally, a balanced presentation should emphasise both the good and bad equally.
To get the most out of this part of the course, it's important that you follow the above structure and at least attempt to match the required flavour. Remember not to spend too much time explaining the basics of the paper: everyone will have read it. The key place where you can add value (and hopefully inspire discussion!) is in your opinion of the paper – provided you can back it up!
Some common mistakes in giving presentations:
- Simply giving a repeat of the paper itself (order, reuse of text or arguments, cut'n'paste of graphs). You can certainly borrow one or two figures from the paper if you think they'll help you explain or argue better, but don't just grab the whole lot.
- Getting overly nervous or flustered. It is definitely a bit nerve-wracking to stand up in front of people and talk, and some people will find this harder than others. Remember that this is a friendly audience, behind closed doors, and that everyone is going to go through it. Try to treat the presentation as a discussion between you and your peers. And know that doing these presentations in this course will stand to you in your future research career.
- Getting defensive or angry. Remember, this is not your paper! In fact, you may be arguing a case that you don't believe in. So don't feel like you need to defend the paper against all criticism. And if you don't understand a question (or even part of the paper), just say so: no-one is expected to be an instant expert on such a wide variety of topics after only a few days or weeks.
To give you a feeling for the kinds of presentations expected, there are a few examples. These are for papers not assigned this year, so you may find them a useful resource in any case.
- "EROS: a fast capability system", Shapiro et al, ACM SOSP 1999.
EXAMPLE1, EXAMPLE2. - "Labels and Event Processes in the Asbestos Operating System",
Efstathopolous et al, ACM SOSP 2005.
EXAMPLE1, EXAMPLE2. - "Managing Update Conflicts in Bayou, a Weakly Connected Replicated Storage
System", Terry et al, ACM SOSP 1995.
EXAMPLE. - "Practical Byzantine Fault Tolerance", Castro and Liskov, USENIX OSDI
1999.
EXAMPLE. - "Zyzzyva: Speculative Byzantine Fault Tolerance", Kotla et al, ACM SOSP
2007.
EXAMPLE1, EXAMPLE2. - "DryadLINQ: A System for General-Purpose Distributed Data-Parallel Computing
Using a High-Level Language", Yu et al, USENIX OSDI 2008.
EXAMPLE. - "Quincy: Fair Scheduling for Distributed Computing Clusters", Isard et al,
ACM SOSP 2009.
EXAMPLE1, EXAMPLE2.