6.5250_6.852/18.437 Distributed Algorithms, MIT, Fall 2022

Instructors: Prof. Mohsen Ghaffari and Prof. Nancy Lynch. Office hours by appointment.

Teaching Assistant: Ce Jin. Office hours Thursdays 3:00-5:00 pm, in 32-G5 (open lounge).

Lecture Time & Place: Tuesdays and Thursdays 11:00-12:30 at 32-141.

Level: Graduate, counts as a TQE course in Theoretical Computer Science.

Administrative Assistants: Joanne Hanely and Nathan Higgins.

Canvas: Distributed Algorithms 2022 on Canvas (for nonpublic material). If you want Canvas access but are not registered in the course, please send an email to the course TA describing your background and how you plan to participate in the course.

Piazza: Distributed Algorithms 2022 on Piazza (for discussions). Please make sure to enroll, especially if you are taking this course for credit.

Feedback: Anonymous Form. Whenever possible, we prefer non-anonymous feedback, as it allows us to further discuss the issue. For non-anonymous feedback, please send an email to Mohsen with the title 6.5250 Distributed Algorithms: Feedback.

Course Description: Distributed computing is central to many modern computational systems, including wired and wireless communication networks, cluster computing, multi-core computers, robot swarms, data management systems, and transportation systems. This is a graduate-level theory course and it introduces and investigates the fundamental aspects of distributed computing, including communication and coordination, locality, symmetry breaking, parallelism, fault-tolerance, asynchrony, bandwidth limitations and congestion, and beyond. The focus will be on algorithmic tools and techniques and methods for proving lower bound or impossibility results.

Prerequisites: Sufficient mathematical maturity to start a graduate-level algorithmic course, including comfort with the basics of algorithm design and analysis, basics of probability, and some prior exposure to randomized algorithms. For instance, having passed MIT's 6.1220/6.046 Design and Analysis of Algorithms would suffice. No background in distributed systems is required. If you're not sure whether you are ready for this course, please talk to Mohsen.

Grading: Six biweekly problem sets 50%, course project 30%, scribing and peer grading 20%. See the Canvas page for further instructions.

 

---

Lectures (Tentative)

The syllabus/material will be updated during the semester. Green links show the main sources (scripts, textbooks, scribe notes, or slides). Blue links point to optional/supplementary material, usually source papers or other related work. Red links indicate deliverables (problem sets or project items).

Block 1: General Introduction

• Lecture  01 (Sept. 08): Introduction, Logistics, and Distributed Coloring in a Ring
  • Section 1.2.1 of the DGA notes
  • Cole and Vishkin (Information and Control Journal 1986)
  • Goldberg, Plotkin, and Shannon (STOC 1987)
  • Naor and Stockmeyer (STOC 1993)
• Lecture  02 (Sept. 13): Flooding, BFS tree, Broadcast, Convergecast, and Bellman-Ford
  • Scribe Notes 

 

Block 2: Local Distributed Graph Algorithms

• Lecture  03 (Sept. 15): Coloring Algorithms
  • Section 1.4 of the DGA notes
  • Linial (FOCS 1987)
  • Kuhn and Wattenhofer (PODC 2006)
• Lecture  04 (Sept. 20): Coloring Lower Bounds
  • Sections 1.2.2 and 1.3.1 of the DGA notes
  • Linial (FOCS 1987)
• Lecture  05 (Sept. 22): Maximal Independent Set
  • Section 1.6 of the DGA notes
  • Deadline for PSET 1
  • Luby (STOC 1985)
  • Alon, Babai, and Itai (Journal of Algorithms 1986)
  • Israeli and Itai (Info. Proc. Letters 1986)
• Lecture  06 (Sept. 27): Network Decomposition, Definition and Randomized Constructions
  • Sections 1.5.1 and 1.5.2. of the DGA Notes
  • Awerbuch, Goldberg, Luby, and Plotkin (FOCS 1989)
  • Linial and Saks (SODA 1992)
  • Miller, Peng, Xu (SPAA 2013)
  • Elkin and Neiman (PODC 2016)
• Lecture  07 (Sept. 29): Network Decomposition, Deterministic Constructions
  • Sections 1.5.4 of the DGA Notes
  • Panconesi and Srinivasan (STOC 1992)
  • Rozhon and Ghaffari (STOC 2020)

Block 3: Fault Tolerance and Asynchrony in Distributed Computing

• Lecture  08 (Oct. 04): Fault-tolerant Synchronous Consensus Algorithms
  • Sections 5.1, 6.1-6.3 of the Lynch Textbook
  • Slides
