<p>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.</p>

<p>See for instance work by Foto Afrati and Jeff Ullman: <a href="http://portal.acm.org/citation.cfm?id=1739041.1739056"><em>Optimizing joins in a map-reduce environment</em></a>, EDBT 2010. (<a href="http://infolab.stanford.edu/~ullman/pub/join-mr.pdf">preprint</a>)</p>

CC BY-SA 3.0
2011-04-30T22:18:23.063Z
2011-04-30T22:18:23.063Z
András Salamon
<p>Since in MapReduce there is a simple and structured graph underlying the computation, this can IMHO classified as a data-flow model.</p>

CC BY-SA 3.0
2011-05-04T11:40:16.630Z
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.
Beef
CC BY-SA 3.0
2011-04-30T06:15:55.433Z
2011-04-30T06:15:55.433Z
Massimo Cafaro
<p>In section 2 of <a href="http://arxiv.org/abs/1101.1902">http://arxiv.org/abs/1101.1902</a>, 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.</p>

CC BY-SA 3.0
2011-04-30T04:01:39.913Z
2011-04-30T04:01:39.913Z
Sasho Nikolov
<p>Is it accurate to call the <a href="http://en.wikipedia.org/wiki/MapReduce">mapReduce</a> framework a type of <a href="http://en.wikipedia.org/wiki/Bulk_Synchronous_Parallel">bulk synchronous parallel</a> programming framework with no local memory retention within processors between synchronizations? If not, what parallel programming model most accurately encapsulates the mapReduce framework?</p>

CC BY-SA 3.0
2011-04-29T23:37:32.947Z
that's a nice question !
Suresh Venkat
CC BY-SA 3.0
2011-04-30T01:03:21.843Z
thanks Suresh, what you think, agree?
Jeff Kubina
CC BY-SA 3.0
2011-05-04T12:31:18.700Z
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.
Jeff Kubina
<dc.parallel-comp><machine-models>
Is the MapReduce framework a type of BSP?
Jeff Kubina
# Is the MapReduce framework a type of BSP?

(Asked by: username_0 on 2011-04-29)

Is it accurate to call the [mapReduce](http://en.wikipedia.org/wiki/MapReduce) framework a type of [bulk synchronous parallel](http://en.wikipedia.org/wiki/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?

**Tags:** dc.parallel-comp, machine-models
> **Comments:**
> **username_1**: that's a nice question !  
> **username_0**: thanks Suresh, what you think, agree?  
> **username_0**: 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.  

---

## 3 answers

### Answer by username_5 on 2011-04-30. Score: 11 | Accepted answer

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.


---

### Answer by username_2 on 2011-04-30. Score: 5

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*](http://portal.acm.org/citation.cfm?id=1739041.1739056), EDBT 2010. ([preprint](http://infolab.stanford.edu/~ullman/pub/join-mr.pdf))


---

### Answer by username_3 on 2011-04-30. Score: 2

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

> **Comments:**
> **username_4**: 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.  

---

