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/08	Introduction [pdf] [key]		Lampson84, Gabriel91–Section 2.1 only, Hamming
Part 1: Concurrency, Threads, Parallelism, Ordering, and Races
Wed 09/10	Implementing remote procedure calls [pdf] [key]		Birrell84
Fri 09/12	Using threads in interactive systems: A case study [pdf] [key]		Hauser93
Mon 09/15	Time, Clocks, and the Ordering of Events in a Distributed System [pdf] [key]		Lamport78
Wed 09/17	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
Fri 09/19	A Case for Redundant Arrays of Inexpensive Disks (RAID) [pdf]	Therac-25, NY Times article	Patterson88, Schroeder07
Mon 09/22	AFS	Leases paper	Howard88
Wed 09/24	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
Fri 09/26	The Design and Implementation of a Log-Structured File System [pdf] [key]		Rosenblum92
Mon 09/29	No class, enjoy the brain space
Wed 10/01	MapReduce and Dryad		Dean04, Dryad
Fri 10/03	OS Architecture and Extensibility: SPIN and the Exokernel [pdf] [ppt] [key]		Bershad95, Kaashoek97
Mon 10/06	No lecture - OSDI
Wed 10/08	No lecture - OSDI
Fri 10/10	No lecture	Course staff will be available to discuss project ideas
Mon 10/13	Kernels and Parallelism		Multikernel
Part 3: Transactions and Databases
Wed 10/15	On Optimistic Methods for Concurrency Control [pdf] [key]	Project groups and initial ideas due. For further reading, see Spectulative Execution in a Distributed File System	Kung81
Fri 10/17	no class - mid-semester break
Mon 10/20	Efficient Locking for Concurrent Operations on B-Trees [pdf] [key]	See also Chord-Sigcomm2001 if you'd like more details.	Lehman81
Wed 10/22	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
Fri 10/24	No class	Project proposal due (by email to staff list).
Mon 10/27	No class	Work on project and study for midterm.
Wed 10/29	No class	Work on project and study for midterm.
Fri 10/31	Midterm Exam
Mon 11/03	Midterm Review and Project Discussions	Please come talk with staff in course room
Wed 11/05	BigTable		Chang06
Fri 11/07	Dynamo		Vogels07
Mon 11/10	No class
Wed 11/12	Project meetings (all day)	Please schedule a 30 minute time slot
Part 4: Generalized Fault Tolerance
Fri 11/14	Paxos [pdf] [key]	Wikipedia Paxos article. Lamport's original Greek parable.	Lamport01
Mon 11/17	No class (dga out of town)
Wed 11/19	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/21	No class
Mon 11/24	Reflections on Trusting Trust, Why Cryptosystems Fail, Crisis and Aftermath [pdf] [key]		Thompson84, Anderson94, Spafford89
Wed 11/26	Gobble gobble (thanksgiving holiday)
Fri 11/28	No class	Turkey day
Part 5: Security
Mon 12/01	TBD
Wed 12/03	Mystery Machine	Paper is here
Fri 12/05	Midterm 2
Tue 12/09	Project Presentations
Wed 12/10	Project Presentations	Final report due before midnight tonight