CSE 40771/60771 - Distributed Systems - Fall 2021
9:25-10:15 MWF, Debartolo Hall 201
Prof. Douglas Thain
Email: dthain at nd dot edu
Office: 384C Fitzpatrick
Office Hours: See Web Page
TA: Yuanbo Guo
Email: yguo6 at nd.edu
Office: Hours: TBA
A distributed system is any computer system consisting of multiple machines that work together on a common problem. Distributed systems appear in many areas of computing, including cloud computing, mobile computing, edge computing, the internet of things, aerospace systems, and more. Distributed systems have been both interesting and difficult to build because their components may be autonomous and highly failure-prone. Students will learn the fundamental principles of distributed systems, study examples of current distributed systems, and build their own distributed systems from scratch. Topics include concurrency, fault tolerance, replication, consistency, agreement. Students will undertake a final project that involves building and evaluating a custom distributed system. Grading will be based on assignments, exams, and a final project.
This will be a fun and challenging class for students who like to build working software systems. Distributed systems bring together some very practical aspects of software engineering (e.g. like how to handle a network disconnection) and the fundamental principles of computers (e.g. whether a partitioned system can reach agreement.) The skills that you learn here will apply directly to advanced systems used in industry.
The theoretical aspects of distributed systems will be studied via the course textbook, Marten van Steen and Andrew Tanenbaum, Distributed Systems 3rd edition, 2017. You can order a physical copy of this book, or register online to download a PDF, as you prefer.
Prerequisites
- CSE 20232 (Data Structures) and CSE 20289 (Systems Programming) or equivalent.
- Experience in the Python programming language.
Course Outcomes
Students successfully completing this course will be able to:Presented in course readings, evaluated in exams.
Presented in class discussions, evaluated in exams.
Presented in course readings, evaluated in exams.
Presented, practiced, and evaluated in the practical assignments.
Practiced in assignment writeups and final project talk.
Programming Assignments
Six programming assignments are required, due one-two weeks apart for the first half of the semester. The assignments together build towards an implementation of a scalable key-value store that could run in a cloud service or as a peer-to-peer system:- Measuring Fundamentals - Precisely measure the cost of fundamental operations in the system: function call, hash table read/write, network packet, file system I/O, process creation.
- Remote Procedure Call - Build a system in Python for performing remote procedure call between processes. Carefully measure the performance and throughput of this system with multiple clients.
- Persistence - Make the prior system persistent by implementing logging, recovery, and periodic log compression. Measure the performance of the system, observing outliers.
- Robustness - Improve the prior system by making it more discoverable by a name service, handle multiple clients simultaneously, and be more robust to a variety of unexpected conditions.
- Sharding - Improve the prior system by dividing up the storage space among multiple servers, allowing for multiple clients to be served simultaneously. Measure the performance and scalability.
- Caching and Consistency - Improve the performance of the prior system by implementing a caching layer that provides a non-trivial consistency model. Measure the performance under various workloads.
Final Project
In the final project, students will propose, build, and measure a distributed system of their own design, which must make use of multiple techniques discussed in class to achieve a system that is robust and performant. Examples might include a distributed filesystem, a parallel programming model, or a peer-to-peer data routing system. The final submission will include a project report describing the design of the system.Graduate Students
Graduate students taking CSE 60771 will dig deeper into the theory of distributed systems. A selection of paper readings will be assigned that address the course topics in greater detail, balanced between "classic" results in distributed systems and specific case studies in distributed systems design.How to Get the Most Out of Class
To succeed in the class, you should attend all class meetings, take notes, and participate in class discussions. During most class sessions, I'll give a prepared lecture for about 30 minutes, and then we will shift into Q&A or working on an example.
The textbook is dense in places; sometimes a key algorithm may only occupy two pages in the book, but requires 30 minutes of class discussion to work out all the details. So, it works best if you read the textbook for a broad understanding before class, and then go back and review details and work some examples afterward.
Because much of the class material involves working with system diagrams and examples, I will mostly work on the blackboard instead of presenting slide decks. I recommend that you take notes by sketching along with pen and paper: the simple act of note-taking exercises your mental muscles in a way that passive observation does not. If you prefer to take notes on your laptop or tablet, then that's fine too.
However, I do ask that you refrain from using your laptops or phones for non-class related tasks during class time. I know it is tempting during a brief lull to respond to messages, check the news, etc, but even one laptop open can be an unavoidable distraction for other people in the class. Please reserve this time for working together.
Communications
Assignments and the course schedule are available on the course website, and assignment grades will be posted in Sakai.
Regular classes will be recorded via Zoom/Panopto and made available by Sakai. You are welcome to make use of the recordings if you are out sick, attending an interview, or just want a refresher. However, the recordings are not a good substitute for participating in class.
We will be using (one of: Sakai/CampusWire/Slack) to handle general Q&A for the class. If you have a technical question that could be of interest to others, please post it there, so that others can benefit from the answers. You are welcome to post (or answer) questions anytime, and we will generally monitor and answer questions on weekday afternoons. (Keep in mind that we do go home at night, and so late-night questions will get answered the next day.) For questions about grades or anything else that just applies specifically to you, just email the instructor or TA directly.
Office hours are a great time to get focused help on a tricky bit of code. We are happy to help you during that time -- just knock, come in, and introduce yourself. If you can't make any of the office hours, then send email to see if we can work out another time.
Assignments and Grading
Programming assignments are generally due at 10PM on Wednesday nights. Because the programming assignments are cumulative, working up to a larger goal, it's important to stay on top of things and make progress every week -- don't leave the assignment until the last minute.Programming assignments will be submitted by copying files to a "dropbox" directory on the student machines. You are free to submit (or resubmit) anytime, so it would be a good idea to submit something (even if incomplete) well before the due date.
Writing assignments (project proposal, graduate readings, etc) will be submitted via the Sakai assignments feature.
Late assignments receive no credit, so submit your work on time. However, you may take one free "late pass" on one programming assignment over the course of the semester. This will allow you to turn in that assignment one week late. (However, the following assignment is still due at the normal time.) To do this, send an email to Prof. Thain prior to the due date, requesting a late pass.
Grades will be weighted as follows:
Category | Undergraduates | Graduates |
---|---|---|
Regular Assignments | 50% | 40% |
Paper Readings | - | 15% |
Course Project | 20% | 15% |
Midterm Exam | 15% | 15% |
Final Exam | 15% | 15% |
Health and Safety
At the time of writing, we expect that campus life and operations will be closer to the pre-pandemic normal. However, we are all still getting used to being in close quarters again. If you aren't comfortable doing something like shaking hands or sitting closely together, just express your preferences politely, and be understanding of others around you. You are welcome to wear a mask, but it is not required to do so at this time. Office hours will be held simultaneously in person and via Zoom, and you can attend in whatever mode you prefer. If the public health situation changes, then we will adapt to new rules as necessary.If you have a major health condition (or any other unforseen circumstance) that will prevent you from coming to class or completing the assignments, please contact Prof. Thain and we will discuss alternate arrangements on a case-by-case basis.
Academic Code of Honor
Programming assignments and exams are to be completed individually. The final project is to be completed in pairs or small groups.Students are encouraged to seek out and consult reference manuals, books, websites, and other documentation that will help you to complete each programming assignment, provided that you indicate what sources you have used. However, the result of such consultation should be an understanding of the material so that you can do it yourself. All software development, experimental work, and writing of results must be by your own hands, in your own words.
Notre Dame students are expected to abide by the Academic Code of Honor Pledge: "As a member of the Notre Dame community, I will not participate in or tolerate academic dishonesty."
Some Campus Resources
If you require an accommodation for a disability, please first contact the Sara Bea Center (sarabeadisabilityservices.nd.edu) for a consultation, and we will be happy to work together on a solution.If you encounter a difficult life situation and don't know what to do, the University Counseling Center (ucc.nd.edu) or the Care and Wellness Consultants (care.nd.edu) can help and also connect you with other campus resources.