CS273: Foundations of Parallel and Distributed Systems

INSTRUCTORS:
Lecturer: Satish Rao (satishr@cs.berkeley.edu)
Office hours (tentative): Mo: 1:30-2:30, Th: 2-3.
TA: Isabelle Stanton
Office hours (tentative): Tu: 11-12, Fr: 2-3.
Fundamental theoretical issues in designing parallel algorithms and architectures and topics in distributed networks. Shared memory models of parallel computation. Parallel algorithms. Fundamentals of routing for general networks. Algorithms for object location in distributed networks. Partitioning methods. Distributed computing. Game theoretic aspects of distributed agents. Foundations of Game Theory. On-line auctions.

Administration

Homeworks, a project, perhaps a final will determine your grade. The course is more front loaded than other courses, so be sure to get your work done as it is posted.

Project.

Choose a paper or propose a "paper to be" related to the topics we will present in this course. It should have a significant theory/analysis component or suggest such a direction. You should propose to either understand or extend the paper. You should be prepared to present and summarize the contents of the paper including sufficient relevant background. Proposals are due September 12, 2010.

Homework Guidelines

The point of homeworks is to learn the material well. Please do so.

Homeworks/Lecture Notes.

Lecture 1. Introduction. Load Balancing. In ps or pdf
Lecture 2. Power of two choices. In ps or pdf
Lecture 3. Expectation. In ps or pdf
Lecture 4. Markov, Chebyshev, and Chernoff/Hoeffding. In ps or pdf
Lecture 5. BSP Computing. Linear Relaxation. (Sparse Matrix-Vector multiply. In ps or pdf
Lecture 6/7. Planar Separator Theorem. In ps or pdf
Lecture 8/9. Hypercube, butterfly, route selection. In ps or pdf
Lecture 10/11/12. Scheduling, random priorities, bounded queues. In ps or pdf
Lecture 12/13. Random delays, Lovasz Local Lemma, $O(C+D)$ scheduling..(nearly). In ps or pdf
Lecture 14. General Path Selection, Linear Programming, Path Selection In ps or pdf
Lecture 15. Path Routing. Shortest path with exponential penalties. In ps or pdf
Lecture 16/17. Experts, Zero-Sum Games, LP games. In ps or pdf
Lecture 18. The PRAM. In ps or pdf
Lecture 19/20. The PRAM. In ps or pdf
Lecture 20/21. The PRAM: Complexity In ps or pdf
Lecture 22. Distributed Coloring. In ps or pdf
Lecture 23/24. Matching in NC, Sorting. In ps or pdf
Lecture 25. Distributed Computing. In ps or pdf
Lecture 26. Graph Partitioning. Pieced together from lectures here , here and here .
Lecture 27. Iterative linear systems. Taken from here .
Lecture 28. Pieced together from here. Just did Arrow's theorem. Did not go into Algorithmic Mechanism Design.