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
- 8/22: Starting next week (on Monday, 8/28), our class will meet
MW, 9-10:15 am, in B13 MLH.
- Week 1: 8/21-8/25: The distributed network model, synchrony and asynchrony,
time complexity and message complexity, broadcasts and convergecasts,
the Cole-Vishkin algorithm for vertex coloring.
- Week 2: 8/28-9/1: The Cole-Vishkin algorithm for vertex coloring and MIS.
The Linial algorithm for vertex coloring.
- Week 3: 9/4-9/8: An application of the deterministic
O(log^* n) round MIS algorithm to wireless networks. This is from
a PODC 2005 paper by Kuhn, Moscibroda, and Wattenhofer (ref [11] in
the reading list).
- Week 4: 9/11-9/15: An Omega(log^* n) round lower bound
on 3-coloring a ring, due to Linial. This is from Chapter 7 in Peleg.
- Week 5: 9/18-9/22:
Strengthening Linial's lower bound.
This is from a PODC 2006 paper by Kuhn and Wattenhofer (ref [13] in
the reading list).
- Week 6: 9/25-9/29:
Complexity of Distributed coloring.
This is from a PODC 2006 paper by Kuhn and Wattenhofer (ref [13] in
the reading list).
- Week 7: 10/2-10/6:
Luby's randomized algorithm for MIS in general networks.
This is from Chapter 8 in Peleg.
- Week 8: 10/9-10/13:
Analysis of some variants of Luby's algorithm.
This is from a JCSS 1993 paper by Luby (ref [16])
and a IPL 1999 paper by Johansson (ref [9]).
- Week 9: 10/16-10/20:
Network Decomposition.
This is from a FOCS 1989 paper by Awerbuch, Goldberg, Luby, and Plotkin
(see ref [1]).
- Week 10: 10/23-10/27:
An O(log \Delta)-approximation for the minimum dominating set problem
in O(polylog(n)) rounds. This is from a PODC 2001 paper by
Jia, Rajaraman, and Suel (see ref [8]).
- Week 11: 10/30-11/3:
Continuation of the Jia, Rajaraman, and Suel paper.
Followed by discussion of constant-time dominating set approximation.
This is from a PODC 2003 paper by Kuhn and Wattenhofer.
A full version of this paper has appeared in Dist. Comp. 2005 (see ref [12]).
- Week 12: 11/6-11/10:
Continuation of the Kuhn-Wattenhofer paper.
- Week 13: 11/13-11/17:
Completion of the Kuhn-Wattenhofer PODC 2003 paper.
Start discussion of the paper What cannot be computed locally!
by Kuhn, Moscibroda, and Wattenhofer.
This shows a lower bound on the approximation factor that can be achieved
for minimum vertex cover, minimum dominating set, etc. by a k-round
distributed algorithm.
This paper appeared in PODC 2004.
- Week 14: 11/27-12/1:
Completion of the Kuhn-Moscibroda-Wattenhofer PODC 2004 paper.
- Week 14: 12/4-12/8:
A distributed approximation algorithm for facility location.
This is from a PODC 2005 paper by Moscibroda and Wattenhofer (see ref [17]).