Distributed Graph Algorithms S2021

Lecture Time & Place: Wednesday 10:15-12:00, Ziskind 155 (after Passover)
Teaching Assistant: Avi Cohen 

Zoom link

Prerequisite: Sufficient comfort with algorithm design & analysis, and basic knowledge of graph algorithms.

Course Schedule (tentative):

*** PART A: LOCALITY (Distributed Symmetry Breaking) ***

(24/03) Lecture  01:  Introduction (models, local and global graph problems), tree coloring. 
Intro-Slides 3ColoringTrees
Chapter 1  by Roger Wattenhofer (Principles of Distributed Computing, ETH 2017)
Sect. 7.3 of Distributed Computing: A Locality-Sensitive Approach by D. Peleg (SIAM)
Sect. 3.4 of Distributed Graph Coloring by L. Barenboim and M. Elkin 
Lecture 1b by Jukka Suomela  (Distributed Algorithms,  Aalto University 2020)

(31/03) Passover

(07/04) Lecture 02: Lower bounds for oriented tree coloring, coloring unoriented trees
Locality in distributed graph algorithms, Linial 1992
Linial's Lower Bound Made Easy,  Laurinharju and Suomela 2014
Lecture notes by M. Ghaffari (Principles of Distributed Computing, ETH 2017)
Advanced reading: a beautiful exposition of the round elimination technique by J. Suomela 

(14/04) Memorial Day

(21/04)  Lecture 03: Deterministic and randomized coloring for general graphs
Single round color reduction with cover-free families (Sec. 1.4) by M. Ghaffari (Principles of Distributed Computing, ETH 2017)
Randomized coloring (only page 1)  (Advanced Distributed Algorithm, Weizmann 2019)

(28/04) Lecture 04: Maximal Independent Set (Luby's algorithm) and intro to network decomposition.
Lecture Notes by C. Lenzen (Theory of Distributed Systems, Max-Planck Institute 2017)
Lecture Notes by E. Vigoda (Randomized Algorithms,  Georgia Tech 2006)
Section 1.6 by M. Ghaffari (Principles of Distributed Computing, ETH 2017)

(05/05) Lecture 05:  Network Decomposition (centralized, randomized and det. constructions)
Scribes by Avi Cohen
Lecture Notes (Advanced Distributed Algorithms, Weizmann IS 2019)
Section 1.5 by M. Ghaffari (Principles of Distributed Computing, ETH 2017)
Deterministic Network Decomposition and Distributed Derandomization (Rozhoň and Ghaffari, STOC 2020)

(12/05) No Class (Security Alert)

(19/05) Lecture 06: Sequential Local Algorithms, (1+eps) Approximation of Max-IS and DS
Lecture Notes
On the Complexity of Local Distributed Graph Problems (Ghaffari, Kuhn, Maus '17)

Exercise 2 due June 3rd

(26/05) Lecture 07: Lovasz Local Lemma (LLL) and Distributed LLL 
Scribes by Avi Cohen  
Scribes-1 2019   Scribes-2 2019 (Advanced Distributed Algorithms, Weizmann IS 2019)
A constructive proof of the general Lovasz Local Lemma (Moser and Tardos, 2009)
Distributed Algorithms for the Lovász Local Lemma and Graph Coloring (Chung, Pettie and Su, 2014)

*** PART B: CONGESTION (Global Graph Problems) ***

(02/06)  Lecture 08: Minimum Spanning Trees 
Section 2 by M. Ghaffari (Principles of Distributed Computing, ETH 2017)
MST Lower Bound, Chapter 24 in Peleg's Book

Exercise 3 due June 22th

(09/06) Lecture 09: Low Congestion Shortcuts, Approximate Minimum Cuts 
Scribes by Avi Cohen
Section 2.3 by M. Ghaffari (Principles of Distributed Computing, ETH 2017)

(16/06) Lecture 10:  Spanners 
Slides
A Simple and Linear Time Randomized Algorithm for Computing Sparse Spanners in Weighted Graphs (Baswana and Sen '03)
Sec. 2 in Efficient Algorithms for Constructing Very Sparse Spanners and Emulators (Elkin and Neiman '17) 

(23/06) Lecture 11: Packet Routing and Distributed Scheduling
Packet routing and job-shop scheduling inO(congestion+dilation) steps (LMR'94)
Lecture Notes by A. Sinclair (CS271 Radomness & Computation, Berkeley 2020)
Lecture Notes by D. Kanoulas (R. Rajaraman, CS7880 Algorithmic Power Tools,  Northeastern University)
Lecture Notes by C. de Boor (B. Haeupler,  Algorithmic Superpower Randomization,  CMU 2019)
Near-Optimal Scheduling of Distributed Algorithms (Ghaffari, 2015)

(30/06) Lecture 12: Distributed Shortest Paths
Distributed Approximation Algorithms for Weighted Shortest Paths (Nanongkai, 2014)
Danupon's Slides and Talk @STOC'14
Scribes by Avi Cohen

Exercise 4 due to July 12th

(07/07) Lecture 13: Distributed Byzantine Computation
The Byzantine Generals Problem (Lamport, Shostak and Pease, 1980)
Lecture Notes by R. Wattenhofer (Distributed Systems, ETH 2015)
Chapter 10 by J. Aspnes (Theory of Distributed Systems, Yale 2020)
Chapter 5 by H.  Attiya and J. Welch (Distributed Computing: Fundamentals, Simulations, and Advanced Topics)
Sec. 2.2 of Broadcast CONGEST Algorithms against Adversarial Edges (Hitron and Parter, 2021)
Scribes by Avi Cohen

 

 

Useful Material:

Distributed Computing -- A Locality-Sensitive Approach, David Peleg, SIAM.

Distributed Graph Coloring by Barenboim and Elkin, 2001

CS-E4510 - Distributed Algorithms Course by Jukka Suomela