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

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

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

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

Scribing lecture notes | 40% |

Minor I | 15% |

Minor II | 15% |

Minor III | 15% |

Major | 15% |

- 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 "lec
*lec 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