15-440: Distributed Systems Syllabus

Textbook

Distributed Systems
Maarten Van Steen & Andrew S. Tanenbaum
Published by CreateSpace Independent Publishing Platform, ISBN 978-1543057386, 3rd edition.

The lecture notes will be available after each lecture to assist with studying -- please read them as they often contain material that goes beyond just what we covered in lecture! For supplemental reading in particular areas, you may find one of the following texts, available from the library, helpful:

Computer Networks: A Systems Approach, fourth edition, by Larry Peterson and Bruce Davie.
Operating Systems Concepts seventh edition, by Silberschatz, Galvin and Gagne
For the projects, please see Dave's Notes on Software Engineering for Systems Hackers.
For programming, see Unix Network Programming: Networking APIs: Sockets and XTI (Volume 1) by W. Richard Stevens.
Advanced Programming in the Unix Environment by W. Richard Stevens, Addison-Wesley, 1993.

Grading

Your final grade for the course will be based on the following weights for the components of the course. The weights of the individual projects will vary slightly by the difficulty of the project:

45% Projects
15% Homework
20% Midterm 1
20% Midterm 2

The midterms will be in-class, closed-book exams. While they may cover all material to that point in the class, their content will emphasize the material covered since the previous exam. The final exam will be a closed-book exam, covering material from the whole semester, with slight emphasis on material covered since the last midterm.

For more information about the project component, see the assignments page.

The homework will combine both textbook-like questions as well as hands-on experimental exercises. There will be three homework assignments.

Because of the importance of understanding both the theoretical and hands-on elements of systems, students must pass all three components of the course (homeworks, exams, and the projects) in order to receive a passing grade for the course. This does not affect the actual letter grade assignment unless one of the components is not completed to a passing standard.

Schedule

Lecture Recordings: you can find videos at the recording folder.

Date	Instructor	Topics	Notes	Readings
Tue 08/31	yuvraj	Introduction [pdf]		Tanenbaum 1.1, 1.2
Thu 09/02	yuvraj	Communication 1, the Internet in a Day, day 1 [pdf]		Tanenbaum 4.1
Tue 09/07	yuvraj	Communication 2, the Internet in a Day, day 2 [pdf]	Additional reading, End-to-End argument of system design .
Wed 09/08	TAs	P0 Recitation [pdf]
Thu 09/09	yuvraj	Consistency - Classical synchronization + Go-style concurrency [pdf]	Chapter on Condition Variables from the Wisconsin OS book , for more information. Rob Pike - Go Concurrency Patterns	Kesden concurrency notes
Tue 09/14	rashmi	Time and Synchronization [pdf]	Optional readings. (1) Recent research on time sync protocols (2019) HUYGENS (PDF). (3) A recent blog from Facebook Engineering on their NTP service FB Blog	Tanenbaum 6.1-6.2
Thu 09/16	rashmi	Distributed Mutual Exclusion [pdf]		Tanenbaum 6.3-6.4
Tue 09/21	yuvraj	Remote Procedure Calls [pdf]		Tanenbaum 4.2
Wed 09/22	TAs	P1 Recitation [pdf]
Thu 09/23	rashmi	Distributed Filesystems [pdf]	See also the book chapters on AFS and NFS from the Wisconsin OS book.
Tue 09/28	rashmi	Distributed Filesystems 2 [pdf]		CODA paper. See also the book chapters on AFS and NFS from the Wisconsin OS book.
Wed 09/29	TAs	Debugging Skills Recitation [pdf]	We will teach you how to debug your projects. If you plan to ask debugging questions during Office Hours or on Piazza, please attend.
Thu 09/30	yuvraj	Concurrency Control (2PL,2PC,3PC) [pdf]		Tanenbaum 8.1, 8.5
Tue 10/05	yuvraj	Logging and Crash Recovery [pdf]	Wikipedia Algorithms for Recovery and Isolation.	Tanenbaum 8.1, 8.6
Wed 10/06	TAs	P1 Part B Recitation [pdf]
Thu 10/07	yuvraj	Distributed Replication [pdf]	Further reading for Paxos. Also check out the Raft consensus algorithm and a nice Vizualization of how it works!	Tanenbaum Ch7 (p364-p370, p398-p401), Tanenbaum 8.2, Paxos Made Simple Paper
Tue 10/12		FIRST MIDTERM EXAM	During class. 10.05am to 11.30am (please come 5 minutes early and plan to leave around 11:35). In GHC 4401."
Thu 10/14		No Class, Mid Semester Break!
Tue 10/19	PhD TAs	Fault Tolerance & RAID [pdf]	See also the book chapter from the Wisconsin book.
Wed 10/20	TAs	P2 Recitation [pdf]	Check out the Raft consensus algorithm and a nice Vizualization of how it works!
Thu 10/21	rashmi	Data center storage (GFS / HDFS) [pdf]	Read Sections 2.3-2.6, 3.1, 3.3, 5.1, 5.2 in the the Google Filesystem paper. Optional GFS follow-up interview.
Tue 10/26	rashmi	Distributed Computing, MPI, and MapReduce/Hadoop [pdf]	Read Sections 3 and 4 in the MapReduce paper, it's pretty readable.
Thu 10/28	rashmi	In-memory cluster compute, Spark, Distributed ML [pdf]	Spark/RDD Paper, Helland on Immutability, further refs in slides
Tue 11/02	rashmi	Internet Content Delivery [pdf]	Optional readings Akamai paper, consistent hashing theory paper (summary paper), Dropbox Blog Post (10/10/18)	Tanenbaum 5.1-5.5, 7.6
Thu 11/04	PhD Student TAs	Publish-Subscribe, Kafka [pdf]
Tue 11/09	yuvraj	Virtualization [pdf]	See also the book chapter on Virtual Machines from the Wisconsin OS book
Thu 11/11	rashmi	Scaling 3-tier Webservice Architectures [pdf]
Tue 11/16	yuvraj	Security Protocols [pdf]	See wikipedia entry for needham-schroeder and wikipedia entry for Diffie-Hellman.	Tanenbaum 9.1-9.3
Wed 11/17	TAs	P3 Recitation [pdf]
Thu 11/18	yuvraj	Security II, Case Study - Anonymous Routing and TOR [pdf]
Tue 11/23		No Class, Early Thanksgiving
Thu 11/25		No Class, Thanksgiving
Tue 11/30	rashmi	Byzantine Fault Tolerance [pdf]	See also an online lecture about BFT by Barbara Liskov, and the PBFT paper. Optional (fun) read James' Saddest Moment	Tanenbaum pages 449 - 460
Thu 12/02		SECOND MIDTERM EXAM	During class. 10.05am to 11.30am (please come 5 minutes early and plan to leave around 11:35). In GHC 4401.