Course title: MA651: Distributed Algorithms [3-0-0-6]
Instructor: Partha Sarathi Mandal[TEL: 2624, E-mail: psm]
Department of Mathematics, Indian Institute of Technology Guwahati
Semester: Jan - May '22
Lecture Time: Wednesday, Thursday, Friday: 4:00-4:55 PM
Class Room: Teams (online)
Contents: Click Here
Exams & Marking: Pop Quizzes* + Term Paper + viva voce + Midsem + Endsem
Class & policy: Minimum 75% attendance in class is must as per institute rule.
* Pop Quiz is a short test given in a class by the instructor, without prior announcement.
Texts:
  1. S. Ghosh, Distributed Systems: An Algorithmic Approach, 2nd Edition (Indian Reprint), CRC Press, 2015.
  2. David Peleg, Distributed Computing: A Locality-Sensitive Approach, SIAM Monographys on Discrete Mathematics and Applications, 2000.
  3. N. Lynch, Distributed Algorithms, Morgan Kaufmann, 1996.
References:
  1. M. V. Steen, A. Tanenbaum: Distributed Systems, 3rd Edition, Pearson 2017.
  2. H. Attiya and J. Welch. Distributed Computing: Fundamentals, Simulations, and Advanced Topics, Second Edition, Wiley, 2006.
  3. G. Tel, Introduction to Distributed Algorithms, Cambridge University Press 2000.
  4. A. Kshemkalyani, M. Singhal, Distributed Computing: Principles, Algorithms, and Systems, Cambridge University Press, 2007.
  5. V. K. Garg, Elements of Distributed Computing, Wiley & Sons, 2002.
Announcement:
  1. Lecture note for some of the topics is available here
Lecture Notes: __________________________________________________________________________________
Week 1 Lecture Notes 1 [Introduction to Distributed Systems] [Ref. 1, chapters 1 & 2] [Lecture Video]
Lecture Notes 2 [contd. Introduction] [Ref. 1, chapters 1 & 2] [Lecture Video]
Lecture Notes 3 [Models] [Ref. 1, chapter 3] [Lecture Video]
Week 2 Lecture Notes 4 [Model of communication] [Ref. 1, chapter 3] [Lecture Video]
Lecture Notes 5 [Model of Communication contd.] [Ref. 1, chapter 3] [Lecture Video]
Week 3 Lecture Notes 6 [Complexity Measures of Distributed Algorithms] [Ref. 1, chapter 3] [Lecture Video]
Lecture Notes 7 [Syntax & semantics, Atomicity, Non-determinism] [Ref. 1, chapter 4] [Lecture Video]
Week 4 Lecture Notes 8 [Contd. Atomicity, Fairness, Scheduler] [Ref. 1, chapter 4] [Lecture Video]
Lecture Notes 9 [Program correctness] [Ref. 1, chapter 5] [Lecture Video]
Week 5 Lecture Notes 10 [Program correctness contd.] [Ref. 1, chapter 5] [Lecture Video]
Lecture Notes 11 [Time in a Distributed System: Logical Clocks, Causal Ordering and Vector Clocks] [Ref. 1, chapter 6] [Paper] [Lecture Video]
Lecture Notes 12 [Distributed Snapshot and Global State Collection] [Ref. 1, chapter 8] [Paper] [Lecture Video]
Week 6 Lecture Notes 13 [Distributed Snapshot (Chandy Lamport Algorithm) contd.] [Ref. 1, chapter 8] [Lecture Video]
Week 7 Lecture Notes 14 [Clock Synchronization] [Ref. 1, chapter 6] [Paper] [Lecture Video]
Lecture Notes 15 [Distributed Mutual Exclusion] [Ref. 1, chapter 7] [Lecture Video]
Lecture Notes 16 [Distributed Mutual Exclusion Contd.] [Ref. 1, chapter 7] [Lecture Video]
Week 8 Lecture Notes 17 [Leader Election] [Ref. 1, chapter 11] [Lecture Video]
Lecture Notes 18 [Leader Election contd.] [Ref. 1, chapter 11] [Lecture Video]
Lecture Notes 19 [Termination Detection] [Ref. 1, chapter 9] [Lecture Video]
Week 9 Lecture Notes 20 [Distributed Deadlock Detection] [Ref. 1, chapter 9] [Lecture Video]
Lecture Notes 21 [Graph Algorithms: single source shortest path, Distance Vector Routing, Link State Routing] [Ref. 1, chapter 10] [Shortest Path by Chandy and Misra] [Lecture Video]
Week 10 Lecture Notes 22 [Interval Routing, Prefix Routing] [Ref. 1, chapter 10]
Lecture Notes 23 [Distributed spanning tree, Graph traversal] [Ref. 1, chapter 10]
Lecture Notes 24 [Distributed MST construction] [Ref. 1, chapter 10] [MST by GHS]
Week 11 Lecture Notes 25 [Distributed graph coloring] [Ref. 1, chapter 10]
Lecture Notes 26 [Coloring Tree in log*(n) time] [Ref. 1, chapter 10, Ref. 2, Chapter 7]
Lecture Notes 27 [Coloring Tree contd. Finding Maximal Independent Set (MIS) using Coloring] [Ref. 1, Chapter 10, Ref. 2, Chapter 8]
Week 12 Lecture Notes 28 [Randomized algorithm to find MIS] [Ref. 1, Chapter 10, Ref. 2, Chapter 8]
Lecture Notes 29 [Matching and Colouring using solution of MIS] [Ref. 1, chapter 10, Ref. 2, Chapter 8]
Lecture Notes 30 [Faults and Classification of Faults] [Ref. 1, Chapter 12]
Lecture Notes 31 [Failure detection and Fault-tolerance] [Ref. 1, Chapter 12]
Week 13 Lecture Notes 32 [Self-Stabilization] [Ref. 1, chapter 17] [Dijkstra 1974]
Lecture Notes 33 [Distributed Consensus and Byzantine General Problem] [Ref. 3, Chapter 5 and 6, Ref. 1, Chapter 13] [FLP 85] [Byzantine]
Lecture Notes 34 [The Paxos algorithm for distributed consensus] [Ref. 1, Chapter 13] [Paxos Made Simple]