CS 253: Design and Analysis of Communication Networks

Instructor: Eli Upfal

When: TuTh 1-2:20
Where: CIT 506
TA: Kee-Eung Kim
Newsgroup: brown.cs.cs253

SLIDES:

• Class 1
• Class 2
• Class 3
• Class 4
• Class 5
• Class 6
• Class 7
• Class 8
• Class 9
• Shared Memory
• Multibutterfly
• Dynamic Analysis

PAPER PRESENTATIONS:

• Hastad et al., Fast Computation Using Faulty Hypercubes [Joel Young, slides in ps, pdf]
  Peleg and Upfal, A Time-Randomness Trade-Off for Oblivious Routing [Ying Xing, slides in ps]
• Don and Stu
• Hajek, Bounds on Evacuation Time for Deflection Routing [Jasminka Hasic, slides in ps, pdf]
• Peleg and Upfal, The Token Distribution Problem [Shaoqing Shi, slides in ps, pdf]
  Maggs and Sitaraman, Simple Algorithms for Routing on Butterfly Networks with Bounded Queues [Yu Bai, slides in ps, pdf]
• Aiello et al., Fast algorithms for Bit-Serial Routing on a Hypercube [Hui-Yuan Song, slides in pdf]
  Ranade, How to Emulate Shared Memory [Thomas Crulli, slides in ps, pdf]

HOMEWORK ASSIGNMENTS:

• Homework Assignment 1 (Due 2/24) [Updated on 2/17]
• Homework Assignment 2 (Due 4/4)

REFERENCES:

• F.T. Leighton. ``Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes''. Morgan Kaufmann Publishers, Inc., California, 1992.