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


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


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

15% Class Participation (scribe wanted!)

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. 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/18, 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.

BFT

Tanvi: 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 (Duke)

Noor: Reliable broadcast Asynchronous Byzantine Agreement Protocols

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

Nakamoto

Sanket: Off-chain solutions The Bitcoin Lightning Network

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

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

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: Recent partially synchronous BFT Casper the Friendly Finality Gadget

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

Peiyao: DAG-based BFT Hashgraph

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

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

Proof of stake The Sleepy Model of Consensus

Proof of stake Ouroboros: A Provably Secure Proof-of-Stake Blockchain Protocol

Jason: Avalanche