Course material 2010–11
Advanced Topics in Computer Systems
This module will attempt to provide an overview of "systems research". This is a very broad field which has existed for over 40 years and which has historically included areas such as operating systems, database systems, file systems, distributed systems and networking, to name but a few. The course will thus necessarily cover only a tiny subset of the field.
Many good ideas in systems research are the result of discussing and debating previous work. A primary aim of this course therefore will be to educate students in the art of critical thinking: the ability to argue for and/or against a particular approach or idea.
This will be done by having students read and critique a set of papers each week. In addition, each week will include presentations from a number of participants which aim to advocate or criticise each piece of work.
The rest of this page has some guidance on how to read, review and present papers, as well as links to the actual papers we'll be covering (local access only). There's also additional guidance in the introductory lecture (powerpoint). .
For most of this course you'll be expected to read 3 papers per week and provide a review in a particular format. You need to submit at least one review every week, and in total you need to submit 12. This which works out at approx 2 per week for most of the 7 weeks. Of course you may submit more than 12, in which case your overall grade will be based on the best of these. My suggestion is that, each week, you first read each paper in outline, and then choose two of those to write reviews for. Each review should be less than 1,000 words (and can be considerably shorter): there is advice in-line in the review form about what is expected for each section.
You should download the review form in either LaTeX or MS Word format. Make sure you put the title of the paper you are reviewing at the appropriate place at the top, and fill out all of the sections as instructed. You need to print out the finished reviews and submit them, along with a pink cover sheet, to student admin by 12 noon on the Monday preceeding the class.
There will be some guidance on how to read and review a paper (for this course) in the first lecture on 12th October. Additional resources that you may find useful:
- "How to Read a Paper", Keshav, ACM CCR July 2007. This is a short (2 page) paper which gives some advice on how to approach reading a research paper. For this course, you will primarily be expected to do a first and second pass for the majority of papers (i.e. no third pass). An exception will be when you are giving a presentation about a paper; in this case you will likely want to do at least some of steps in the third pass.
- "Writing Reviews for Systems Conferences", Roscoe, 2007. This is targeted more at people writing reviews for conferences, and so has quite a lot of focus on ensuring what you write is appropriate and useful to the authors. This is less relevant for this course, but you may still find the advice useful (particularly the questions in Section 4).
If you find any other documents on the web (or elsewhere) that you find useful, please let me know by email and I'll update this page.
Each week we will have 3 presentations from students. Presentations should be about 12-15 minutes long; we'll have 2 presentations (and discussion) to start, then have a short break, and have the final presentation and more discussion.
When giving a presentation, you need to cover at least:
- 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: your judgement. 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)?
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; however an Advocate should emphasise the good points, and perhaps spend less time on the negatives. 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, should still present the work fairly, but towards the end focus on the negative aspects; essentially they should try to convince the audience that the paper is not really much good! Finally, a balanced presentation should emphasise both the good and bad equally.
In order to get good grades for 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 this 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 userful 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.
Schedule & Reading List
We'll meet in SS03 for two hours every Tuesday during Michaelmas term (starting on Tuesday 12th October). The time-slot is 10am to 12noon, although realistically speaking we'll aim to start at 10:05 and be done by 11:55.
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 on which dates and time slots you are.
- Week 1: Introduction: Systems Research and System Design.
- Week 2: OS Structures and Virtual memory.
- "Virtual Memory Management in the VAX/VMS Operating System", Levy and Lipman, IEEE Computer, March 1982
- "Machine Independent Virtual Memory Management for Paged Uniprocessor and Multiprocessor Architectures", Rashid et al, ACM ASPLOS, 1987
- "On Micro-Kernel Construction", Liedtke, ACM SOSP 1995.
- Week 3: Virtualization
- "Disco: Running Commodity Operating Systems on Scalable Multiprocessors", Bugnion et al, ACM SOSP 1997.
- "Xen and the Art of Virtualization", Barham et al, ACM SOSP 2003.
- "A Comparison of Hardware and Software Techniques for x86 Virtualization", Adams and Agesen, ACM ASPLOS 2006.
- Week 4: Bugs
- "Bugs as Deviant Behavior: A General Approach to Inferring Errors in Systems Code", Engler et al, ACM SOSP 2001.
- "KLEE: Unassisted and Automatic Generation of High-Coverage Tests for Complex Systems Programs", Cadar et al, USENIX OSDI 2008.
- "Fast Byte-Granularity Software Fault Isolation", Castro et al, ACM SOSP 2009.
- Week 5: Multicore Operating Systems
- "K42: Building a Complete Operating System", Krieger et al, ACM EuroSys 2006.
- "The Multikernel: A new OS architecture for scalable multicore Systems", Baumann et al, ACM SOSP 2009.
- "An Analysis of Linux Scalability to Many Cores", Boyd-Wickizer et al, USENIX OSDI 2010.
- Week 6: Datacenter Storage
- "The Google File System", Ghemawat et al, ACM SOSP 2003.
- "BigTable: A Distributed Storage System for Structured Data", Chang et al, USENIX OSDI 2006.
- "Dynamo: Amazon's Highly Available Key-value Store", DeCandia et al, ACM SOSP 2007.
- Week 7: Data Intensive Computing
- "MapReduce: Simplified Data Processing on Large Clusters", Dean and Ghemawat, USENIX OSDI 2004.
- "Dryad: Distributed Data Parallel Programming from Sequential Building Blocks", Isard et al, ACM EuroSys 2007.
- "Large-scale Incremental Processing Using Distributed Transactions and Notifications", Peng and Dabek, USENIX OSDI 2010.
- Week 8: Deterministic Parallelism