Consensus Algorithms

Instructor: Ling Ren

Lectures: Tue/Thu 12:30 PM - 01:45 PM, 1214 Siebel Center

Office hours: Wed 2 PM - 3 PM or by appointment, 4312 Siebel Center

This course covers classic results and recent advances in consensus algorithms: state-of-art algorithms and bounds under different problem formulations, assumptions and paradigms.

CS598LR Consensus Algorithms Fall 2019 Schedule

Student presentations and notes (Illinois login required)

Additional Resources

Important papers that are not covered

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

Consensus in the Presence of Partial Synchrony

The Part-Time Parliament

Another advantage of free choice

Random Oracles in Constantinople


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


15% Class Participation (scribe wanted!)

35% Assignment (out 10/08, due 10/25) (Updated: broken up into three parts. See schedule.)

50% Lecture/presentation

Each student can choose between giving a lecture or completing a final project. For lectures, you can choose a topic from the list provided below; you will be required to read one or two papers on the topic, explain them to the class and share your lecture note. For projects, you are expected to come up with your own project idea; you will be required to present your result in class and submit a written report. Engineering projects are perfectly fine as long as they are related to course contents.

Certain lecture topics accommodate teams of two. A team of two project is encouraged if it indeed involves twice the work. Each individual presentation will be 25 minutes. Each team presentation will be 40 minutes. (Note the shortened time due to increased enrollment.) You should factor in the time for audience interruption. Selection of lecture topics or project ideas is due 10/08, but you are encouraged to finalize your pick earlier. Scribe/lecturer slots are first-come first-serve.

Candidate topics for student lectures

(2) indicates that a team of two is encouraged.


Tanvi: Fault bound proof Easy impossibility proofs for distributed consensus problems

Duke: Fast-track BFT Revisiting Fast Practical Byzantine Fault Tolerance SBFT: a Scalable and Decentralized Trust Infrastructure

Noor: Reliable broadcast Asynchronous Byzantine Agreement Protocols

Rahul/Dan: Byzantine quorum systems (2) Byzantine quorum systems Asymmetric Distributed Trust


Sanket: Off-chain solutions The Bitcoin Lightning Network

Federico/Rui: Selfish mining Majority is not Enough: Bitcoin Mining is Vulnerable Stubborn Mining

Faria: Rationality The Miner's Dilemma On the instability of bitcoin without the block reward

Linyi: Deterministic longest chain Analysis of Deterministic Longest-Chain Protocols

Evaluate recent new proposals (team of two can be accommodated for each paper below)

Chen/Zhengyang: Recent synchronous BFT Sync HotStuff: Simple and Practical Synchronous State Machine Replication

Kinith/Surya: Recent partially synchronous BFT Casper the Friendly Finality Gadget HotStuff: BFT Consensus in the Lens of Blockchain

Andrew/Amit: Recent asynchronous BFT The Honey Badger of BFT Protocols

Peiyao: DAG-based BFT Hashgraph (Aleph)

Siheng/Luke: Tree-based Nakamoto Accelerating Bitcoin's Transaction Processing

Gerui: DAG-based Nakamoto Scaling nakamoto consensus to thousands of transactions per second

Hung/Ranvir/Haris: Proof of stake The Sleepy Model of Consensus Ouroboros: A Provably Secure Proof-of-Stake Blockchain Protocol

Jason/Iris: Avalanche