In this course, we will discuss classic papers across the broad area of Systems, in roughly chronological order by area: programming languages, architecture, runtime systems, operating systems, and system design in general. This is a lecture-driven class (not a seminar); you will not be expected to present papers, but you are expected to have read every paper before class and participate in in-class discussions.
This course can be used to satisfy core requirements for Systems for the M.S. and PhD degrees.
Grades will be based on in-class participation, projects, and exams.
You must submit your reviews via the review submission site the night before each class, by 9 p.m.
See these notes by John Ousterhout on writing reviews. Focus on the positive: these are classics for a reason!
Your reviews must address the following points:
- Summary: (at least two paragraphs) What is the problem that this work addressed? What are the big ideas / key insights / technical contributions?
- Significance / Contributions: How have the assumptions / context this work was based on changed? What is the practical significance of these results today?
- Discussion Points: Include at least two discussion points to bring up in class.
You will be expected to scribe at least one lecture’s notes. Here is an example to use as a template (in LaTeX).
NOTE: The use of laptops and cell phones is not allowed in class.Tentative paper reading schedule:
|Date||Topic / Papers||Read/Review||Author(s)||Year||Area||Comments|
|The Education of a Computer||read||Hopper||1952||PL||the first compiler|
|The FORTRAN Automatic Coding System||review||Backus et al.||1957||PL||first optimizing compiler|
|Recursive Functions of Symbolic Expressions and Their Computation by Machine||review||McCarthy||1960||PL||LISP and first GC|
|9/21/2015||PL Runtime Systems|
|Garbage Collection in an Uncooperative Environment||review||Boehm & Weiser||1991||PL||conservative GC|
|Uniprocessor Garbage Collection Techniques||background||Wilson et al.||1991||PL||vast GC survey|
|A Unified Theory of Garbage Collection||background||Bacon et al.||2004||PL||model encompassing many GCs|
|Architecture of the IBM System/360||review||Amdahl et al.||1964||architecture||first “architecture” paper!|
|Structural aspects of the System/360 Model 85: The cache||read||Liptay||1968||architecture||first implemented cache|
|9/28/2015||Multicore and Parallelism|
|Cramming More Components onto Integrated Circuits||review||Moore||1965||architecture||Moore’s Law|
|Validity of the Single Processor Approach to Achieving Large Scale Computing Capabilities||review||Amdahl||1967||concurrency||Amdahl’s Law|
|Amdahl’s Law in the Multicore Era||review||Hill & Marty||2008||concurrency / arch||Amdahl’s Law|
|Wikipedia: Amdahl’s Law||background|
|The Case for the Reduced Instruction Set Computer||review||Patterson & Ditzel||1980||architecture|
|Comments on the Case for RISC||review||Clark & Strecker||1980||architecture|
|Available Instruction-Level Parallelism for Superscalar and Superpipelined Machines||review||Jouppi & Wall||1991||architecture|
10/5/2015 – 10/7/2015
|no class (SOSP)|
|An Introduction to Programming with Threads||background||Birrell||1989||concurrency / PL||background|
|Experience with Processes and Monitors in Mesa||review||Lampson & Redell||1980||concurrency / PL|
|Dthreads: Efficient Deterministic Multithreading||review||Liu et al.||2011||concurrency / PL|
|10/15/2015||OS Design and Internals|
|The Structure of the “THE”-Multiprogramming System||review||Dijkstra||1968||OS|
|Introduction and Overview of the MULTICS System||skim||Corbató & Vyssotsky||1965||OS|
|The Evolution of the UNIX Time-Sharing System||review||Ritchie||1984||OS|
|The Rise of “Worse is Better”||review||Gabriel||1991||PL / systems||MIT vs. Berkeley approach|
|10/19/2015||Networked Systems Principles|
|End-to-End Arguments in System Design||review||Saltzer, Reed, Clark||1981||systems|
|The Design Philosophy of the DARPA Internet Protocols||review||Clark||1988||networking|
|Hints for Computer System Design||review||Lampson||1983||systems|
|10/21/2015||Concurrent / Queueing Systems|
|Little’s Law as Viewed on its 50th Anniversary||review||Little||2011||systems modeling|
|Flux: A Language for Programming High-Performance Servers||review||Burns et al.||2006|
|A Note on the Confinement Problem||review||Lampson||1973||security|
|Reflections on Trusting Trust||review||Thompson||1984||security||Turing Lecture|
|11/2/2015||Privacy & Security|
|Tor: The Second-Generation Onion Router||review||anonymity||onion routing|
|A Method for Obtaining Digital Signatures and Public-Key Cryptosystems||read||RSA||1978||security||RSA algorithm|
|TBD: Project 1 Due|
|TBD: Midterm Exam|
|A Case for Redundant Arrays of Inexpensive Disks (RAID)||review||Patterson, Gibson & Katz||1988||fault-tolerant storage||classic RAID paper|
|Disk failures in the real world: What does an MTTF of 1,000,000 hours mean to you?||review||Schroeder & Gibson||2007||storage|
|Why Do Computers Stop and What Can Be Done About It?||review||Gray||1985||fault tolerance|
|Jim Gray’s Tandem Contributions||review||Nauman & Bartlett||2000||fault tolerance|
|DieHard: Probabilistic Memory Safety for Unsafe Languages
revised tech report version
|review||Berger & Zorn||2006||fault tolerance|
|Gprof: A call graph execution profiler;Retrospective||review||Graham et al.||1982||PL||profiling|
|Producing wrong data without doing anything obviously wrong!||review||Mytkowicz et al.||2009||PL||performance analysis|
|Stabilizer: Statistically Sound Performance Evaluation||review||Curtsinger and Berger||2013||PL||performance analysis|
|The Byzantine Generals Problem||review||Lamport et al.||1981||distributed systems|
|The Part-Time Parliament||for reference only||Lamport||1998||distributed systems|
|Paxos Made Simpler||for reference only||Lamport||2001||distributed systems|
|Parallel Databases||review||DeWitt & Gray||1992||concurrency / databases|
|MapReduce: A Flexible Data Processing Tool||review||Dean and Ghemawat||2010||data processing|
|MapReduce and Parallel DBMSs: Friends or Foes?||review||Stonebraker et al.||2010||databases|
|12/7/2015||Distributed & Concurrent Systems|
|Time, Clocks, and the Ordering of Events in a Distributed System||review||Lamport||1978||distributed systems||vector clocks|
|FastTrack: efficient and precise dynamic race detection||review||Flanagan and Freund||2009||concurrent systems||race detection|
|12/9/2015||Static & Dynamic Analysis|
|A Few Billion Lines of Code Later: Using Static Analysis to Find Bugs in the Real World||review||Engler et al.||2010||static analysis|
|Valgrind: A Framework for Heavyweight Dynamic Binary Instrumentation||review||Nethercote & Seward||2007||dynamic analysis|
|supplementary||“Modern” Programming Languages|
|Why Functional Programming Matters||review||Hughes||1990||programming languages||functional programming|
|A Haskell Retrospective||for reference||Peyton-Jones||2003||functional programming||Haskell|
|An empirical study of the reliability of UNIX utilities (Fuzz Testing)||review||Miller||1990||software engineering||testing|
|DART: Directed Automated Random Testing||review||Godefroid et al.||2005||software engineering||testing|
|The Anatomy of a Large-Scale Hypertextual Web Search Engine||read||Brin and Page||1995||data centers||Google!|
|Spanner: Google’s Globally-Distributed Database||read||All Google Employees||2012||data centers||Google + 17 years|
|Project 2 due TBD|
|Final Exam TBD|
All projects in this course are to be done by you / your group. Violation will result in a zero on the project in question and initiation of the formal procedures of the University. We use an automated program and manual checks to correlate projects with each other and with prior solutions. At the same time, we encourage students to help each other learn the course material. As in most courses, there is a boundary separating these two situations. You may give or receive help on any of the concepts covered in lecture or discussion and on the specifics of programming language syntax.
You are allowed to consult with other students in the current class to help you understand the project specification (i.e. the problem definition). However, you may not collaborate in any way when constructing your solution: the solution to the project must be generated by you or your group working alone. You are not allowed to work out the programming details of the problems with anyone or to collaborate to the extent that your programs are identifiably similar. You are not allowed to look at or in any way derive advantage from the existence of project specifications or solutions prepared elsewhere.
If you have any questions as to what constitutes unacceptable collaboration, please talk to the instructor right away. You are expected to exercise reasonable precautions in protecting your own work. Don’t let other students borrow your account or computer, don’t leave your program in a publicly accessible directory, and take care when discarding printouts.