Abstract: The Massively Parallel Computation (MPC) model was inspired by several modern distributed computation frameworks, including MapReduce and Pregel. In this talk we compare the MPC model with the computation frameworks it captures and discuss how it relates to practical large-scale computation. Moreover, we present an extension of the MPC model, called Adaptive Massively Parallel Computation (AMPC), which models a combination of MapReduce and a distributed key-value store. We show that AMPC admits constant-round algorithms for several prominent algorithmic problems, and the corresponding implementations are highly effective in practice.

Abstract: Connectivity, spanning forest, and minimum spanning tree are fundamental algorithmic problems. They are used as subroutines in many algorithmic settings, and so it is especially important that algorithms for these problems be as fast as possible.

A recent line of research in the Massively Parallel Computation (MPC) model, with low local space per machine, has led to a significant improvement in the complexity of the state-of-the-art algorithms for these problems; and further work derandomized these algorithms without any asymptotic loss of complexity. Additionally, recent research has led to conditional lower bounds for connectivity and spanning tree which nearly match the complexity of the best known algorithms.

In this talk, we discuss this line of work, the techniques and challenges involved, and conclude with a discussion of interesting open problems.

Abstract: The Massively Parallel Computation model has risen to popularity in recent years, accompanied by an array of very fast algorithms for classic graph problems. Until recently, however, no meaningful lower bounds for the model were known. While there is evidence that we cannot currently hope for unconditional lower bounds, a framework introduced by Ghaffari, Kuhn and Uitto (FOCS ’19) and revised by Czumaj, Davies and Parter (PODC ’21) allowed a host of lower bounds from the LOCAL model to be transferred to low-space MPC, conditioned on the hardness of a simple connectivity problem.

However, the latter also showed that these bounds are subject to some important technical caveats relating to the concept of “component-stability”, and that in some cases they can be surpassed by component-unstable algorithms. In this talk, we will survey the current status of lower bounds in low-space MPC, where they do and do not hold, and whether there is scope to find more robust bounds.

Abstract: Even though the MPC model is expected to be much more powerful than distributed models such as the local or congest models, so far most of a vast majority of results in this model are limited to local problems. Shortest path computation is one of the most fundamental examples of such global problems that is still quite challenging in MPC, specially in the more restrictive low memory settings. In this talk I explain some directions for tackling this important problem using distance structures such as spanners, hopsets and distance sketches. I will also explain how these objects are used in related models (such as PRAM and Congested Clique) and describe the obstacles we face in getting faster MPC algorithms using the existing algorithmic toolkit.