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


15% Class Participation

35% Assignment (out 10/08, due 10/25)

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. Each student lecture/presentation will be 30 minutes.

Selection of lecture topics or project ideas is due 10/18, but you are encouraged to finalize your selection earlier to secure your preferred topic. If two students are interested in the same lecture/project, teamwork will be encouraged if the topic/project indeed involves twice the work.

Candidate topics for student lectures and projects

(2) indicates that two 30-minutes lecture slots are available on the topic.


Fault bound proof Easy impossibility proofs for distributed consensus problems

Fast track of BFT (2) Revisiting Fast Practical Byzantine Fault Tolerance SBFT: a Scalable and Decentralized Trust Infrastructure

Consensus on large values Optimal Extension Protocols for Byzantine Broadcast and Agreement

Reliable broadcast Asynchronous Byzantine Agreement Protocols

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

Recent partially synchronous BFT Casper the Friendly Finality Gadget

Recent asynchronous BFT The Honey Badger of BFT Protocols

Byzantine quorum systems (2) Byzantine quorum systems Asymmetric Distributed Trust

Evaluate recent alternative proposals (2) Hashgraph Avalanche


Off-chain solutions The Bitcoin Lightning Network

Selfish mining (2) Majority is not Enough: Bitcoin Mining is Vulnerable Stubborn Mining

Scalability On the Security and Performance of Proof of Work Blockchains On scaling decentralized blockchains

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

Variants (2) Accelerating Bitcoin's Transaction Processing Scaling nakamoto consensus to thousands of transactions per second

Deterministic longest chain Analysis of Deterministic Longest-Chain Protocols

Proof of stake designs (2) The Sleepy Model of Consensus Ouroboros: A Provably Secure Proof-of-Stake Blockchain Protocol