# CSL860: Theory of Network Communication

# II semester: 2005-06

# Amitabha Bagchi

**Class Timings:** 3:30PM to 5PM, Tuesdays and Wednesdays.

**Room:** VI 403.

**Minor I:** 4PM to 5PM,
Monday, 20th Feb.

**Room:** V 315.

### Topics

This class will cover topics in the theory of communication in
distributed systems. The course is visualized as part lecture, part
reading group. Approximately one-third of the class will be devoted to
reading and presenting research papers.
Some knowledge of probability theory will be required, but a refresher
of the probability tools used in the class will be provided in the
beginning.

### Lecture Breakup

**Review of probability theory**. 3 lectures.
**Communication models**. 2 lectures.
**Oblivious routing**. 2 lectures.
**Routing parameters and offline routing**. 4 lectures.
**Edge disjoint paths**. 2 lectures.
**Robust routing: Edge faults**. 2 lectures.
**Robust routing: Node faults**. 4 lectures.
**Sorting networks**. 2 lectures.
**Peer-to-peer networks**. 2 lectures.
**Hashing for content distribution**. 2 lectures.
**Caching**. 2 lectures.

### Presentations

- List of papers with assignments and
dates of presentation. Also
**slides from completed presentations** are
posted on this page.
- Presentation guidelines for readers
and discussants.
- Presentation schedule. Please take a
look at the available dates and decide which will be convenient for
you.

We will assign dates in class on **Tuesday, the 14th of
Feb** (yes, you will get a date on the 14th of Feb this
year).
- On the
**14th of Feb** and **15th of
Feb** I will be available between **2PM and
3:30PM** to discuss your presentation
plans.

**This discussion is mandatory.**

Please fix an alternate date or time with me if this isn't
convenient. You are **required** to meet me **at least
one week before** your presentation.

### Minor syllabus

For the first minor you will be expected to know the introductory
material covered in class (routing in a cycle, congestion and dilation,
routing parameters up to the definition of the flow number, oblivious
routing.) Some knowledge of probability (including tail inequalities like
Chernoff bounds) will be assumed but I will include all required
formulae (if any) in the exam paper.
### Notes and other lecture materials

### Evaluation

- Presentation(s): 40%.
- Presentation report: 10%.
- Discussion participation: 20%.
- I Minor Exam: 10%.
- II Minor Exam: 10%.
- Major Exam: 10%.

Amitabha Bagchi