11
$\begingroup$

Is it accurate to call the mapReduce framework a type of bulk synchronous parallel programming framework with no local memory retention within processors between synchronizations? If not, what parallel programming model most accurately encapsulates the mapReduce framework?

$\endgroup$
  • 1
    $\begingroup$ that's a nice question ! $\endgroup$ – Suresh Venkat Apr 29 '11 at 23:37
  • $\begingroup$ thanks Suresh, what you think, agree? $\endgroup$ – Jeff Kubina Apr 30 '11 at 1:03
  • $\begingroup$ tough choice on selecting the best answer since I think they all helped me gain more knowledge about mapreduce and how others view it. i chose Sasho's answer since it led me to a paper that address's my question the best. thanks everyone. $\endgroup$ – Jeff Kubina May 4 '11 at 12:31
11
$\begingroup$

In section 2 of http://arxiv.org/abs/1101.1902, the authors define a model of MapReduce that is intentionally structured like BSP. They prove simulation theorems as well. May be a good place to start.

$\endgroup$
5
$\begingroup$

Yes, my opinion is that classical MapReduce is a BSP model (and therefore has its inherent limitations on the maximum possible parallel performance that can be achieved). However, newer work on MapReduce seems to be focused on looser notions of synchronization, which would take this "generalized MapReduce" out of the strict BSP framework. In particular, if one replicates some of the data then the synchronization structure can be relaxed, yielding performance gains.

See for instance work by Foto Afrati and Jeff Ullman: Optimizing joins in a map-reduce environment, EDBT 2010. (preprint)

$\endgroup$
2
$\begingroup$

Since in MapReduce there is a simple and structured graph underlying the computation, this can IMHO classified as a data-flow model.

$\endgroup$
  • $\begingroup$ I agree, MapReduce has the same computation strategy as a tagged-dataflow machine. Yahoo's Pig language even builds a dataflow language on top of MapReduce. $\endgroup$ – Beef May 4 '11 at 11:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.