15-712 Syllabus

• 15-712 Home
• Syllabus
• Exams
• Announcements
• Summaries
• Project

Textbooks

There are no official texts for the course. If you're not familiar with the background material, you may wish to look at:

• Operating Systems Concepts, by Silberschatz, Galvin, and Gagne. This and the below text cover mostly background material that we assume students will be generally familiar with (both of these texts go beyond what we'll expect).
• Modern Operating Systems, 2nd edition, by Andrew S. Tanenbaum.
• Computer Networks: A Systems Approach, third edition, by Larry Peterson and Bruce Davie. It is available in the CMU Bookstore. Covers background networking material that we assume students will be generally familiar with.
• Advanced Programming in the Unix Environment by W. Richard Stevens, Addison-Wesley, 1993.
• Unix Network Programming: Networking APIs: Sockets and XTI (Volume 1) by W. Richard Stevens.
• The Art of Computer Systems Performance Analysis, by Raj Jain.
• Distributed Algorithms, by Nancy Lynch
• Remzi Arpaci-Dusseau's OS lecture notes are a great, free, online resource for background ugrad OS concepts.

You might take a peek at the two CMU undergrad systems courses for background information on operating systems (15-410) and networking (15-441).

Suggested Readings

You may also find the following readings useful:

• The Mythical Man-Month: Essays on Software Engineering, by Fred Brooks
• Scale and performance in a distributed file system, Howard, Kazar, Menees, Nichols, Satyanarayanan, Sidebotham, and West. ACM Transactions on Computer Systems (Feb 1988). This paper describes AFS, and is cited by most papers that evaluate filesystem performance. Many people simply know this paper as Howard88. You may find this interesting because you use AFS, and you may need to cite this if you build a storage system.
• End-to-end arguments in system design, Saltzer, Reed, and Clark. ACM Transactions on Computer Systems (Nov 1984). This paper presents the design principle that functionality should be end-to-end. For example, data should be verified or encrypted at the source and destination rather than along the way. Mechanisms in the middle tend to be redundant.

Grading

Your final grade for the course will be based on the following weights:

• 40% Project
• 20% Midterm exam
• 20% Final exam
• 20% Paper Summaries, homeworks, and participation

The project in 15-712 is an open-ended research project, done in groups of three. The project requires a proposal, a project status report, and a final report (both written and presented).

Schedule

Also available as an ical file that you can subscribe to.

Date	Topics	Notes	Readings
Mon 09/09	Introduction [pdf] [key]		Lampson84, Gabriel91–Section 2.1 only, Hamming
Part 1: Concurrency, Threads, Parallelism, Ordering, and Races
Wed 09/11	Implementing remote procedure calls [pdf] [key]		Birrell84
Fri 09/13	no class
Mon 09/16	Using threads in interactive systems: A case study [pdf] [key]		Hauser93
Wed 09/18	Time, Clocks, and the Ordering of Events in a Distributed System [pdf] [key]		Lamport78
Fri 09/20	Eraser: A Dynamic Data Race Detector for Multi-Threaded Programs [pdf] [key]	Mentioned in class: Bugs as Deviant Behavior.	Savage97
Part 2: Storage and Remote DMA
Mon 09/23	A Case for Redundant Arrays of Inexpensive Disks (RAID) [pdf] [key]	Therac-25, NY Times article	Patterson88, Schroeder07
Wed 09/25	AFS	Leases paper	Howard88
Fri 09/27	Separating data and control transfer in distributed operating systems, The Direct Access File System	no DeBergalis required. NFS over RDMA paper mentioned in class.	Thekkath94, DeBergalis03
Mon 09/30	The Design and Implementation of a Log-Structured File System [pdf] [key]		Rosenblum92
Wed 10/02	No class, enjoy the brain space
Fri 10/04	MapReduce and Dryad		Dean04, Dryad
Mon 10/07	OS Architecture and Extensibility: SPIN and the Exokernel [pdf] [ppt] [key]	Project groups and initial ideas due	Bershad95, Kaashoek97
Wed 10/09	No Lecture -- meetings with course staff to discuss project proposal
Fri 10/11	Kernels and Parallelism		Multikernel
Part 3: Transactions and Databases
Mon 10/14	On Optimistic Methods for Concurrency Control [pdf] [key]	Project proposal due (in class). For further reading, see Spectulative Execution in a Distributed File System	Kung81
Wed 10/16	Efficient Locking for Concurrent Operations on B-Trees [pdf] [key]	See also Chord-Sigcomm2001 if you'd like more details.	Lehman81
Fri 10/18	no class - mid-semester break
Mon 10/21	Principles of Transaction-Oriented Database Recovery [pdf] [key]	Bernstein's concurrency notes - MVCC, Why snapshot isolation is useful, short paper about an anomaly in snapshot isolation, mentioning history.	Franklin97
Wed 10/23	No class, review for midterm
Fri 10/25	Midterm Exam
Mon 10/28	No class
Wed 10/30	Midterm Review and Project Discussions	Please come talk with staff in course room
Fri 11/01	BigTable		Chang06
Mon 11/04	No class - SOSP
Wed 11/06	No class - SOSP
Fri 11/08	Dynamo		Vogels07
Mon 11/11	Project meetings (all day)	Please schedule a 30 minute time slot
Part 4: Generalized Fault Tolerance
Wed 11/13	No class
Fri 11/15	Paxos [pdf] [key]	Wikipedia Paxos article. Lamport's original Greek parable.	Lamport01
Mon 11/18	No class
Wed 11/20	The Byzantine General's Problem, Practical Byzantine Fault Tolerance [pdf] [ppt]	Lamport's comments on the Byzantine Generals paper (see also here).	Castro99, Lamport82
Fri 11/22	No class
Mon 11/25	Reflections on Trusting Trust, Why Cryptosystems Fail, Crisis and Aftermath [pdf] [key]		Thompson84, Anderson94, Spafford89
Wed 11/27	No class	Early turkey day
Fri 11/29	No class	Turkey day
Part 5: Security
Mon 12/02	Class Canceled - Instructor still sick. :(
Wed 12/04	X-Ray	Paper is here
Fri 12/06	Midterm 2
Mon 12/09	Project Presentations
Tue 12/10	Final report due