Why can't every computation be expressed in the style of MapReduce?

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?

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

But if you have a problem that can't be broken down into sub-problems that are independent of one another or dependent on some global state, then you are stuck with doing one long big computation and lose the benefits of MapReduce.

StackExchange Computer Science Q#24783, answer score: 5