Systems, Spring 2017

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
1/23/2017 Compilers
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
[scribe notes]
1/27/2017 Programming Languages
Recursive Functions of Symbolic Expressions and Their Computation by Machine review McCarthy 1960 PL LISP and first GC
Algol-60 Translation skim Dijkstra 1961 PL

[scribe notes]
1/30/2017 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

[scribe notes]
2/3/2017 Computer Architecture
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

[scribe notes]
2/6/2017 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
[scribe notes]
2/10/2017 Hardware/Software Interface
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

[scribe notes]
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

[scribe notes]
2/17/2017 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
[scribe notes]
2/24/2017 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
[scribe notes]
2/27/2017 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
[scribe notes]
3/3/2017 Security
A Note on the Confinement Problem review Lampson 1973 security
Reflections on Trusting Trust review Thompson 1984 security Turing Lecture
[scribe notes]
3/6/2017 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
[scribe notes]
TBD: Project 1 Due
TBD: Midterm Exam
3/10/2017 Fault-Tolerance (Hardware)
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
[scribe notes]
3/20/2017 Fault-Tolerance (Software)
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
[scribe notes]
3/24/2017 Performance Analysis
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
[scribe notes]
3/27/2017 Distributed Systems
The Byzantine Generals Problem review Lamport et al. 1981 distributed systems
Paxos made live review   Chandra et al. 2007 distributed systems
The Part-Time Parliament for reference only Lamport 1998 distributed systems
Paxos Made Simpler for reference only Lamport 2001 distributed systems
[scribe notes]
3/31/2017 Databases
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
[scribe notes]
4/3/2017 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
[scribe notes]
4/7/2017 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
4/14/2017 “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
4/18/2017 Testing
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
4/21/2017 Scale
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

Plagiarism Policy

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.