CS6851 - Distributed Algorithms

Course Data :

Syllabus:

  • Review of Prerequisite Topics: Graph theory, probability theory covering Markov's inequality, Chebyshev's inequality, Chernoff bounds, Markov chains and random walks.
  • Models for Distributed Computer Networks: Message passing and shared memory models, synchronous and asynchronous timing models, failure models. Complexity measures like time, space, and message complexity.
  • Fundamental Problems on Distributed Networks: Maximal independent set, minimum spanning tree, vertex colouring, dominating set, routing algorithms, leader election, Byzantine agreement, synchronizers, graph spanners, dynamic networks.
  • Application Specific Problems: Storage and retrieval of data in peer-to-peer computing, coverage and routing in sensor networks, and rumour spreading in social networking.

References

  • Distributed Computing: a Locality-Sensitive Approach, by David Peleg.
  • Distributed Algorithms, by Nancy Lynch.
  • Distributed Computing: Fundamentals, Simulations, and Advanced Topics, by Hagit Attiya and Jennifer Welch.
  • Randomized Algorithms, by Rajeev Motwani and Prabhakar Raghavan.
  • Principles of Distributed Computing, lecture notes by Roger Wattenhofer.

Pre-Requisites

    None

Parameters

Credits Type Date of Introduction
3-1-0-4 Elective Jan 2013

Previous Instances of the Course


© 2016 - All Rights Reserved - Dept of CSE, IIT Madras
Website Credits