Welcome

Thank you for your interest in this GIAN course (161003K01) on distributed network algorithms.

Instructors: Gopal Pandurangan and John Augustine
Teaching Assistants: William Kumar Moses Jr. (Billy) and Anisur Rahaman Molla
Venue: Mechanical Sciences Block (MSB) 360, IIT Madras (click here for location in map)
Dates: Aug 1 - 5, Aug 8 - 12, 2016 (See map)
Time: 4 - 7PM (with a break in the middle)
Contact Details: Email John Augustine (see http://www.cse.iitm.ac.in/~augustine/ for contact details.)

Credits for IIT Madras students: 2 credits (under the old system).


Registering for the Course

  1. Enroll at the GIAN portal. There will be a one-time enrollment fee of Rs. 500 after which you can apply for participation in any GIAN course.
  2. Register for the course at the GIAN portal. Note that this is course specific. You will have to sign in and register for "161003K01 : Distributed Network Algorithms: Foundations and Future Directions".
  3. Email me (see http://www.cse.iitm.ac.in/~augustine/ for contact details) saying that you have registered for this course. Add information about your educational background and interests that you think is relevant. I will shortlist you if I think you will benefit from the course.
  4. If you are shortlisted:
    1. Mail me (or hand over in person) the course registration fee as a DD drawn in favour of "Registrar, IIT Madras" payable at Chennai. My address is given below. The fee structure is Rs. 2000 for students, Rs. 5000 for faculty members, Rs. 10,000 for Govt. of India research organization participants, and Rs. 15,000 for industry participants.
    2. The  participants  may be  provided  with  hostel  accommodation, depending on the availability, on payment basis. Request for hostel accommodation  may be submitted through the link: <http://hosteldine.iitm.ac.in/iitmhostel>. You may incur some boarding and lodging charges. I urge you to apply asap.
Address to send DD (please send by registered post or courier):
Dr. John Augustine
Dept. of Computer Science and Engineering
IIT Madras, Chennai, TN - 600036.

                  

Contents of the Course

The course is divided into two modules. A series of lecture notes will be posted here as the course progresses.

Module 1: Foundations

We will present a variety of fundamental distributed network algorithms including broadcast, convergecast, maximal independent set, coloring, leader election, spanning tree algorithms, shortest paths, and routing. Fundamental concepts in distributed algorithms  including symmetry breaking, locality, cover construction, and synchronizers will be covered. Basic issues arising in distributed network systems such as communication, synchronization, fault-tolerance, and resource allocation will be addressed. Applications to real-world networks such as the Internet, peer-to-peer networks, wireless networks, sensor networks and dynamic networks will also be discussed.

Module 2: Future Directions

We will present state-of-the-art research topics and future research directions in distributed network algorithms. The course will cover the following topics that have seen significant new developments in the last five years: (1) techniques for showing lower bounds of distributed algorithms using communication complexity, (2)  distributed computation of large-scale data, and (3) dynamic network algorithms.

The course topics will be covered in a self-contained manner that will make the concepts accessible to those that don't have prior background in distributed algorithms.

Email List

We will be using https://groups.google.com/forum/#!forum/gian-dna-ffd-2016 as a mailing list. Please join for important emails, group discussions, etc.

List of Topics

 Day Topics (tentative) Notes and references Exercises 
 1 Introductory concepts: models, complexity measures, and fundamental algorithms  pdf Hw1:  Exercises 3.6,3.7,4.3
Due:  Aug. 4.
 2 Leader election, randomization  pdf  Hw2: Exercises 5.2. 5.6, 5.11,
         Bonus: Exercise 5.7
Due: Aug. 8.
Symmetry breaking: maximal independent set and colouring algorithms  pdf  Hw3: Exercises 6.1 (bonus), 6.4, 6.8, 6.9
Due: Aug. 10
Minimum spanning tree algorithms  pdf  
Agreement protocols and barriers: synchronous and asynchronous networks  Handout given in class
 
Byzantine agreement and leader election     
Lower bounds in distributed algorithms: Part 1  paper
 slides
 
8 Lower bounds in distributed algorithms: Part 2  paper1
 paper2
 FINAL EXAM
 Due: Aug. 12 (4pm).
Distributed Big Data: models and algorithms  lecture notes    
 paper1
 paper2
 slides 
 
10 Dynamic networks: models and algorithms paper 
slides
 

Grading Policy

All registered participants will receive a course participation certificate. In addition, registered participants can also choose to credit the course; this is a two credit course. You will be required to submit assignments and take the exam if (and only if) you credit the course. Therefore, the grading policy is only relevant to those participants who are crediting this course. IIT Madras students may be able to apply the credits towards their regular institute credits.

Given the short duration of the course, the final exam will mostly focus on your ability to absorb the material and less on problem solving. Homework may include problem solving, but will be reasonably short given the short duration of the course. 

Homework: 50%

Final Exam: 50%