Emery Berger

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.

---