Lecture  Date  Topics  Required Readings  Other information 
1  8/26/2014 

Chapters 1 and 2 of textbook Slides: Chapter 1, Chapter 2 
Why the Chord RingMaintenance Protocol
Is Not Correct, Pamela Zave How to Make Chord Correct", Pamela Zave. 
2  8/28/2014  Faulttolerant consensus. Crash fault tolerant consensus algorithm; f+1 round lower bound.  Chapter 5 of textbook Slides: Consensus, Byzantine consensus 

3  9/2/2014  f+1 round lower bound. Byzantine consensus. 3f+1 node lower bound. Exponential complexity (tree) algorithm.  Chapter 5 of textbook Slides: Consensus, Byzantine consensus 

4  9/4/2014  Exponential complexity (tree) algorithm. Phase King algorithm (Algorithm 16 in Chapter 5) with polynomial complexity.  Chapter 5 of textbook  
5  9/9/2014  Lewis Tseng discussed some exercises from the textbook  
6  9/11/2014  No class today  
7  9/16/2014  BenOr's randomized exact consensus algorithm. Approximate consensus with crash failures in an asynchronous system. 
First 5 pages of The correctness proof of BenOr's randomized consensus algorithm, Aguilera and Toueg, 2012.
Slides for approximate consensus with crashes and asynchrony. 

8  9/18/2014 
Approximate consensus with Byzantine failures in an asynchronous system. Shared memory mutual exclusion. 
Chapter 4 Mutex slides: set 1, set 2 

9  9/23/2014  Shared memory mutual exclusion.  Chapter 4 Mutex slides: set 2 set 3 Reading assignment: Byzantine Vector Consensus in Complete Graphs, Nitin Vaidya and Vijay Garg, ACM PODC, July 2013 

10  9/25/2014  Shared memory mutual exclusion. Impossibility of consensus in asynchronous systems in presence of crash failures: messagepassing.  Chapter 4 Mutex slides: set 3 pages 108109 and Section 5.3.1 of textbook Slides for waitfree impossibility Impossibility of distributed consensus with one faulty process, Fischer, Lynch, Paterson, JACM, 1985 
Slides for [FLP] from the web 
11  9/30/2014  Impossibility of consensus in asynchronous systems in presence of crash failures: messagepassing, and shared memory (waitfree case).  Chapter 4 pages 108109 and Section 5.3.1 of textbook Slides for waitfree impossibility Impossibility of distributed consensus with one faulty process, Fischer, Lynch, Paterson, JACM, 1985 
Slides for [FLP] from the web 
12  10/2/2014  Causality: Happenedbefore, logical clocks, vector clocks, consistent cuts.  Chapter 6  Slides by Prof. Welch: Causality 
13  10/7/2014  Clarifications for the midterm exam I.  
14  10/9/2014  Causality and time. Broadcast.  Chapter 6 Section 6 of Distributed Snapshots, Chandy and Lamport, 1985. 
Slides by Prof. Welch: Causality, Clocks 
15  10/14/2014  Broadcast. Distributed shared memory (DSM). 
Sections 8.1 and 8.2. Sections 9.1, 9.2 and 9.3 
Slides by Prof. Welch:
broadcast DSM 
16  10/16/2014  Distributed shared memory (DSM). 
Sections 9.1, 9.2 and 9.3
Discussion of causal consistency & weak consistency from Memory consistency models, Mosberger, 1993. Replicated Data Consistency Explained Through Baseball, Doug Terry, 2013. Brewer's conjecture and the feasibility of consistent, available, partitiontolerant web services, Gilbert and Lynch, 2002. 
Slides by Prof. Welch:
broadcast DSM 
17  10/21/2014  Distributed shared memory (DSM). 
Sections 9.1, 9.2 and 9.3
Discussion of causal consistency & weak consistency from Memory consistency models, Mosberger, 1993. Replicated Data Consistency Explained Through Baseball, Doug Terry, 2013. Brewer's conjecture and the feasibility of consistent, available, partitiontolerant web services, Gilbert and Lynch, 2002. 
Slides by Prof. Welch: DSM 
18  10/23/2014  Average consensus (using doubly stochastic and singly stochastic transition matrices). Full link reversal routing algorithm. 
Two average consensus algorithms
are described in Section II of paper by Benezit et al. First 8 pages of notes from Prof. Soma Choudhuri 
A nice paper on link reversal: Analysis of Link Reversal Routing Algorithms, Buschh and Tirthapura, 2005. 
19  10/28/2014  Full link reversal routing algorithm. Faulttolerant simulation of read/write objects. 
First 8 pages of notes from Prof. Soma Choudhuri Chapter 10. 
A nice paper on link reversal:
Analysis of Link Reversal Routing Algorithms, Buschh and Tirthapura, 2005. slides by Prof. Welch 
20  10/30/2014  Faulttolerant simulation of read/write objects: multireader, singlewriter, multireader, multiwriter, atomic snapshot object.  Chapter 10.  slides by Prof. Welch 
21  11/4/2014  Atomic snapshot object. Waitfree hierarchy.  Chapter 10. Chapter 15 (up to and including Section 15.3.2).  Slides by Prof. Welch: ASO, waitfree 
22  11/6/2014  No lecture today on account of takehome midterm exam 2. 
This paper is NOT included for midterm exam 2: Atomic Snapshots of Shared Memory, Afek et al., 1993. 

23  11/11/2014  Universality. Problems solvable in asynchronous systems: Kset consensus, approximate agreement 
Chapter 15 (up to and including Section 15.3.2).
Section 16.1 (except the lower bound proof) and Section 16.2 (except Section 16.2.2). Atomic Snapshots of Shared Memory, Afek et al., 1993. 

24  11/13/2014  Quiz 1. Herlihy's topological approach.  Slides by Herlihy (used in the class) If slides are inadequate, you may refer to the tutorial by Herlihy et al. (see the right column). 
Tutorial by Herlihy et al.
Lectures by Herlihy 
25  11/18/2014  Equality function computation. 
Multiparty Equality Function Computation in Networks with PointtoPoint Links (except Section 5) 
slides 
26  11/20/2014  Quiz 2 (inclass). Communication complexity of Byzantine broadcast 
paper on Byzanine agreement complexity Slides 4773 of this talk 

27  12/2/2014  Selfstabilization.  Kstate machines (K>N) from Selfstabilizing systems in spite of distributed control, Dijkstra, 1974. Become familiar with the notation used in this paper  any final exam question regarding this algorithm will use the notation from the paper.  slides 
28  12/4/2014  TOPICS COVERED TODAY ARE NOT INCLUDED FOR THE FINAL EXAM: leader election in rings, Byzantine clock synchronization, checkpointing and rollback recovery.  TOPICS COVERED TODAY ARE NOT INCLUDED FOR THE FINAL EXAM  
29  12/9/2014  Quiz 3 (inclass) 