CSL860: Special Topics in Parallel Computation: Routing in the Presence of Faults

I semester: 2008-09

Amitabha Bagchi

Class Timings: Tu W: 1:30PM to 3:30 PM.
Room: Bharti 204.

Topics

This class studies the effect of faults on the routing properties of networks. We largely focus on random fault models. Apart from routing, we will also study the more general problem of emulating a fault-free network on a faulty version of itself. We will formalize the routing problem and relate it to the expansion (isoperimetric constant) of a graph. We will introduce percolation as a model for the study of random faults and discuss some basic techniques of this area and their applicability to the study of routing. The square mesh will be primary network we will work with but we will also look at the butterfly and expanders. The class assumes only a basic working knowledge of probability and graph theory.

Lecture Breakup

Each lecture below is one hour, the actual class may be held in two 1.5 hour slots.

The communication model and fault models.	1 lecture.
Oblivious routing: congestion and dilation.	5 lectures.
Routing parameters: expansion, diameter.	6 lectures.
Emulation in the mesh.	3 lectures.
Intro to routing in the mesh with random faults.	2 lectures.
Percolation in the mesh: introduction.	10 lectures.
Routing in the percolated mesh.	3 lectures.
Expansion in percolated mesh.	3 lectures.
Routing in the butterfly.	2 lectures.
Percolation in expanders.	2 lectures.
Random geometric graphs.	3 lectures.

Notes

Lecture 1. (30/7, 5/8, 6/8): Introduction: Models for routing and faults (ps, pdf.)
Scribe: Amitabha Bagchi. Posted 15th August 2008.
Lecture 2. (12/8, 13/8): Introduction: Routing parameters: Diameter and expansion (ps, pdf.)
Scribes: Amandeep Singh, Aman Gupta. Posted 26th August 2008.
Lecture 3. (20/8, 26/8, 9/9): The effect of faults on expansion I: Adversarial faults. (ps, pdf.)
Scribe: Amitabha Bagchi. Posted 23rd September 2008.
Lecture 4. (11/9, 16/9, 17/9): The effect of faults on expansion II: Random faults. (ps, pdf.)
Scribe: Rajnish Dahiya, Amit Sharma. Posted 28th September 2008.
Lecture 5. (23/9, 24/9): Scheduling in networks and embeddings. (ps, pdf.)
Scribe: Md Tanveer Alam, Harsh Sanghvi. Posted 7th October 2008.
Lecture 6. (30/9, 1/10): Emulating a faulty mesh. (ps, pdf.)
Scribe: Neha Dahiya, Ravi Soni. Posted 2nd November 2008.
Lecture 7. (7/10, 14/10, 21/10): The critical probability of bond percolation in 2 dimensions is 1/2. (ps, pdf.)
Scribe: Nitin Gupta, Nimish J Oliapuram, Johannes Weißl, S. Anand. Posted 9th November 2008.
Lecture 8. (29/10): Emulating a faulty mesh up to the critical probability. (ps, pdf.)
Scribe: Johannes Weißl, S. Anand. Posted 6th November 2008.
Lecture 9. (4/11, 5/11): Emulating the faulty mesh with constant slowdown. (ps, pdf.)
Scribe: Lukas Schwaighofer. Posted 9th November 2008.

Other lecture materials

T. Mathies.
Percolation theory and computing with faulty arrays of processors.
Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms. pp 100 - 103, 1992.
C. Kaklamanis, A. R. Karlin, F. T. Leighton, V. Milenkovic, P. Raghavan, S. Rao, C. D. Thomborson, A. Tsantilas.
Asymptotically Tight Bounds for Computing with Faulty Arrays of Processors (Extended Abstract).
31st Annual Symposium on Foundations of Computer Science. pp 285-296. 1990.
R. J. Cole, B. M. Maggs, R. K. Sitaraman
Reconfiguring Arrays with Faults Part I: Worst-Case Faults.
SIAM J. Computing 26(6):1581-1611, 1997.

Assignments and Exams

Minor 1. (ps, pdf). Posted 3rd September 2008. Revised 6th September.
Handwritten: Due in my office before 11AM on Monday, 8th September 2008. Latexed: Due at the beginning of class on Tuesday, 9th September 2008.
Minor 2. (ps, pdf). Posted 26th September 2008.
Due in my office before 12PM on Thursday, 2nd October 2008.

Evaluation

Scribing lecture notes	40%
Minor I	15%
Minor II	15%
Minor III	15%
Major	15%

Scribing

Each student will be expected to scribe at least one lecture. This will involve taking careful and complete notes during the lecture and then typing them out in latex.
Please download the template file and the latex class file that will be needed. As a sample the tex file for the first lecture (along with the figure files) can be downloaded as a tar file from here (local access only).
Important. I have put up some typesetting instructions. Please follow them. This document will keep evolving so please check back before you start scribing.
Note that all figures must be made in xfig. Please prepend the string "leclec no-" to the name of each figure e.g. lec3-lower-bound.fig could be a file name if you are scribing lecture 3. Send me the .fig files along with all other files.
Please read the instructions for rendering latex fonts in figures made with xfig.
Three days after the lecture the first draft will be due. This will have to be emailed to Dr Bagchi.
The instructor will return the draft with comments and, three days after that, a final version will have to be made and submitted with all the required changes incorporated.
Here are some general guidelines which may help you with scribing class notes. Please read them before you begin typing. Also refer to some rules for coherent writing to help you along.
Some latex tips here.

Amitabha Bagchi