Distributed Algorithms (CS6851)

Term: Jan - May, 2013

Instructor: John Augustine

Class Meeting Schedule: Wednesdays 11-11:50 + Thursdays 2 – 3:50 PM (with a break) + 1 discussion hour (~50 minutes)

Teaching Assistants:





Brief Description:

We live in the Internet age when computers that are distributed geographically can communicate with each other and perform meaningful computation. This course will focus on one of the key drivers for building theses large distributed systems, namely, the design and analysis of efficient distributed algorithms.

In order to focus on the algorithmic aspects of distributed computing, we will first abstract out some key theoretical models that capture essential features of real world distributed systems. We will then present algorithms for some fundamental problems that arise in distributed computing environments and mathematically analyze their correctness and efficiency.

Course Contents:

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

There is no prescribed textbook for this course offering. The following books and web links are useful references.



Lectures

Jan 15 – 18: Introduction to probability theory.

Lectures were delivered by Sumathi and Billy. (Thanks.)

Jan 21 – 25: Class cancelled.

Visitors Wendy Hall and Vint Cerf gave lectures on Web Science and The Future of The Internet, resp.

Jan 28 – Feb 1: Introduction to Distributed Algorithms.

Various models and complexity measures were discussed with special emphasis on the CONGEST model. Reference: Chapters 1 and 2 of Peleg's book.

Feb 4 – 8: The Agreement Problem.

The agreement problem was defined and various lower bounds and impossibility results were discussed. The lower bound on the number of rounds required in a faulty synchronous network was taken from Attiya and Welch's book (Chap 5). The impossibility of agreement in asynchronous shared memory model (and message passing mode) were based on Lynch's book (Chap 12). My own handwritten notes are available, but use at your own risk. The randomized algorithm for byzantine agreement (with access to a global coin) was taken from Motwani and Raghavan (Chap 12).

Feb 11 – 15: Routing Algorithms.

We discussed various distributed routing algorithms. Reference: Theory of Communication Networks by Pandurangan and Khan. We discussed the Link State Algorithm, the Distributed Bellman-Ford Algorithm (aka the Distance Vector Algorithm), and the Gallagher-Humblet-Spira algorithm for computing the Minimum Spanning Tree of a network.

Feb 18 – 22: Leader Election.

We discussed various leader election algorithms on rings (from Lynch's book, Chapter 3). We also discussed Peleg's algorithm taken from Time-Optimal Leader Election in General Networks, J. Parallel Distrib. Comput. 8(1): 96-99 (1990).

Feb 25 – 28: Maximal Independent Set.

We discussed two algorithms for computing the Maximal Independant Set. Reference: notes by Wattenhofer (Chap 7) and my own notes based on notes Pandurangan shared with me.

Mar 4 – 8: Vertex Colouring.

We discussed a neat transformation of the underlying network graph G into a modified graph G' such that an MIS on G' (simulated by the nodes in G) gave us a (Δ+1)-colouring in G. (Here, Δ is maximum degree in G.) Then, we discussed a much faster 3-colouring algorithm on rooted oriented trees; this algorithm only requires O(log* n) rounds. We also started proving that vertex colouring requires Ω(log* n) rounds. We will complete this proof next week. The material is taken from Peleg's book (Chap. 7)) and Wattenhofer's notes (chapters on vertex colouring, MIS, and locality lower bounds).

Dynamic Networks.

While the world of static networks is fairly well-studied, our understanding of networks that change over time is limited. In a sense, we have already seen dynamism in the form of fault tolerance, but we are interested in understanding algorithms designed for networks that are perpetually changing. With this in mind, we defined a suitable notion of a dynamic graph/network in which the nodes remain fixed, but the edges can change dramatically from round to round. We covered the entire chapter on dynamic networks in Wattenhofer's notes.

Peer-To-Peer (p2p) Networks.

We began with a discussion on what constituted p2p networks --- in essence boiling down to networks that accomplish meaningful tasks despite the lack of a central authority. ( I must admit that this definition is a bit biased by my own interests.) Furthermore, these are systems characterised by heavy node churn, i.e., a form of network dynamism in which a large number of nodes enter (i.e., log into the network) and leave (i.e., log out of the network) every round. This means that we must design algorithms that can tolerate churn. In this context, we discussed some recent work that tackled the agreement problem in networks that experience very heavy churn. A copy of the paper that we mainly focussed on was sent to the course students via email.

Distributed Sorting and Sorting Networks.

We saw a simple form of distributed sorting in which the network is an array of nodes v1, v2, ...vn. Each node in the array starts with an input value. We discussed a simple algorithm that sorts the values such that the node vi outputs the value with the ith rank. Perhaps more interestingly, we studied a lemma that simplified our analysis quite a bit by allowing us to focus only on binary input values. A sorting network takes n input wires, each with some value and outputs them in sorted order employing comparators to swap values on wires. We discussed the Batcher sorting network and analyzed it, again making use of the convenient lemma. We covered the odd/even sort on arrays and the section on sorting networks in the chapter titled “Distributed Sorting” in Wattenhofer's notes.

Assignments:

  1. Assignment 1 due on March 20 at 11AM (before class starts).

Discussion Hour:

There will be three (or four) discussion hours scheduled at various times of the week. In each of these hours, we will discuss papers centering on a well-defined topic (within distributed algorithms, of course). Each student must regularly attend and participate in one such hour. You must choose your discussion hour based on your interest level in the topic of discussion (and other scheduling constraints that you might have).





Other Related Courses:

There are several other related (elective) courses offered this semester at CSE.

I encourage students interested in parallel/distributed computing to discuss with each of these faculty members. All these courses are purposefully scheduled in different time slots, so you can take more than one of these courses if you so desire.

From a theory perspective, the course

will be useful.