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.


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.


Other lecture materials

Assignments and Exams


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


Amitabha Bagchi