Theoretical model for parallel algorithms
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 formula_1 machines, each having a local memory consisting of formula_2 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 formula_3 at most proportional to formula_4. Typically one assumes that formula_5, for some parameter formula_6, 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 formula_7. 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 formula_8 values, distributed to formula_9 machines having memory size formula_9.
The resulting algorithm succeeds with high probability in formula_15 rounds of computation, using total work formula_16, matching the amount of work needed for sequential sorting algorithms.
References.
 ;templatestyles src="Reflist/styles.css" / ;