6.852: Distributed Algorithms
Below are links to material relevant to our lectures. Each lecture will appear below on the day
it is held.
Lecture 01 (Tue 2/5/2008): Introduction
- Handouts:
- Course Information [PDF]
- Course Schedule [PDF]
- Supplementary Reading List [PDF]
Lecture 02 (Thur 2/7/2008): Leader Election
- Handouts:
- Problem Set 1, Part a [PDF]
Lecture 03 (Tue 2/12/2008): Synch Algs in General Graphs
Lecture 04 (Thur 2/14/2008): Consensus with Failures
- Handouts:
- Problem Set 1, Part b [PDF]
Lecture 05 (Thur 2/21/2008): Consensus Bounds
- Handouts:
- Problem Set 2, Part a [PDF]
Lecture 06 (Tue 2/26/2008): More Consensus Bounds, k-Agreement
Lecture 07 (Thur 2/28/2008): Commit, IOA Introduction
- Lecture Notes:
- Lecture Slides pt. 1 [PPT]
- Lecture Slides pt. 2 [PDF]
- Handouts:
- Problem Set 2, Part b [PDF]
- Introduction to Tempo Toolkit [PDF]
Lecture 08 (Tue 3/4/2008): More Asynchrony
Lecture 09 (Thur 3/6/2008): Leader Election, BFS, and Shortest Paths
- Handouts:
- Problem Set 3, Part a [PDF]
Lecture 10 (Tue 3/11/2008): Minimum Spanning Trees, Synchronizers
- Lecture Notes:
- Lecture Slides pt. 1 [PDF]
- Lecture Slides pt. 2 [PPT]
Lecture 11 (Thur 3/13/2008): More Synchronizers, Logical Time
- Handouts:
- Problem Set 3, Part b [PDF]
Lecture 12 (Tue 3/18/2008): Snapshots, Property Detection, and Intro to Shared Memory
- Lecture Notes:
- Lecture Slides pt. 1 [PPT]
- Lecture Slides pt. 2 [PPT]
Lecture 13 (Thur 3/20/2008): Asynchronous Shared Memory Systems
- Handouts:
- Problem Set 4, Part a [PDF]
Lecture 14 (Tue 4/01/2008): Mutual Exclusion
- Lecture Notes:
- Lecture Slides Pt. 1 [PPT]
- Lecture Slides Pt. 2 [PDF]
- Fake Lecture Slides Post on April 1st [PPT]
Lecture 15 (Thur 4/03/2008): Mutual Exclusion with RMW Objects
- Handouts:
- Problem Set 4, Part b [PDF]
Lecture 16 (Thur 4/08/2008): Consensus Lower Bounds
Lecture 17 (Thur 4/10/2008): Atomic Objects
- Handouts:
- Problem Set 5, Part a [PDF]
Lecture 18 (Tue 4/15/2008): Atomic Snapshot Objects and Implementing Read/Write Objects
- Handouts:
- Revised Course Schedule [PDF]
Lecture 19 (Thur 4/17/2008): Wait-Free Synchronization
- Handouts:
- Problem Set 5, Part b [PDF]
Lecture 20 (Thur 4/24/2008): Boosting
- Handouts:
- Problem Set 6, Part a [PDF]
Lecture 21 (Thur 4/29/2008): List Algorithms
Lecture 22 (Thur 5/1/2008): Transactional Memory
- Handouts:
- Problem Set 6, Part b [PDF]
Lecture 23 (Tue 5/6/2008): Shared Memory vs. Network Model; Paxos
Lecture 24 (Thur 5/8/2008): Paxos Concluded; Self-Stabilization Begun
- Lecture Notes:
- Lecture Slides (Paxos) [PDF]
- Revised Lecture Slides (Paxos) [PDF]
- Lecture Slides (Self-Stabilization) [PPT]
Lecture 25 (Tue 5/13/2008): Self-Stabilization Concluded; Partial Synchrony Begun
- Lecture Notes:
- Lecture Slides (Self-Stabilization) [PPT]
- Lecture Slides (Partial Synchrony) [PPT]