Lecture Time & Place: Wednesday 10:15-12:00, Ziskind 155
Lecturers: David Peleg and Merav Parter
Teaching Assistant: Orr Fischer
The course covers the key notions and principles of distributed computing theory. The student is expected to become familiar with some of the basic paradigms and algorithmic techniques of the field of distributed network algorithms, learn about some of the central problems in the area and their solutions, and get exposed to modern research in the field.
Prerequisite: Sufficient comfort with algorithm design & analysis, and basic knowledge of graph algorithms.
Course Schedule (tentative):
(19/04) Lecture 01 (D): Introduction, the distributed model, asynchrony, complexity measures. Slides
Exercise 1 due to May 04.
(10/05) Lecture 02 (D): The broadcast problem, construction of spanning trees. Slides
(17/05) Lecture 03 (M): Intro to local graph prblems, 3-coloring oriented trees Slides Notes
- Locality in distributed graph algorithms, Linial 1992
- Chapter 1 by Roger Wattenhofer (Principles of Distributed Computing, ETH 2017)
- Sect. 3.4 of Distributed Graph Coloring by L. Barenboim and M. Elkin
- Linial's Lower Bound Made Easy, Laurinharju and Suomela 2014
- Lecture 1b by Jukka Suomela (Distributed Algorithms, Aalto University 2020)
- Advanced reading: a beautiful exposition of the round elimination technique by J. Suomela
Exercise 2 due to June 14 (extended)
(07/06) Lecture 04 (M): Coloring General Graphs, Maximal Independent Set (MIS)
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)
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)
Useful Probabilities Inequalities: Handout by Avrim Blum and Anupam Gupta (15-859 Randomized Algorithms, CMU, Spring'11).
(14/06) Lecture 05 (M): Network Decomposition: Sequential and Randomized
Low Diameter Graph Decomposition (Linial and Saks, 1993)
Lecture Notes (Advanced Distributed Algorithms, Weizmann IS 2019)
Scribes by Avi Cohen (Distributed Graph Algorithms, Weizmann IS 2021)
Section 1.5 by M. Ghaffari (Principles of Distributed Computing S19, ETH)
(21/06) Lecture 06 (M): Network Decomposition cont. (deterministic), Spanners
Section 1.5 by M. Ghaffari (Principles of Distributed Computing S19, ETH)
A Simple and Linear Time Randomized Algorithm for Computing Sparse Spanners in Weighted Graphs (Baswana and Sen '03)
Spanner-Slides
Exercise 3 due to July 11
(28/06) Lecture 07 (M): Spanners cont.
(05/07) Lecture 08 (D): Synchronizers: Methodology, Synchronizers α,β + Initialization
Slides
(12/07) Lecture 09 (D): Synchronizer (cont.), Additive Spanners Slides
Exercise 4 due to July 27
(19/07) Lecture 10 (D): Leader Election, Algorithms on a Ring and Message Lower Bounds
Slides
Bibliography
-
N. Lynch, Distributed Algorithms, Morgan Kaufmann Publishers, Inc., San Mateo, California, 1995.
-
D. Bertsekas and R. Gallager, Data Networks, Prantice Hall, Englewood Cliffs, New Jersey, 1987.
-
M. Raynal, Algorithms for Mutual Exclusion, MIT Press, Cambridge, MA, 1986.
-
D. Peleg, Distributed Computing: A locality-Sensitive Approach, SIAM, Philadelphia, 2000.
-
Leonid Barenboim, Michael Elkin: Distributed Graph Coloring: Fundamentals and Recent Developments. Synthesis Lectures on Distributed Computing Theory, Morgan & Claypool Publishers 2013.
-
CS-E4510 - Distributed Algorithms Course by Jukka Suomela