Instructor: Ling Ren
Lectures: Wed/Fri 9:30 AM - 10:45 AM, Zoom meeting 812 9513 8525
Office hours: Wed 10:45 AM - 11:30 AM or by appointment, Zoom meeting 812 9513 8525
(The Zoom meeting password will be announced over emails. If you would like to attend the lectures without enrolling officially, you are welcome and please email me.)
This course covers classic results and recent advances in consensus algorithms. The course studies different problem formulations of consensus including Byzantine agreement, broadcast primitives and state machine replication (a.k.a, blockchains); different models and assumptions regarding timing, fault pattern, cryptography, and setup; state-of-art algorithms and lower bounds under various combinations of settings; common algorithm design techniques including randomization, leader-based approach, and quorum systems; Nakamoto’s new permissionless model, longest-chain paradigm, the Bitcoin protocol, its mathematical analysis, proposals to improve Nakamoto consensus; longest-chain protocols with other resources or stake, and their connection to classic consensus algorithms; and recent advances in consensus algorithms inspired by Nakamoto's paradigm.
Distributed Computing: Fundamentals, Simulations, and Advanced Topics 2nd Edition by Hagit Attiya and Jennifer Welch
Introduction to Reliable and Secure Distributed Programming 2nd Edition by Christian Cachin, Rachid Guerraoui and Luís Rodrigues
Distributed Algorithms by Nancy Lynch
10% Class participation
50% Project (35% presentation + 15% final report)
Each student will complete a semester-long research project. You are expected to come up with and finalize your project topic by February 26 and you are encouraged to discuss project ideas with me early in the semester. Project topics from your own research or engineering projects are encouraged as long as they are related to course contents. Alternatively, you can choose to do a literature study project, which involves reading two to three papers on a topic and evaluating them. You can team up with a partner but a group project is expected to involve twice the work. You will present your results or findings in class (expect 30 to 45 minutes) and submit a written report towards the end of the semester.