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)
Consensus Link failure (Based on the Book by Nancy Lynch)
Consensus Crash Failure(Based on the lecure note by Roger Wattenhofer)
Consensus Byzantine Failure Slide 1 and Slide 2 (Lecture note credit: Dr. Avery Miller, University of Manitoba )
Consensus Byzantine Failure algorithms (Based on the lecure note by Roger Wattenhofer)
Consensus process failure: impossibility with f rounds proof for f=1 (Based on the Book by Nancy Lynch)