Massively parallel algorithms for finding connected components

In this talk we consider the problem of finding connected components in a distributed setting. We present state of the art algorithms that achieve near-optimal round complexity and work well in practice. Our main focus is the Massively Parallel Computation (MPC) model, which is the standard theoretical model for modern parallel frameworks such as MapReduce, Hadoop, or Spark. This is joint work with Soheil Behnezhad, Laxman Dhulipala, Hossein Esfandiari, Vahab Mirrokni, Warren Schudy and Michał Włodarczyk.