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