(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.