Course content:
· Distributed Computing: Introduction, Models, and Challenges
· Broadcast, Converge-cast, BFS Tree Construction, Time in Distributed System
· BFS Tree Construction, Time in Distributed System
· Leader Election: Algorithms and Lower Bounds
· Distributed Graph Algorithms:
o Coloring, Maximal independent set
o Shortest Path, MST
· Distributed Consensus:
o Consensus with link failure
o Consensus with crash failure
o Consensus with Byzantine failure
· Distributed Algorithms for mobile robots:
o Exploration
o Gathering
o Dispersion
Textbooks Distributed Network Algorithms by Gopal Pandurangan. Download from here.
Distributed Computing: Fundamentals, Simulations and Advanced Topics, 2nd edition, by Jennifer Welch and Hagit Attiya.
Lecture Notes
Lecture 9-11: Graph Coloring1 (Slow Graph coloring, Fast tree coloring)
Lecture 16-17: Minimum Spanning tree: GHS Algorithm (Lecture note by Prof. Pallab Dasgupta, IIT KGP)
Lecture 18: Pipeline Algorithm for MST (Section 7.2 of the book)
Lecture 19: GKP Algorithm(Section 7.3 of the book)