Massively Parallel Computation
Krzysztof Nowicki
(University of Copenhagen (DIKU));
Course Summary |
About the lecturer |
Location and schedule
| Assignment
The Massively Parallel Compution model (MPC) is a model used for studying complexity of parallel algorithms for big data sets (e.g. algorithms for frameworks like MapReduce, Hadoop, or Spark). In this model, computation is performed by a set of machines in synchronous rounds (each round consists of a phase of local computation and a phase of communication). While designing MPC algorithms, given an upper bound S on the local memory of a single machine, we try to minimize the number of rounds needed by the algorithm to finish the computation. For graph problems, we distinguish three different variants (memory regimes) of MPC, defined by the relation between the local memory S and the number of vertices of the input graph n (S >> n, S~n, S << n), mainly because the algorithmic techniques applicable to those three variants are quite different, and because the algorithms using smaller memory usualy require larger number of rounds. In this course, we will discuss the techniques used to desing the state of the art algorithms for three fundamental graph problems: Minimum Spanning Tree, Maximal Matching, and Maximal Independent Set. More precisely, for each of those problems we will discuss the algorithms in all three memory regimes of MPC, which hopefully will shed some light on the similarities / differences between them.
About the lecturer: Krzysztof Nowicki is possibly the youngest speaker in the history of the PhD Open program. He received the Witold Lipski Prize for young Computer scientists in 2020 for his achievements in the area of parallel and distributed algorithms. He obtained his PhD from the University of Wrocław in February 2021. The reviewer Professor David Peleg from the Weizmann Institute wrote, among others, that the contributions "constitute a significant progress over the best-known results to date" and recommended "an excellence prize". Krzysztof Nowicki published at the topmost conferences in the area, including STOC, SODA, PODC, and DISC. Location and schedule:ZOOM registration. The lectures will be recorded and posted below after each lecture.
|
|
|
||||||||||||||||||