| LEC # | TOPICS | KEY DATES |
|---|---|---|
| 1 | Course Overview Synchronous Networks Leader Election in Synchronous Ring Networks | |
| 2 | Basic Computational Tasks in Synchronous Networks: Leader Election Breadth-first Search Shortest Paths Broadcast and Convergecast | |
| 3 | Breadth-first Search (cont.) Shortest Paths (cont.) Broadcast and Convergecast (cont.) Spanning Trees Minimum Spanning Trees | |
| 4 | Fault-tolerant Consensus Link Failures: The Two Generals Problem Process Failures (Stopping, Byzantine) Algorithms for Agreement with Stopping Failures | |
| 5 | Exponential Information Gathering Algorithms for Agreement with Byzantine Failures | Homework assignment 1 due |
| 6 | Number-of-processes Lower Bounds for Byzantine Agreement Weak Byzantine Agreement Time Bounds for Consensus Problems | |
| 7 | Other Kinds of Consensus Problems: $k$-agreement Approximate Agreement Distributed Commit | |
| 8 | Asynchronous Distributed Computing Formal Modeling of Asynchronous Systems using I/O Automata | |
| 9 | Proof Methods Non-fault-tolerant Algorithms for Asynchronous Networks Leader Election, Breadth-first Search, Shortest Paths, Broadcast and Convergecast | Homework assignment 2 due |
| 10 | Non-fault-tolerant Algorithms for Asynchronous Networks (cont.) Leader Election, Breadth-first Search, Shortest Paths, Broadcast and Convergecast (cont.) | |
| 11 | Spanning Trees Gallager et al. Minimum Spanning Tree Algorithm | |
| 12 | Synchronizers | Homework assignment 3 due |
| 13 | Synchronizer Applications Time, Clocks, and the Ordering of Events Vector Timestamps | |
| 14 | State-machine Simulation Synchronous vs. Asynchronous Distributed Systems Stable Property Detection Distributed Termination Global Snapshots Deadlock Detection Asynchronous Shared-memory Systems | |
| 15 | Mutual Exclusion Mutual Exclusion Algorithms | |
| 16 | Mutual Exclusion Algorithms (cont.) | Homework assignment 4 due |
| 17 | Bounds on Shared-memory for Mutual Exclusion | |
| 18 | Impossibility of Consensus in Asynchronous, Fault-prone, Shared-memory Systems | |
| 19 | Atomic Objects Atomic Snapshot Algorithms | |
| 20 | Atomic Read/Write Register Algorithms Wait-free Computability The Wait-free Consensus Hierarchy | Homework assignment 5 due |
| 21 | The Wait-free Consensus Hierarchy (cont.) | |
| 22 | Wait-free vs. $f$-fault-tolerant Atomic Objects | |
| 23 | Asynchronous Network Model vs. Asynchronous Shared-memory Model Impossibility of Consensus in Asynchronous Networks Failure Detectors and Consensus | Homework assignment 6 due |
| 24 | Paxos Consensus Algorithm Reliable Communication using Unreliable Channels | |
| 25 | Reliable Communication using Unreliable Channels (cont.) Self-stabilizing Algorithms | |
| 26 | Atomic Memory Algorithms for Dynamic Networks Rambo | Homework assignment 7 due |