Consensus Algorithms
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.
Additional Resources
Important papers
Time, Clocks, and the Ordering of Events in a Distributed System
Consensus in the Presence of Partial Synchrony
Random Oracles in Constantinople
The State Machine Approach: A Tutorial
Textbooks
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
Grading
10% Class participation
40% Homework
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 19 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.
Some topics for literature study
Some sample papers for literature study: Byzantine quorum systems Asymmetric Distributed Trust Fast PBFT GHOST Sleepy Consensus Ouroboros Honey Badger Dumbo Aleph HotStuff Sync HotStuff Avalanche Streamlet