Distributed Algorithms
Com S 612
Course Topics/Chapters/Papers
The following is a tentative schedule of the topics we will be covering in class.
| Week | Date | Book Chapters/ Papers | Topics |
|---|---|---|---|
| 1 | Aug 21 | AW Section 1 | Course Policies Introduction to Distributed Computing |
| 1 | Aug 23 | AW Section 2.1 | Formal Model for Message Passing Systems |
| 2 | Aug 28 | AW Section 3.1, 3.2 | Proofs comparing the strength of various models Leader Election in Rings |
| 2 | Aug 30 | AW Section 3.3.1 | O(n^2) message complexity algorithm for asynchronous rings |
| 3 | Sept 4 | AW Section 3.3.2 | O(n log n) message complexity algorithm for asynchronous rings |
| 3 | Sept 6 | AW Section 3.3.3 | An n log n lower bound for asynchronous rings |
| 4 | Sept 11 | AW Section 3.4.1 | O(n) message complexity algorithms for synchronous rings |
| 4 | Sept 13 | AW Section 4.1 | Formal Model for Shared Memory Systems |
| 5 | Sept 18 | AW Sections 4.2, 4.4.1 | The Mutual Exclusion Problem Lamport's Bakery Algorithm |
| 5 | Sept 20 | AW Section 4.4.2 | A Bounded Mutual Exclusion algorithm for 2 processors |
| 6 | Sept 25 | AW Section 4.4.3 | A Bounded Mutual Exclusion algorithm for n processors |
| 6 | Sept 27 | AW Section 4.4.4 | Lower Bound on number of Read/Write Registers |
| 7 | Oct 2 | AW Section 4.4.4 | Lower Bound on number of Read/Write Registers (contd.) |
| 7 | Oct 4 | AW Section 4.3.1, 4.3.2 | Mutual Exclusion using Powerful Primitives |
| 8 | Oct 9 | AW Section 4.3.3 | Lower Bound on number of Memory States |
| 8 | Oct 11 | AW Section 5.1.1 - 5.1.3 | Consensus in Synchronous Systems with Crash Failures |
| 9 | Oct 16 | AW Section 5.1.4 | (f+1)-round Lower Bound for Consensus |
| 9 | Oct 18 | AW Section 5.2.1 - 5.2.3 | Consensus in Synchronous Systems with Byzantine Failures Lower Bound on Degree of Fault-Tolerance |
| 10 | Oct 23 | AW Section 5.2.4 - 5.2.5 | An Exponential Message Size Algorithm A Polynomial Message Size Algorithm |
| 10 | Oct 25 | AW Section 5.3 | Impossibility of Consensus in Asynchronous Systems |
| 11 | Oct 30 | AW Section 14.1 - 14.3 | Randomization: Leader Election, Mutual Exclusion, Consensus |
| 11 | Nov 1 | AW Section 6.1 | Causality & Time Logical Clocks and Vector Clocks |
| 12 | Nov 6 | AW Section 6.2 - 6.3 | Consistent Cuts Clock Synchronization |
| 12 | Nov 8 | AW Section 8.1 | Specification of Broadcast Services |
| 13 | Nov 13 | AW Section 9.1 - 9.2 | Distributed Shared Memory Linearizability & Sequential Consistency |
| 13 | Nov 15 | AW Section 9.3 | Algorithms for Linearizability & Sequential Consistency |
| - | Nov 20 | - | Fall Break |
| - | Nov 22 | - | Fall Break |
| 14 | Nov 27 | AW Section 9.4 | Time Lower Bounds for Linearizability & Sequential Consistency |
| 14 | Nov 29 | AW Section 10 | Fault-Tolerant Register Simulations |
| 15 | Dec 4 | - | Student Presentations |
| 15 | Dec 6 | - | Student Presentations |
| 16 | Dec 10 | - | Student Presentations |