| 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 Ring-Maintenance Protocol
Is Not Correct, Pamela Zave How to Make Chord Correct", Pamela Zave. |
| 2 | 8/28/2014 | Fault-tolerant 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 | Ben-Or's randomized exact consensus algorithm. Approximate consensus with crash failures in an asynchronous system. |
First 5 pages of The correctness proof of Ben-Or'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: message-passing. | Chapter 4 Mutex slides: set 3 pages 108-109 and Section 5.3.1 of textbook Slides for wait-free 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: message-passing, and shared memory (wait-free case). | Chapter 4 pages 108-109 and Section 5.3.1 of textbook Slides for wait-free 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: Happened-before, logical clocks, vector clocks, consistent cuts. | Chapter 6 | Slides by Prof. Welch: Causality |
| 13 | 10/7/2014 | Clarifications for the mid-term 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, partition-tolerant 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, partition-tolerant 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. Fault-tolerant 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 | Fault-tolerant simulation of read/write objects: multi-reader, single-writer, multi-reader, multi-writer, atomic snapshot object. | Chapter 10. | slides by Prof. Welch |
| 21 | 11/4/2014 | Atomic snapshot object. Wait-free hierarchy. | Chapter 10. Chapter 15 (up to and including Section 15.3.2). | Slides by Prof. Welch: ASO, wait-free |
| 22 | 11/6/2014 | No lecture today on account of take-home mid-term exam 2. |
This paper is NOT included for mid-term exam 2: Atomic Snapshots of Shared Memory, Afek et al., 1993. |
|
| 23 | 11/11/2014 | Universality. Problems solvable in asynchronous systems: K-set 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 Point-to-Point Links (except Section 5) |
slides |
| 26 | 11/20/2014 | Quiz 2 (in-class). Communication complexity of Byzantine broadcast |
paper on Byzanine agreement complexity Slides 47-73 of this talk |
|
| 27 | 12/2/2014 | Self-stabilization. | K-state machines (K>N) from Self-stabilizing 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 (in-class) |