22C:196 Advanced Distributed Algorithms

9:30-10:20 MWF, Room 112 MLH


Instructor: Sriram V. Pemmaraju
101G MLH, sriram@cs.uiowa.edu, 319-353-2956
Office Hours: 10:30 to 11:30 MWF and by appointment.

The course is on distributed algorithms with a focus on locality. We will be mainly interested in (i) distributed algorithms that solve problems exactly or approximately in at most polylogarithmic number of rounds and (ii) why certain problems cannot be solved in polylogarithmic number of rounds. Some of the problems for which polylogarithmic distributed algorithms exist include maximal independent set (MIS), vertex coloring, edge coloring, dominating set, facility location, etc. The algorithms we will study include the Cole-Vishkin algorithm for vertex coloring and MIS, Luby's randomized MIS algorithm, Linial's vertex coloring algorithms, the Linial-Saks network decomposition algorithm, and the Jia-Rajaraman-Suel approximation algorithm for minimum dominating set. We will also study lower bound results showing that certain problems, including the minimum spanning tree problem (MST), are impossible to solve in a certain number of rounds. These lower bound arguments include the MIS/coloring lower bound due to Linial, the MST lower bound due to Peleg and Rubinovich, and MST-approximation lower bound due to Elkin.

Syllabus document, Announcements, Homeworks and Exams, Weekly Topics, Online Resources



Announcements

Homeworks and Exams

Weekly Topics

Online Resources