| Lecture | Date | Topics | Required Readings | Other information |
| 1 | 8/24/2015 |
|
Chapters 1 and 5 of textbook Slides: Chapter 1, Consensus |
Why the Chord Ring-Maintenance Protocol
Is Not Correct, Pamela Zave How to Make Chord Correct", Pamela Zave. |
| 2 | 8/24/2015 | Crash and Byzantine fault-tolerant consensus. | Chapter 5 Slides: Consensus, Byzantine consensus |
|
| 3 | 8/31/2015 | Crash and Byzantine fault-tolerant consensus. | Chapter 5 Sections 1, 2 and 3 of The Byzantine Generals Problems, Lamport, Shostak and Pease, 1982. Slides: Consensus, Byzantine consensus |
|
| 4 | 9/2/2015 | Crash and Byzantine fault-tolerant consensus. | Chapter 5 Sections 1, 2 and 3 of The Byzantine Generals Problems, Lamport, Shostak and Pease, 1982. Slides: Consensus, Byzantine consensus |
|
| 5 | 9/9/2015 | Lecture cancelled. | ||
| 6 | 9/14/2015 | Causality: Happened-before, logical clocks, vector clocks. | Chapter 6 | Causality, Clocks |
| 7 | 9/16/2015 | Causality: Consistent cuts. Clock synchronization. | Chapter 6 | Causality, Clocks |
| 8 | 9/21/2015 | Distributed shared memory. | Sections 9.1, 9.2, 9.3 |
Slides: DSM, fault-tolerant simulations, |
| 9 | 9/23/2015 | Fault-tolerant simulation of read/write objects: multi-reader, single-writer, multi-reader, multi-writer, atomic snapshot object. | Chapter 10 | Slides: DSM, fault-tolerant simulations, |
| 10 | 9/28/2015 | Fault-tolerant simulation of read/write objects: multi-reader, single-writer, multi-reader, multi-writer, atomic snapshot object. | Chapter 10 | Slides: DSM, fault-tolerant simulations |
| 11 | 9/30/2015 |
Fault-tolerant simulation of read/write objects: multi-reader, multi-writer, atomic snapshot object. Mutual exclusion in shared memory systems |
Chapter 10 Pseudo-code for Mutex algorithms from Chapter 4 |
Slides: DSM,
fault-tolerant simulations Mutex slides 1, Mutex slides 2 |
| 12 | 10/5/2015 | Impossibility of consensus in asynchronous systems with faults. Topological approach. |
Impossibility of distributed consensus with one faulty process, Fischer, Lynch, Paterson, JACM, 1985 Examples from slide set 1 and set 2 |
slides for FLP from the web |
| 13 | 10/7/2015 | Topological approach. | Computability in Distributed Computing: a Tutorial, Examples from slide set 1 and set 2 | |
| 14 | 10/12/2015 | Wait-free hierarchy | Chapter 15 (up to and including Section 15.3.2). | slides |
| 15 | 10/14/2015 |
Wait-free hieararchy. Iterative consensus |
Readings on iterative consensus to be posted | |
| 16 | 10/19/2015 | Mid-term exam (take-home). Only a short lecture. | ||
| 17 | 10/21/2015 | Iterative consensus. | ||
| 18 | 10/26/2015 | Iterative consensus. |
|
slides |
| 19 | 10/28/2015 | Iterative Byzantine consensus. Vector consensus. | See readings above. | |
| 20 | 11/2/2015 | Communication complexity of equality function computation (algorithm for 3-party equality). | Sections 1,2,3,6 of Multiparty Equality Function Computation in Networks with Point-to-Point Links | |
| 21 | 11/4/2015 | Induced matchings. Communication-efficient Byzantnie broadcast. |
Sections 1, 2 and 6 of
Nearly complete graphs decomposable into
large induced matchings and their applications Sections 1 through 5 of Complexity of Multi-Value Byzantine Agreement |
|
| 22 | 11/9/2015 | Reliable broadcast. Asynchronous Byzantine consensus. |
Section 2.1 of Multidimensional Approximate Agreement in Byzantine Asynchronous Systems Section 3 of Optimal Resilience Asynchronous Approximate Agreement |
|
| 23 | 11/11/2015 | Ben-Or's algorithm. Full link-reversal algorithm. |
Sections 1, 2, 3, 4 of Correctness Proof of Ben-Or's Randomized Consensus Algorithm First 8 pages of notes from Prof. Soma Choudhuri |
|
| 24 | 11/16/2015 | No lecture (due to exam today) | ||
| 25 | 11/18/2015 | Full link reversal. | First 8 pages of notes from Prof. Soma Choudhuri | |
| 26 | 11/30/2015 |
In-class Quiz. Distributed optimization (NOT included for the final exam). K-set consensus in asynchronous systems, Approximate consensus in asynchronous shared memory. |
Sections 16.1 and 16.2.1 | slides |
| 27 | 12/2/2015 | Student presentations | ||
| make-up class | 12/6/2015 (11:00 am, room 239 CSL) | |||
| 28 | 12/7/2015 | Student presentations | ||
| 29 | 12/9/2015 | Student presentations |