**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 |