CS6851 Distributed Algorithms

List of Topics:

Part 1: Introduction to LOCAL and CONGEST models.
- - Lower bound for 2-coloring.
  - Cole-Vishkin algorithm for 3-coloring rooted trees.
  - Linial's lower bound for 3-coloring.
Part 2: "Local" problems like maxmal independent set (MIS) and coloring.
- - Introduction to basic probability and concentration bounds.
  - Luby's randomized algorithm for MIS.
Part 3: "Global" problems like minimum spanning tree (MST).
- - Different algorithms for MST: GHS, GKP.
  - Lower bound for MST using communication complexity.
Part 4: Fault-tolerant distributed consensus.
- - The Fischer-Lynch-Patterson proof of impossibility of deterministic fault-tolerant consensus.
  - Lamport's Paxos algorithm.
Part 5: Miscellaneous Advanced Topics.
- - Message-efficient algorithms using linear sketching.
  - Randomized and Deterministic Network Decompositions.

Grading

Assignments (50%)
- - Roughly each part will have its own assignment.
  - The submission deadline will be announced along with the assignment. Late submissions will not be allowed.
  - You may discuss with your peers, but you MUST write the solutions on your own.
Final Project (40%)
- - You can do a project on a topic of your liking, as long as it is relevant to the spirit of the course.
  - Deadlines will be announced to check your progress.
Class participation (10%)

Textbook

There is no single textbook for this course, I will provide relevant readings and notes for each topic we cover. But here are some reference materials