Advanced Distributed Algorithms S2019

Lecture Time & Place: Thursday 10:00-12:00, Ziskind 155 
TA: Avi Cohen
Prerequisite: Sufficient comfort with both algorithm design & analysis, and basic knowledge in distributed algorithms (e.g.,  taking the Distributed Network Algorithms course of Prof. David Peleg).

New: Final assignment instructions

Course Schedule (tentative):

• (28/03) Lecture  01:  Introduction (models, local and global graph problems), network decomposition and applications.  Lecture-01
  • Network decomposition and locality in distributed computation (Awerbuch, Luby, Goldberg and Plotkin, 1989)
  • On the complexity of distributed network decomposition (Panconesi and Srinivasan, 1996).
  • Lecture 04 of Mohsen Ghaffari (Distributed Graph Algorithms 6.S899, MIT)
  • Chapter 9 in the Distributed Graph Coloring book of Barenboim and Elkin, 2001.
     
• (04/04) Lecture 02:  Sequential and randomized network decomposition.
  Exercise-1  (due May 2nd), Lecture-02
  • Low Diameter Graph Decomposition (Linial and Saks, 1993)
  • Section 1.5.2 of Mohsen Ghaffari's notes (Principles of Distributed Computing S19, ETH)
     
• (18/04) Lecture 03:  Randomized and sublogarithmic coloring algorithms Lecture-03
  • Chapter 10 in Distributed Graph Coloring by Barenboim and Elkin, 2001
  • The Locality of Distributed Symmetry Breaking by Barenboim, Elkin, Pettie, and Schneider, 2012.
  • Notes by Mohsen Ghaffari, Section 1.7
     
• (25/04) No Class Due to Passover
   
• (02/05) Lecture 04:  An Improved Distributed Algorithm for Maximal Independent Set by Ghaffari, 2016.   Lecture-04,  Exercise-2 (Due Monday 20/5) 
  • A more detailed description of the algorithm appears in Ghaffari's thesis (Section 3).
     
• (09/05) No Class Due to Yom-Ha'atzmaut
   
• (16/05) Lecture 05: An Exponential Separation between Randomized and Deterministic Complexity in the LOCAL Model (Chang, Kopelowitz, and Pettie, 2017) New: Lecture-05
   
• (23/05):  No Class Due to Lag B'aomer.
   
• (30/05) Lecture 06: Lovasz Local Lemma (LLL) and Distributed LLL New: Lecture-06

  • A constructive proof of the general Lovasz Local Lemma (Moser and Tardos, 2009)

  • Lectures 04 and 05 by Bernhard Haeupler (Algorithmic Superpower Randomization, CMU,  Fall 2019)

  • For additional recommanded lectures notes, see here and here 
     

• (06/06) Lecture 07:  Improved distributed LLL and applications New: Lecture-07 Exercise-03 (Due June 30)
  • Distributed Algorithms for the Lovász Local Lemma and Graph Coloring (Chung, Pettie and Su, 2014)
  • Sublogarithmic Distributed Algorithms for Lovász Local lemma, and the Complexity Hierarchy (Fischer and Ghaffari, 2017)
     
• (13/06) Lecture 08: Intro to global problems in the CONGEST model. Minimum Spanning Tree and low-congestion shortcuts New: Exercise-04
  • Lecture 10 of Principles of Distributed Computing 2019, ETH
  • Lecture 6 and Lecture 7 of Theory of Distributed Systems, 2016, MPI
  • MST Lower Bound, Chapter 24 in Peleg's Book
     
• (20/06) Lecture 9: Distributed minimum cut and connectivity decomposition
  • Distributed Minimum Cut Approximation (Ghaffari and Kuhn, 2013)
  • Lecture 11 of Principles of Distributed Computing 2019, ETH
     
• (27/06) Class Cancelled
   
• (04/07) Lecture 10: Communication complexity based lower bounds, guest class by Seri Khoury (UC Berkeley)
  • Deterministic lower bound for set disjointness in the 2-party communication complexity model  (Communication Complexity book by Kushilevitz and Nisan)
  • Lower bounds in the CONGEST model via reductions to communication complexity
    • Distributed Verification and Hardness of Distributed Approximation  by Das-Sarma et al., 2011
    • Lower bound for exact diameter computation based on  Networks Cannot Compute Their Diameter in Sublinear Time by Frischknecht, Holzer and Wattenhofer, 2012
    • Lower bound for 4-cycle detection based on  On the Power of the Congested Clique Model by Drucker, Kuhn and Oshman, 2014
       
• (11/07) Lecture 11: Distributed Single Source Shortest Paths (SSSP)

Useful Material:

• Probabilities Inequalities: Handout by Avrim Blum and Anupam Gupta (15-859 Randomized Algorithms, CMU, Spring'11).
• Distributed Computing -- A Locality-Sensitive Approach, David Peleg, SIAM.
• Distributed Graph Coloring by Barenboim and Elkin, 2001