Massively Parallel Algorithms, ETH Zurich, Spring 2019


Instructor: Prof. Mohsen Ghaffari
Units: 2V+1U+2A = 6CP
Lecture Time & Place: Fridays 10:00-12:00 at CAB G51
Exercise Session Time & Place: Fridays 17:00-18:00 at CAB G59
Grading: A semester-long project, delivered in three parts: an initial proposal (20%), a presentation (20%), and final report (60%).
Other Links: Information on the Course Catalogue of ETH Zurich

Course Content: Data sets are growing faster than the capacity of single processors. This makes it almost a certainty that the future of computation relies on parallelism. In this new graduate-level course, we study the theoretical foundations of modern parallel computation, with an emphasis on the algorithmic tools and techniques. In particular, we will discuss the growing body of algorithmic results in the Massively Parallel Computation (MPC) model. This model is a mathematical abstraction of some of the popular large-scale data processing settings such as MapReduce, Hadoop, Spark, etc. The course will cover a sampling of the recent developments (and open questions) at the frontier of research in massively/modern parallel algorithms. The related papers will be provided throughout the semester. By the end of the semester, the students will know all the standard tools of this area, as well as the state of the art on a number of the central problems. Our hope is that the course prepares the students for independent research in this area, and we will take concrete steps in that direction with the course projects.

Tentative Topics: Massively parallel algorithms for various problems including sorting, maximum matching approximations, maximal independent set, connected components, minimum spanning tree, minimum cut, graph coloring, geometric problems, some dynamic programming problems, various clusterings, submodular maximization, triangle counting, densest subgraph, and coreness decomposition, as well as some impossibility results and conditional lower bounds and some discussion of composobale coresets.

Prerequisite: The class does not assume any prior knowledge in parallel algorithms/computing. Our only prerequisite is the undergraduate class Algorithms, Probability, and Computing (APC) or any other course that can be seen as the equivalent. In particular, much of what we will discuss uses randomized algorithms and therefore, we will assume that the students are familiar and comfortable with the basic tools and techniques in randomized algorithms and analysis (to the extent covered in the APC class). Please check Problem Set 0 to see if you are comfortable with the required background material. If you're not sure whether you're ready for this class, please consult with the instructor.

 

Projects:

Step 1 --- Proposals: We have had one-on-one meetings with each of the teams regarding project proposals. If you need another meeting, please send me an email. Your final project proposals should be submitted (via email to ghaffari@inf.ethz.ch) by the midnight of Monday, April 8. Please see the email from March 25 regarding guidlines for the proposal.

Step 2 --- Presentations: We will have the presentations on July 24 in CAB G51. Details and the schedule will be announced later.

Step 3 --- Final Reports: The final reports should be submitted (via email to ghaffari@inf.ethz.ch) by August 15.


Here is a compilation of the scribe notes, courtesy of Davin Choo. These notes will be updated regularly, throughout the semester. Last Update: June 19, 2019.

Lectures: