CS590A: Distributed Network Algorithms - Fall 2007

Professor

Gopal Pandurangan (gopal@cs.purdue.edu)
Office: LWSN 1209
Office hours: by appointment

Lectures

TTh 1:30-2:45pm Room: LWSN B134

About this course

This course is about Distributed computing in general, and distributed network algorithms, in particular. With the emergence of the Internet and other modern networking technologies such as peer-to-peer networks, overlay networks, and ad hoc wireless and sensor networks, it is has become all the more important to design and analyze efficient distributed algorithms for solving various key distributed computing problems. This course will start with the basics of distributed algorithms. We will then cover distributed network algorithms for solving fundamental network optimization problems. This includes leader election, routing algorithms (including shortest paths), spanning trees, and minimum spanning trees. Applications to the Internet, peer-to-peer, ad hoc and sensor networks will be stressed throughout the course. The last part of the course will deal with recent cutting-edge stuff in the area from journals and conferences. This course will be of importance not only to algorithms and theory students, but also to students interested in networking and distributed systems including those working in the Internet, peer-to-peer, ad hoc wireless and sensor networks.
The course is aimed towards graduate students (and advanced undergraduate students) in Computer Science and ECE. There are no real prerequisites, but CS580 (Graduate-level Algorithms course) or equivalent is highly recommended. Talk to me if you have any questions.

Topic Themes (Tentative)

Basic Distributed Algorithms

Leader Election

Routing algorithms

Distributed Graph Algorithms

Minimum Spanning Tree

Distributed Approximation Algorithms

Locality in distributed algorithms: covers, partitions, and spanners

Applications to Internet, Peer-to-Peer and Sensor networks

Lecture Slides and Notes

Lecture 1: Introduction 1.pdf
Reading: Theory of Communication networks , 590R Lecture Notes (1-6). First chapter of Tel.

Lecture 2: Maximal Independent Set (MIS) Algorithm 2.pdf
Luby's paper
Related Papers (for Project Ideas/Presentation):
MIS in radio networks Deterministic MIS Algorithms for growth bounded graphs (includes unit disk graphs, a popular model for wireless networks)
A fast randomized MIS algorithm for growth bounded graphs
What cannot be computed locally (gives distributed time lower bounds on MIS and other problems)
What can be computed locally
Distributed Dominating Set Algorithm
Another nice distributed dominating set algorithm
Locality in Distributed Graph Algorithms

Lecture 3: Tree Construction Algorithms 3.pdf
Reading: Peleg's book, Chapter 5 and Chapter 6 (Synchronizers).
Best known BFS algorithms are due to:
Network Synchronization with Polylogarithmic Overhead and
Sparser: A paradigm for running distributed algorithms

Lecture 4: Leader Election Algorithms 4.pdf
Reading: Tel's book (Chapter 7), Lynch's book (Chapter 3).
Khan, Pandurangan, Kumar algorithm
D. Peleg. A Time Optimal Leader Election algorithm in general networks, Journal of parallel and distributed computing, vol. 8, pages 96-99, 1990.
Korach, Kutten, Moran Algorithm
Scalable leader election

Lecture 5: Minimum Spanning Tree Algorithms 5.pdf
Reading: Lynch's book (Chapters 4.4 and 15.5), Theory of Communication networks

Lecture 6: Clocks, Synchronization, Event Ordering etc. (by Prof. P. Eugster) 6.pdf

Lecture 7: Routing Algorithms 7.pdf
Reading: Theory of Communication networks , Tel (Chapter 4). Computer Networking by Kurose and Ross (Chapter 4) gives a good overview of the practical aspects of routing in the Internet.
Approximate Distributed Bellman Ford Algorithms

Lecture 8: Faster Distributed MST Algorithms 8.pdf
Reading: Theory of Communication networks , Peleg (Chapters 5 and 24).
Kutten and Peleg's MST Algorithm
An O(log log n) time MST algorithm in a complete network
Elkin's faster MST algorithm
A distributed algorithm for finding minimum diameter spanning trees
A fast distributed MST approximation algorithm

Lecture 9: Distributed Approximate MST Algorithms 9.ppt
Reading: Peleg (Chapter 24, lower bounds for MST)
A fast distributed MST approximation algorithm
Unconditional lower bounds on the time-approximation tradeoffs for the distributed minimum spanning tree problem

Lecture 10: Wireless Sensor Network Applications 10.ppt
Reading: Distributed Algorithms for Constructing Approximate Minimum Spanning Trees in Wireless Sensor Networks

Lecture 11: Interesting Graph Classes 11.pdf

Lecture 12: Compact routing 12.pdf
Reading: Peleg (Chapter 9, 11,12, 26).
Sparse Network Covers
Network Decomposition
Linial and Saks Network Decomposition Algorithm

Lecture 13: Dominating set 13.pdf
Distributed dominating set algorithm
Jia, Rajaraman, Suel Algorithm
Lecture notes from Wattenhofer
Kuhn and Wattenhofer algorithm

Lecture 14: Fast Distributed Construction of Small k-dominating Sets and Applications by Satyajit Desai.

Lecture 15: What cannot be computed locally by Yongwook Choi.

Lecture 16: Distributed Dominating Set Algorithm by Xun Zhou

Lecture 17: Constant Time Distributed Dominating Set Algorithm by Sagar Mittal.

Lecture 18: Fast Cover Constructions and Application to Distributed MST by Vasil Denchev.

Lecture 19: Fast MST Construction in Complete Networks by Hwan Jo Heo.

Lecture 20: Network Decompositions, locality, bounded growth graphs by Ashish Gandhe.

Lecture 21: Local MST Computation with short advice by Khalilallah Aglaguel.

Textbook/References

The main source of reference will be the lecture notes and slides. We will not follow any one textbook, but the following references will be helpful, besides papers from journals/conferences.
(I have asked these books to be placed in reserve in the Math Sciences Library).
1) Distributed Computing: A Locality Sensitive Approach by David Peleg
2) Distributed Algorithms by Nancy Lynch
3) Introduction to Distributed Algorithms by Gerard Tel
4) Distributed Systems: An Algorithmic Approach by Sukumar Ghosh
5) Theory of Communication networks by Pandurangan and Khan , to appear in Algorithms and Theory of Computation Handbook, Second Edition
6) Lecture Notes on Randomized Algorithms (CS590R) CS590R
7) Lecture Notes on Algorithms (CS580) CS580
8) Computer Networking by Kurose and Ross (4th edition)

Grading

Every class one (or two) students will be nominated to take lecture notes. These should be typeset in Latex and turned in the next week. The first part of the course will consist of lectures by me. The second part of the course will be devoted to studying some recent interesting results in the area. One student will lead the discussion every week. There will be NO exams. There will be a final project and presentation. The project should be a theoretical or experimental analysis of significant scope. Students are required to discuss with me well in advance of their project interests.
The grading split-up is (approx.) :
lecture notes and class participation: 25%
paper discussion and presentation: 25%
final project: 50%

Newsgroup

We plan to use the purdue.class.cs590a newsgroup (on the server news.purdue.edu) for announcements and other postings. You should subscribe to this newsgroup and check it regularly. Send all general questions (such as clarifications regarding assignments etc.) to this newsgroup.