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