CSL860: Theory of Network Communication
II semester: 2005-06
Class Timings: 3:30PM to 5PM, Tuesdays and Wednesdays.
Room: VI 403.
Minor I: 4PM to 5PM,
Monday, 20th Feb.
Room: V 315.
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
- 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.
- List of papers with assignments and
dates of presentation. Also slides from completed presentations are
posted on this page.
- Presentation guidelines for readers
- Presentation schedule. Please take a
look at the available dates and decide which will be convenient for
We will assign dates in class on Tuesday, the 14th of
Feb (yes, you will get a date on the 14th of Feb this
- On the 14th of Feb and 15th of
Feb I will be available between 2PM and
3:30PM to discuss your presentation
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.
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
- Presentation(s): 40%.
- Presentation report: 10%.
- Discussion participation: 20%.
- I Minor Exam: 10%.
- II Minor Exam: 10%.
- Major Exam: 10%.