What are the limitations of map reduce in the sense of the types of computations

Question

What are the limitations of map reduce in the sense of the types of computations that they can express? Is Map Reduce "turning complete"?

I have been told that map reduce only works on things that can be expressed in the Map and Reduce framework, but my question is, why can't everything be expressed like that?

This might be the reason why Distributed Shared Memory systems like tread marks or IVY started to exist. So that we could express general programs and deal with them in a distributed computing manner.

Can someone give me an example of a task that can be done in a DMS and one that cannot be in map reduce? Or maybe, is there a formal theorem or proof showing what things can't be done in MapReduce but that a general programing language can do? What are the inherit limitations of Map Reduce and why are they the way it is?

Explanation / Answer

In MapReduce you take a big computation and split it up into many small computations that are done in paralell and that don't depend on one another. That way you can use many cores and if one calculation fails you dont have to redo the entire job, just that small task.

But if you have a problem that cant be broken down in to sub-problems that are independent of one another or dependant on some global state, then your stuck with doing one long big computation and loose the benefits of MapReduce.

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.