• Lecture  09 (Oct. 06): Fault-tolerant Synchronous Consensus Lower Bounds
  • Sections 6.4-6.7, 7.1 of the Lynch Textbook
  • Slides
  • Deadline for PSET 2
• Lecture  10 (Oct. 13): Modeling Asynchronous Network Algorithms, and Basic Algorithms
  • Chapters 8, 14, and 15 of the Lynch Textbook
  • Slides
• Lecture  11 (Oct. 18): Mutual Exclusion Algorithms
  • Chapter 9 and Sections 10.1-10.5, 10.7 of the Lynch Textbook
  • Slides
• Lecture  12 (Oct. 20): Impossibility of Consensus in Asynchronous Shared-Memory Systems
  • Chapter 12 of the Lynch Textbook
  • Slides
  • Deadline for PSET 3
• Lecture  13 (Oct. 25): Shared-Memory vs Networks, Consensus in Asynchronous Networks, and Paxos
  • Chapter 17 of the Lynch Textbook
  • Slides

 

Block 4: Global Distributed Graph Algorithms 

• Lecture  14 (Oct. 27): Synchronizers
  • Scribe Notes (initial draft)
  • Awerbuch (Journal of ACM 1985)
  • Awerbuch and Peleg (FOCS 1990)
  • Awerbuch, Patt-Shamir, Peleg, and Saks (STOC 1992)

• Lecture  15 (Nov. 01): MST Algorithms
  • Section 2.2 of the DGA Notes
  • Handwritten notes (the shared screen in the recorded video)
  • Garay, Kutten, Peleg (FOCS 1993)
  • Kutten and Peleg (PODC 1995)
• Lecture  16 (Nov. 03): Min-Cut Algorithms
  • Section 2.3 of the DGA Notes
  • Deadline for PSET 4  (11:59 pm on November 4)
  • Ghaffari and Kuhn (DISC 2013)
  • Ghaffari and Haeupler (SODA 2016)
• Lecture  17 (Nov. 08): Lower Bounds for MST, Min-Cut, Shortest Paths, and Beyond
  • Scribe Notes (initial draft)
  • Peleg and Rubinovich (FOCS 1999)
  • Das Sarma et al. (STOC 2011)
• Lecture  18 (Nov. 10): Shortest Path Algorithms
  • Scribe Notes
  • Nanongkai (STOC 2014)
• Lecture  19 (Nov. 15): Shortest Path  Algorithms,  continued
  • Scribe Notes (initial draft)
  • Nanongkai (STOC 2014)
  • Lenzen and Patt-Shamir (STOC 2013)
  • Baswana and Sen (RSA 2006)

 

Block 5: Selected Topics

• Lecture  20 (Nov. 17): Routing in the Complete Network
  • Scribe Notes (initial draft)
  • Lenzen and Wattenhofer (STOC 2011)
  • Lenzen (PODC 2013)
  • Deadline for PSET 5 (11:59 pm on November 18)
• Lecture  21 (Nov. 22): Connectivity via Linear Sketching
  • Scribe Notes
  • Ahn, Guha, McGregor (SODA 2012)
  • Ahn, Guha, McGregor (PODS 2012)
  • Kapron, King, Mountjoy (SODA 2013)
• Lecture  22 (Nov. 29): Local Computation Algorithms (LCAs) 
  • Scribe Note TBA
  • Nguyen and Onak (FOCS 2008)
  • Rubinfeld, Tamir, Vardi, and Xie (ITCS 2011)
  • Alon, Rubinfeld, Vardi, and Xie (SODA 2012)
  • Ghaffari and Uitto (SODA 2019)
  • Ghaffari (FOCS 2022)
• Lecture 23 (Dec. 01): Shattering and Its Necessity
  • Scribe Notes TBA
  • Deadline for PSET 6
  • Berenboim, Elkin, Pettie, and Schneider (FOCS 2012)
  • Ghaffari (SODA 2016)
  • Chang, Kppelowitz, Pettie (FOCS 2016)
• Lecture 24 (Dec. 06), option 1: The Landscape of Local Distributed Complexities 
  • Scribe Notes TBA
  • Chang, Kopelowitz, Pettie (FOCS 2016)
  • Chang and Pettie (FOCS 2017)
  • Fischer and Ghaffari (DISC 2017)
• Lecture  24 (Dec. 06), option 2: Local Rounding
  • Scribe Notes TBA
  • Ghaffari and Kuhn (FOCS 2021)
  • Faour, Ghaffari, Grunau, Kuhn, Rozhon (SODA 2023)

 

Block *: Project Presentations and Reports

• • Project presentations on Demeber 13, from 9 am to 4 pm.
  • Deadline for final project reports, 11:59 pm on Dec 17

---

Accessibility