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

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?

Answer 1

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.

Answer 2

there are two different/separate concepts to keep in mind. computation related to Turing completeness is not about parallelism. a general purpose parallel computing system, of which Mapreduce is one, is Turing complete, and all Turing complete operations can run on a parallel system, but (as pointed out in the other answer) the speedup due to parallelism may not be possible.

Mapreduce in a single operation is actually designed for a narrow class of parallel problems known as embarrassingly parallel where no communication between processors is required. any problems that require communication between processors are not reducible to single Mapreduce operations although could generally be broken down into multiple Mapreduce operations with communications of results between processors (or centrally operated on) in intermediate steps.

the question about which problems can be efficiently computed in one architecture (eg Parallel) vs others are mostly open in complexity theory. about all that can be proven is that some problems can be "sped up" via parallelism but other basic questions such as "do there exist algorithms that cannot be parallelized (ie speedup due to parallelism)" cannot be answered definitively at the current state of knowledge.

Answer 3

By googling I found a list of example:

http://csci8980-2.blogspot.com/2012/10/limitations-of-mapreduce-where-not-to.html

I provide it as a reference, but I would still love to see the intuition (or proofs) on why these methods can't be expressed in MapReduce.

Answer 4

MapReduce is based on splitting a task and have it done by several machines. It is obvious that some tasks can not be spitted. The reason is that the result is kind of Holistic meaning that whole data should be considered at once. Two types of holistic problems are:
1) Intensive calculations:
First let see what is extensive property: suppose you want to square 2K numbers and then add them up. this is extensive operation since you can send every (per say) 200 numbers to every machine and have them do the operation for you and finally add the result coming from each machine. Another way to think about this is that you do the operation on given 2K numbers and another number is received, in this case you can simply square the number and add it to the previous result. Now think that you need to first sum all the numbers and then square the result.
Oops! you can not do this easily. As you can see you can simply extend the operation to new number. ( note that for this simple example one can use $c^2 = a^2 + b^2 + 2ab$ however this is not the case for all problems)
2)‌‌‌‌ Graphs:
most of the calculations on graphs require data from whole graph so those kinds of calculations can not be done using distributed systems.
How do we find out if a calculation can be done by distributed system or not?
If you remember distribution property in Algebra you have the answer. for the above example we have:
extensive scenario: $ a^2 + b^2 + c^2 = (a^2 + b^2) + c^2 = a^2 + (b^2 + c^2)$
Intensive Scenario: $(a+ b+ c)^2 != (a+b)^2 + c^2$