| Instructor: | Zizhan Zheng (zzheng3@tulane.edu), Stanley Thomas 307B |
| Class Time & Place: | TR 2:05-3:15pm, Stanley Thomas 302 |
| Office Hours: | W 2-3pm and by appointment |
This course covers the fundamental concepts in distributed computing at the graduate level. The objective is to introduce students to the core notions, techniques, and algorithms in the design of distributed systems when there is no global clock and when unpredictable failures and variable latency are the norms. Recent developments in the Internet, cloud computing, and blockchain, etc. will be used as case studies to help students establish a firm understanding of the philosophy and pitfalls in achieving reliable and efficient distributed computing. Topics to be covered include interprocess communication, time and clocks, mutual exclusion, group communication, consensus, decentralized optimization, transactions, and security.
We will meet both in person and online (about 40% of lectures will be online). A detailed class schedule can be found on the course webpage. The tentative plan for January and February is to meet in person on Tuesdays and meet online on Thursdays.
There will be both written problem assignments and labs (programming assignments). Graduate level students will be given extra questions that require advanced algorithmic/analytic techniques. Specific instructions will be given in each assignment.
Each student will present one or two papers from the suggested paper list or chosen by the student (please confirm with me). Two undergraduate students can present together while each graduate student should give a presentation independently. For each presentation, all the students (other than the presenter) are expected to give feedback to the presenter.
There will be a midterm and a final exam. Both will be online, open-book and open-notes.
Each student has a total of 6 grace days that may be applied to the homework assignments. No more than 2 grace days may be used on any single assignment. Any assignment submitted more than 2 days past the deadline (or the date the student no longer has late day credit) will get zero credit. No late days are allowed for the presentation and exams.
Faculty and students must comply with University policies on COVID-19 testing and isolation, which are located here[https://tulane.edu/covid-19/health-strategies]. Faculty and students must wear face coverings in all common areas, including classrooms, and follow social distancing rules. Failure to comply is a violation of the Code of Student Conduct and students will be subject to University discipline, which can include suspension or permanent dismissal.
If a student cannot attend class for any reason, the student is responsible for communicating with their instructor to make up any work they may miss. Faculty will provide online options for class participation, outlined in this document, and unless a student is seriously ill, they are expected to use this option. The University Health Center will provide documentation verifying a student is ill, as well as verification that a student may return to class. With the approval of the Newcomb-Tulane College dean, an instructor may have a student who has excessive absences involuntarily withdrawn from a course with a WF grade after written warning at any time during the semester.
The weighted average will determine your final letter grade as follows:
All grades will be posted on Canvas. As a reminder to undergraduate
students, the S/U option may not be used to satisfy the writing, foreign
language, quantitative or formal reasoning, and laboratory components of
the NTC Core Curriculum, nor may it be used to satisfy major or minor
requirements. Details of the policy can be found here: https://registrar.tulane.edu/2020-21-covid-19-grading-policy.
Students are encouraged to consult with their Newcomb Tulane College
academic advisor if they have any questions.
| Lecture | Date | Topic | Lecture Topic | Reading | Assignments |
| 1 | Jan 19 (Tu) |
Background |
Course
Overview. Characterization of Distributed Systems |
Chapter 1 | |
| 2 | Jan 21 (Th) | System Models [intro.pdf] Networking |
Chapters 2-3 | ||
| 3 | Jan 26 (Tu) | Networking | Chapter 3 | ||
| 4 | Jan 28 (Th) | Socket programming. IP multicast, RPC | Chapters 4-5 | ||
| 5 | Feb 2 (Tu) | RPC and RMI [ipc.pdf] | Chapter 5, "Hello World" with Java RMI |
Lab 1: Java RMI (due Feb 11 before class) | |
| 6 | Feb 4 (Th) | Time and Global State | Physical clock synchronization | Sections 14.1-14.3 | |
| 7 | Feb 9 (Tu) | Logical and vector clocks | Section 14.4 | ||
| 8 | Feb 11 (Th) | Vector clocks and global state | Sections 14.4-14.5 |
Homework 1 (due Feb 25 before class) | |
| Feb 16 (Tu) | Lagniappe Day - Mardi Gras Holiday | ||||
| 9 | Feb 18 (Th) | Snapshot algorithm | Section 14.5 | ||
| 10 | Feb 23 (Tu) | Coordination | Snapshot algorithm [clock.pdf];
Distributed mutual exclusion |
Sections 14.5, 15.2 | |
| 11 | Feb 25 (Th) | Distributed mutual exclusion | Section 15.2 | ||
| 12 | Mar 2 (Tu) | Distributed mutual exclusion [dme.pdf]; Leader election | Section 15.3 | Homework 2 (due Mar 11 before class) | |
| 13 | Mar 4 (Th) | Leader election [le.pdf] | Section 15.3 | ||
| 14 |
Mar 9 (Tu) | Group communication | Sections 6.2 | ||
| 16 |
Mar 11 (Th) | Midterm review [midterm-review.pdf];
Group communication |
Sections 6.2, Section 15.4 | ||
| 15 | Mar 16 (Tu) | Midterm Exam: Mar 16 (Tu) 2:05-3:15 pm | |||
| 17 |
Mar 18 (Th) | Group communication | Section 15.4 | Lab
2: Group Communication (due Apr
1 before class) |
|
| 18 |
Mar 23 (Tu) | View-synchronous group communication [group.pdf] | Section 18.2 | ||
| 19 | Mar 25 (Th) | Consensus |
Consensus in
synchronous systems. Byzantine generals problem |
Sections 15.5.1-15.5.3, L. Lamport, R. Shostak, M. Pease "The Byzantine Generals Problem". |
|
| 20 | Mar 30 (Tu) | Consensus in asynchronous systems: FLP impossibility result | Section 15.5.3, M. J. Fischer, N. A. Lynch, and M. S. Paterson, "Impossibility of Distributed Consensus with One Faulty Process" |
||
| 21 |
Apr 1 (Th) | FLP impossibility
result. Paxos protocol [consensus.pdf] |
Section 21.5.2 | Presentation paper selection due | |
| 22 |
Apr 6 (Tu) | Intro to Blockchain | Chapters
1 and 2 in A. Narayanan, et al., "Bitcoin and Cryptocurrency Technologies", |
Homework 3 (due Apr 15 before class) | |
| Apr 8 (Th) | Lagniappe
Day |
||||
| 23 |
Apr 13 (Tu) | Intro to Blockchain [blockchain.pdf] | Elaine Shi, "Foundations of Distributed Consensus and Blockchains" | ||
| 24 |
Apr 15 (Th) | Transactions and Concurrency Control | Transactions |
|
|
| 25 |
Apr 20 (Tu) | Concurrency control |
|
Homework 4 (due Apr 29 before class) | |
| 26 |
Apr 22 (Th) | Student Presentation | Concurrency control [transaction.pdf] |
||
| 27 |
Apr 27 (Tu) |
|
|
||
| 28 |
Apr 29 (Th) | Final
Review [final-review.pdf] Solution to Homework 4 [pdf] |
|
||
| Final Exam: May 10 (Mon) 4-6pm | |||||
This course will follow Tulane's Code of Academic Conduct. Cheating will be reported to the Associate Dean of Newcomb-Tulane College. Discussion is encouraged. However, what you turn in must be your own. You may not read another classmate’s solutions or copy a solution from the web.
Tulane University recognizes the inherent dignity of all individuals and promotes respect for all people. As such, Tulane is committed to providing an environment free of all forms of discrimination including sexual and gender-based discrimination, harassment, and violence like sexual assault, intimate partner violence, and stalking. If you (or someone you know) has experienced or is experiencing these types of behaviors, know that you are not alone. Resources and support are available: you can learn more at titleix.tulane.edu. Any and all of your communications on these matters will be treated as either “Confidential” or “Private” as explained in the chart below. Please know that if you choose to confide in me I am mandated by the university to report to the Title IX Coordinator, as Tulane and I want to be sure you are connected with all the support the university can offer. You do not need to respond to outreach from the university if you do not want. You can also make a report yourself, including an anonymous report, through the form at tulane.edu/concerns.
| Confidential | Private |
| Except in extreme circumstances, involving imminent danger to one’s self or others, nothing will be shared without your explicit permission. | Conversations are kept as confidential as possible, but information is shared with key staff members so the University can offer resources and accommodations and take action if necessary for safety reasons. |
| Counseling and Psychological Services (CAPS) | (504) 314-2277 or The Line (24/7) | (504) 264-6074 | Case Management and Victim Support Services | (504) 314-2160 or srss@tulane.edu |
| Student Health Center | (504) 865-5255 | Tulane University Police (TUPD) | Uptown - (504) 865-5911. Downtown – (504) 988-5531 |
| Sexual Aggression Peer Hotline and Education (SAPHE) | (504) 654-9543 | Title IX Coordinator | (504) 865-5615 or titleix@tulane.edu |