We will study some of the key building blocks – such as synchronization primitives, group communication protocols, and replication techniques – that form the foundation of modern distributed systems, such as cloud-computing platforms or the Internet. We will also look at some real-world examples of distributed systems, such as GFS, MapReduce, Spark, and Dynamo, and we will gain some hands-on experience with building and running distributed systems.
CIS 5050 is one of the core courses in the MSE program, as well as an option for the course requirements for PhD students.
Instructor:
Linh Thi Xuan Phan
Office hours: Mondays 12pm-1pm (Levine 576)
When and where:
Mondays/Wednesday 10:15-11:45am,
Towne 100
Teaching assistants and office hours:
| Ryan Morris (Head TA) | OH: TBA |
| Amanda Guan | OH: Mondays 12:00-2:00pm (Levine 501) |
| Grace Deng | OH: Tuesday (on 09/01) 4:00-6:00pm (Zoom) |
| Kota Yamamoto | OH: Tuesdays 11:00am-1:00pm (Levine 601) |
| Tiffany Chang | OH: Thursdays 4:45-6:45pm (Levine GRW 5th bump space) |
| Rayhan Faizel | OH: Fridays 10:30am-12:30pm (Levine 501) |
| Henry Xu | OH: Saturdays 1:00-3:00pm (OHQ) |
| Xian Wang | OH: TBA |
Course textbook:
Distributed Systems: Principles and Paradigms, 4th edition (by M. van Steen and A. Tanenbaum).
You can get a digital version of this
book for free; hardcopies of the previous version of the book are available, e.g., from Amazon. Additional material will be drawn from selected
research publications.
Prerequisites:
The course requires undergraduate-level operating systems and networking knowledge, such as CIS 4480 (formerly CIS 3800) and NETS 2120 (or CIS
5530) or the equivalence. You must also be proficient in C or C++ programming.
Workload:
The course will involve three substantial programming assignments, a group project, and two midterms.
Both the programming assignments and the project involve a considerable amount of programming in C/C++, and
the project requires the ability to work with your classmates in teams.
Grading:
Your letter grade will be based on the individual programming assignments (20%), the group project (35%), the
two midterm exams (40%), and participation (5%).
Attendance and other policies:
Class attendance is mandatory and will count towards your participation score. More details on attendance and
key course policies can be found here.
We will be using Ed Discussion for all course-related discussions.
Homework assignments and project are available for download from the assignments page. You can submit your solutions online via GradeScope.
| Date | Topic | Details | Reading | Remarks |
|---|---|---|---|---|
| Aug 26 | Introduction | Course overview Policies |
Chapter 1 | HW0 released |
| Aug 31 | Processes and threads | Basic concepts The UNIX model Implementation in the kernel Parallelization Scheduling |
Chapter 3.1 (Sections 1+2) | HW0 due; HW1 released |
| Sep 2 | Concurrency control (See next class slides) |
Race conditions, mutual exclusion Synchronization primitives Semaphores Deadlock and starvation |
||
| Sep 7 | Labor Day (No class) | |||
| Sep 9 | Synchronization |
Semaphores Classical synchronization problems Monitors and condition variables |
[Hoare monitors] [Mesa monitors] |
HW1 due (on 9/10) |
| Sep 14 | Communication | Sockets Socket programming Handling multiple connections |
Chapters 4.1+4.3 | HW2 released |
| Sep 16+21 | Remote Procedure Calls |
Programming model Stub code; marshalling; binding Handling failures |
Chapters 4.2+8.3 | HW2MS1 due (on 9/21) |
| Sep 23 | Naming | Kinds of names; name spaces The Domain Name System; Akamai; DNSSEC |
Chapter 6 | |
| Sep 28 | Clock synchronization |
Logical clocks NTP and Berkeley algorithms Lamport and vector clocks |
Chapters 5.1+5.2 | |
| Sep 30 | Group communication |
Reliable multicast IP multicast FIFO, causal and total ordering |
Chapter 8.4 |
HW2MS2+3 due HW3 released |
| Oct 1-4 | Fall break | |||
| Oct 5+7 | Replication | Primary/backup protocols Quorum protocols Sequential and causal consistency Client-centric models |
Chapter 7 | HW3 due (10/9) Project released |
| Oct 12 | Bigtable and Project | Bigtable case study Project overview |
[Bigtable] | |
| Oct 14 | First midterm exam | |||
| Oct 19+21 | Fault tolerance |
2PC and 3PC Logging and recovery Chandy-Lamport algorithm |
Chapters 8.5+8.6; | |
| Oct 26 | State-machine replication |
Failure models The Consensus problem Paxos |
Chapters 8.1+8.2; [Paxos] | |
| Oct 28 + Nov 2 | Non-crash Fault Tolerance |
The Byzantine Generals problem Impossibility results Solutions |
[BFT] | |
| Nov 4 | Distributed file systems | NFS Coda Disconnected operation |
Chapter 2.3.3; [Coda] | Nov 9 | Google File System |
Google cluster architecture Reading and writing in GFS Consistency and fault tolerance |
[Cluster] [GFS] |
| Nov 11 | MapReduce |
MapReduce programming model System architecture |
[MapReduce] | |
| April 16 | Spark | Differences to MapReduce RDDs Case study: PageRank |
[RDD] [Spark] | |
| Nov 18+23 | DHTs and Dynamo | Distributed hash tables The CAP dilemma Amazon Dynamo |
[Dynamo] | |
| Nov 25 | Friday schedule (No class) | |||
| Nov 26-29 | Thanksgiving break | |||
| Nov 30 + Dec 2 | Security | Threat models Cryptography Digital signatures Hash functions OWASP Top 10 |
Chapter 9 | |
| Dec 7 | Second midterm exam | |||
| Dec 8-9 | Reading days | |||
| Dec 10-17 | Project demos and reports | |||