Massively parallel communication

This article is about a theoretical model for parallel algorithms. For the general concept of computing with many parallel devices, see massively parallel.

In the study of parallel algorithms, the massively parallel communication model or MPC model is a theoretical model of computing, intended as an abstraction for parallel computing systems that use frameworks such as MapReduce, and frequently applied to algorithmic problems in graph theory.

Model

In this model, one is given a system consisting of $M$ machines, each having a local memory consisting of $S$ words of memory. The input to a computational problem in this model is distributed arbitrarily across all of the machines, and is assumed to have a size $N$ at most proportional to $MS$. Typically one assumes that $S=N^{1-\varepsilon }$, for some parameter $\varepsilon >0$, so that each machine can see only a small fraction of the input and some nontrivial level of parallelism will be required to solve the given problem.

With this setup, computation proceeds in a sequence of rounds. In each round, each machine performs some local computation with the information it has in its memory, and then exchanges messages with other machines. The total amount of information sent or received by a single machine in a single round of communication must be $O(S)$. The goal in designing algorithms for this model is to achieve a very small number of rounds, such as a constant number or a number that is logarithmic in the input size.

History and relation to other models

An initial version of this model was introduced, under the MapReduce name, in a 2010 paper by Howard Karloff, Siddharth Suri, and Sergei Vassilvitskii. As they and others showed, it is possible to simulate algorithms for other models of parallel computation, including the bulk synchronous parallel model and the parallel RAM, in the massively parallel communication model. The name massively parallel communication was given to this model in a subsequent refinement by Beame, Koutris, and Suciu.

Example: sorting

Goodrich et al. provide the following example of an algorithm in this model, for sorting $n$ values, distributed to $O({\sqrt {n}})$ machines having memory size $O({\sqrt {n}})$.

1. Select a random sample of $O({\sqrt {n}})$ of the input values, collect them on a single machine, and sort them.

2. 

   A butterfly network containing many replicated copies of a balanced binary tree (one of which is highlighted in red)

   Build a balanced binary search tree on the sorted sample values, replicate the nodes at higher levels of this tree to form a butterfly network with $O({\sqrt {n}})$ nodes at each level of the network (including one copy of each leaf), and distribute the replicated copies so that each machine gets one copy of a node at each level.
3. Distribute the inputs of the sorting problem randomly to the replicated copies of the root nodes of the binary search tree, so that with high probability each copy of the root node is assigned $O({\sqrt {n}})$ values.
4. In a sequence of logarithmically many rounds, one round per level of the binary search tree, propagate each input value down through the tree, until they are eventually grouped into buckets at each leaf of the tree, with each bucket stored on a single machine and with $O({\sqrt {n}})$ values per bucket with high probability.
5. Sort each bucket locally.

The resulting algorithm succeeds with high probability in $O(\log n)$ rounds of computation, using total work $O(n\log n)$, matching the amount of work needed for sequential sorting algorithms.

See also

• 1-vs-2 cycles problem, a simplified graph connectivity problem whose conjectured hardness has been used for lower bounds in this model