Monday, May 28, 2012

Foundations of Parallel and Distributed Systems

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.

Some lecture references.

Previous Versions.

  • The 2009 site.
  • The 2006 site.
  • The 2005 273 website.
  • Other resources...

    No comments:

    Post a Comment