CS 854: Consensus Protocols

Information

Instructor: Bernard Wong
Email: bernard@uwaterloo.ca
Time: Every Friday at 3:00-5:50 Fall 2016
Location: DC 2568
URL : http://www.cs.uwaterloo.ca/~bernard/courses/cs854-F16

Description

Achieving consensus among a set of entities is a fundamental problem for many distributed systems. In these systems, different entities may propose conflicting values, but all of them must agree on a single one. This can be challenging due to unexpected system and network failures.

CS854 is a graduate course on both past and current research in consensus protocols. It is offered as a "paper-chase" course: we read and discuss important papers on different subtopics each week. Students must also complete a programming assignment (implementing Raft), and a final project that explores a new idea in one of the sub-topics covered in the course. The goal is that by the end of the course, the final project can serve as a starting point for a workshop paper submission.

Grading

The following is the tentative course grades breakdown.

Paper Reviews

Before each class, each student must submit a review for the non-optional papers to be discussed that day. A review should include a paragraph summarizing the core contributions of the paper, and a second paragraph that identifies weaknesses in the paper and areas in which the paper can be expanded upon.

Please inform me via email the circumstances for each late or missed submission.

Paper Presentations

Each student is expected to present the papers to be discussed in class for at least one class. The paper presentations should follow the same format as a conference talk. The presenter should be prepared with sufficient background knowledge of the related work in the area to answer broad questions and lead the class discussion.

Presenters: Please send me a copy of your slides at least two days before your presentation. I will provide feedback on the slides the next day. Do not just re-use slides provided by the paper authors. You may borrow, with attribution, figures and animations, but your slides should be created independently.

Reading

Date Presenter Topic
9/9 Bernard Introduction: General course description

The Part-Time Parliament

Paxos Made Simple

Impossibility of Distributed Consensus with One Faulty

9/16 Bernard Background

Paxos Made Moderately Complex

In Search of an Understandable Consensus Algorithm

(Optional) Viewstamped Replication Revisited

9/23 Xinan, Sharon Coordination and Lock Services

The Chubby lock service for loosely-coupled distributed systems

ZooKeeper: Wait-free coordination for Internet-scale systems

(Optional) Zab: High-performance broadcast for primary-backup systems

9/30 Stephen, Sajjad, and Bernard Cheap, Fast and Ring Paxos

Cheap Paxos

Fast Paxos

(Optional) Ring Paxos

10/7 Milad, and Group Discussion Scalable Consensus

Mencius: Building Efficient Replicated State Machines for WANs

There Is More Consensus in Egalitarian Parliaments

10/14 Everyone No class due to fall break

10/21 Everyone Assignment Demo

10/28 Babar, Chathura, and Murray Byzantine Fault Tolerance

The Byzantine Generals Problem

Practical Byzantine Fault Tolerance

(Optional) Zyzzyva: Speculative Byzantine Fault Tolerance

11/4 Linguan, Siddhartha, and Shayan More Paxos and DARE

Consensus on Transaction Commit

Paxos Made Transparent

(Optional) DARE: High-Performance State Machine Replication on RDMA Networks

11/11 Harsimran, Ben Armstrong, and Siavash Blockchains (Nakamoto Consensus)

Bitcoin: A Peer-to-Peer Electronic Cash System

Bitcoin-NG: A Scalable Blockchain Protocol

(Optional) Anonymous Byzantine Consensus from Moderately-Hard Puzzles: A Model for Bitcoin

11/18 Haibo, Elaheh, and Sepehr Consensus in hardware

NetPaxos: Consensus at Network Speed

Consensus in a Box: Inexpensive Coordination in Hardware

(Optional) Just Say NO to Paxos Overhead: Replacing Consensus with Network Ordering

11/25 Everyone Project Presentations

Last modified: Aug 15, 2016