**Distributed
Algorithms (CS6851)**

Sai Sreenivas Kodur

Paresh Nakhe (ACT lab)

Nishaanth

Shrikant Polawar (ACT lab)

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.

__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.

There is no prescribed textbook for this course offering. The following books and web links are useful 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.

__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 v_{1}, v_{2}, ...v_{n}. Each node in
the array starts with an input value. We discussed a simple
algorithm that sorts the values such that the node v_{i}
outputs the value with the i^{th} 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.

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

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).

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

Wireless Communication and Networks by Dr. Siva Ram Murthy

Cloud Computing by Dr. D. Janakiram

Social Network Analysis by Dr. B. Ravindran

Concurrent Programming by Dr. Shankar Balachandran

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

Modern techniques in Theory of Computation by Dr. Raghavendra Rao

will be useful.