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.

Consensus Algorithm, Spring 2021

Additional Resources

Important papers

Time, Clocks, and the Ordering of Events in a Distributed System

Consensus in the Presence of Partial Synchrony

The Part-Time Parliament

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 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.

Some topics for literature study

Some sample papers for literature study: By.zantine quorum systems Asymmetric Distributed Trust Fast PBFT GHOST Sleepy Consensus Ouroboros Honey Badger Dumbo Aleph Avalanche Streamlet Sync HotStuff