#
A Model of Computation for MapReduce

##
Dmitri Arkhipov

(a SODA 2010 paper by Howard Karloff, Siddharth Suri, Sergei Vassilvitski)

This paper introduces a computational model for MapReduce called the
MapReduce
computation model MRC. The paper presents a technique for
parallelizing a strictly defined class of functions within the MRC
model by decomposing such functions into map and reduce operations
implementable within MPC. This technique is used to prove that any
concurrent read exclusive write parallel random access machine (CREW
PRAM) can be efficiently run on a system implementing MapReduce if
the
memory/processor constraints of their model are satisfied. Lastly,
the
researchers show that in some cases more efficient MRC algorithms may
be designed than existing algorithms in PRAMs.