Distribution is ubiquitous in modern computing systems. For example, today’s telephone systems, banking systems, global information systems, and aircraft and nuclear power plant control systems all depend critically on distributed algorithms. Robust distributed algorithms should offer reliability and security despite process failures, network disconnections, or even malicious attacks on processes. This course will introduce fundamental distributed computing problems and provides a collection of applicable algorithms. It also presents formal specification and rigorous reasoning about distributed algorithms. The course follows a modular and layered approach to the implementation of distributed abstractions. It covers reliable broadcast, causal broadcast, total-order broadcast, distributed shared memory, consensus variants including blockchain consensus, atomic commit and terminating reliable broadcast, and replicated systems. The course considers processes that are subject to crashes and also malicious attacks by non-cooperating processes.
In this course, we will have both lectures by the instructor, and presentations by students. The presenter presents a paper or related papers and leads the discussion.
Textbook:
Introduction to Reliable and Secure Distributed Programming
Christian Cachin, Rachid Guerraoui, Luís Rodrigues
Second Edition, Springer, 2011, XIX, 320 pages, ISBN-13: 978-3-642-15259-7
Hamsaz: Replication Coordination Analysis and Synthesis
Farzin Houshmand, Mohsen Lesani
POPL ’19 (ACM SIGPLAN Symposium on Principles of Programming Languages)
Hambazi: Spatial Coordination Synthesis for Augmented Reality
Yi-Zhen Tsai, Jiasi Chen, Mohsen Lesani
OOPSLA ’25 (ACM SIGPLAN conference on Object-oriented Programming, Systems, Languages, and Applications)
Hamraz: Resilient Partitioning and Replication
Xiao Li, Farzin Houshmand, Mohsen Lesani
S&P ’22 (IEEE Symposium on Security and Privacy)
Deconstructing Stellar Consensus.
A. G. Perez, M. A. Schett
OPODIS 2019.
Atomic cross-chain swaps
Maurice Herlihy
PODC 2018 (ACM symposium on principles of distributed computing. 2018)
Evaluation
We post the assignments on Canvas and you submit your solutions on Gradescope.
Four Assignments: 10% each
Written Assignment 1: Release: April 8, Submission: April 15
Written Assignment 2: Release: April 29, Submission: May 6
Programming Assignment: Release: May 6, Submission: May 29
Written Assignment 3: Release: May 27, Submission: June 3
Midterm Exam: 30%
May 20 in the class
Presentation and discussion: extra credit
Four presentations in the last week, June 3 and 5
Final Exam: 30%
Finals week, June 11, 4-7pm, in the class
We keep track of attendance, and only those that attend regularly will get their grades scaled.
Academic Integrity
One of the joys of university life is socializing and working with your classmates. We want you to make friends with each other and discuss the material. That said, I expect all assignments (code, write-ups, and tests) to be your own original work. If you work together with a classmate on an assignment, please mention this, e.g. in the comments of your code. If you use a figure you didn’t create in a write-up, then it needs a citation. Please review the university’s policy on plagiarism. This class has a zero-tolerance policy on cheating. Please don’t do it.
As a final note on cheating: the economic condition facing computer science graduates is volatile in the near future. It is crucial that you benefit from your time at the university, and learn the concepts thoroughly. If you cheat, you will not be able to stand out from others who put in the effort when it comes time to find a job. Cheating will have a devastating impact on your own career opportunities. Just don’t do it.
We are in an exciting time for AI, especially for tools like Github co-pilot and LLMs (e.g., ChatGPT). These tools have incredible potential and they are improving every day. However, the educational community has not had sufficient time to understand their impact on learning objectives. This class has been designed to be taken without the use of AI tools. They are not allowed to be used in the course. If we suspect abuse, then we may implement random audits of assignments, where you will be asked to explain your implementation in detail. If you are interested in seeing how these tools can help, please feel free to use them after you have submitted a non-AI version of the homework.
