CS 260: Seminar in Distributed Computing


      
CS 260: Distributed Computing
Instructor: Prof. Mohsen Lesani
Schedule: MWF 3:10-4pm, Life Sciences 2418
Prerequisites: CS 014, CS 100

--------------------------------------------------------------
Description:

Have your ever wondered how blockchain nodes agree on the state and sequence of transactions?

This course will introduce fundamental distributed programming algorithms. We follow a step-by-step layered approach; we incrementally implement more sophisticated abstractions based on simpler abstractions. We will consider processes that are subject to crashes and also malicious attacks by non-cooperating processes. Resilience to these attacks has become widely known as Byzantine fault-tolerance. The course will cover reliable broadcast, causal broadcast, total-order broadcast, consensus and agreement including blockchain consensus, atomic commit and terminating reliable broadcast, distributed shared memory, replicated systems and Byzantine fault tolerance. Students will read and present research papers, and participate in class discussions, or complete a project.

--------------------------------------------------------------
Textbook:

Introduction to Reliable and Secure Distributed Programming. 2011. C. Cachin, R. Guerraoui, L. Rodrigues
Book page

--------------------------------------------------------------
Papers:
----------------
April 26
How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs
Leslie Lamport 1979
Linearizability: A Correctness Condition for Concurrent Objects
Maurice P. Herlihy and Jeannette M. Wing
TOPLAS 1990

----------------
April 29
Brewer’s Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services
Seth Gilbert and Nancy Lynch 2002
Perspectives on the CAP Theorem
Gilbert and Lynch. 2012

----------------
May 3
Principles of Eventual Consistency.
2014. S. Burckhardt.

----------------
May 6
Hamsaz: Replication Coordination Analysis and Synthesis
F. Houshmand, M. Lesani
POPL 2019

----------------
May 10
Conflict-free Replicated Data Types
Marc Shapiro et al., 2011
A comprehensive study of Convergent and Commutative Replicated Data Types
Marc Shapiro et al., 2011

----------------
May 13
Declarative Programming over Eventually Consistent Data Stores
KC Sivaramakrishnan, Gowtham Kaki, and Suresh Jagannathan
PLDI ‘15

----------------
May 17
Consistency Analysis in Bloom: a CALM and Collected Approach
Peter Alvaro et al.,
CIDR ‘11
Logic and Lattices for Distributed Programming
Neil Conway et al.
SoCC ‘15

----------------
May 20
MixT: a Language for Mixing Consistency in Geodistributed Transactions
Matthew Milano and Andrew C. Myers
PLDI ‘18
   
----------------
May 24
Bitcoin A Peer-to-Peer Electronic Cash System.
Nakamoto 2008

----------------
May 29
Atomic Cross-Chain Swaps.
Maurice Herlihy
PODC 2018

--------------------------------------------------------------
Evaluation:

    Participation and discussion: 20%
    Presentation: 30%
    Reviews: 20%
    Project: 30%