Graduate Software Systems (CMPSCI 630)

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) 9/3/2013 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]            
(2) 9/5/2013 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]            
(3) 9/10/2013 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]

(4) 9/12/2013 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]            
(5) 9/17/2013 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]            
(6) 9/19/2013 Compiler/Architecture 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]            
(7) 9/24/2013 Concurrency  

  An Introduction to Programming with Threads background   Birrell 1989 concurrency / PL review  

  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]            
(8) 9/26/2013 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]            

(9) 10/1/2013 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]            

(10) 10/3/2013 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]            

(11) 10/8/2013 Security      

A Note on the Confinement Problem review   Lampson 1973 security    

Reflections on Trusting Trust review   Thompson 1984 security Turing Lecture  

[scribe notes]            

(12) 10/11/2013 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]            

10/15: No class (UMass Monday)
10/17: Midterm Exam
10/18: Project 1 Due
(13) 10/22/2013 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]            

10/24/2013 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]            

10/29: No class

10/31/2013 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 2011 PL performance analysis

[scribe notes]            

11/5: No class

11/7/2013 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]            

11/12/2013 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]            

11/14/2013 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]            

11/19/2013 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    

11/21/2013 "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  

11/26/2013 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  

12/3/2013 File Systems
  A Fast File System for UNIX review McKusick et al. 1984 OS file systems  
  The Google File System review   Ghemawat et al. 2003 OS file systems  

12/5/2013 Scale
  The Anatomy of a Large-Scale Hypertextual Web Search Engine review   Brin and Page 1995 data centers Google!  

  Spanner: Google’s Globally-Distributed Database review   All Google Employees 2012 data centers Google + 17 years  

Project 2 due 12/8

Final Exam 12/9, 10:30am

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.