rewrote
Xodarap
• 1.5k
• 10
• 16

Think ofI think you've hit the following:nail on the head with your comment.

count = 0
for i = 1 to n:
output[i] = do_something(input[i])
count++


Clearly, this is breakingIt's not true that in any functional language maps can be parallelized - the problem into smaller pieceslanguage must be pure. But it's a pain to distribute, because count(I believe Haskell is shared between all the loopsonly vaguely mainstream purely functional language. Lisp, OCaml and Scala are all non-pure.)

The map-reduce paradigm enforces certain constraints, among them thatWe've known about the functions must be idempotent (which is a fancy waybenefits of saying they can't have side effectspure code since even before timesharing, like usingwhen engineers first pipelined their processors. So how come no one uses a shared count variable)pure language?

It's really, really, really hard. It turns out that any code following these constraints will be to some degree distributableProgramming in a pure language often feels like programming with both hands tied behind your back.

So the advancement hereWhat MR does is notrelax the creation of map or fold functionspurity constraint somewhat, but rather the observation that certain types of maps and folds are easierprovide a framework for other pieces (like the shuffle phase) making it quite easy to distribute than others while still remaining useful inwrite distributable code for a varietylarge fraction of contextsproblems.

(As I think you probably know, there are debates about whether this was really "discovered" by Google or had been knownwere hoping for a whilean answer like "It proves this important sub-lemma of $$NC=P$$" and I don't think it does anything of the sort. Whoever inventedWhat it though, it's reasonable to saydoes do is show that it's a non-trivial observation that manyclass of problems can meet the M/R constraints, and henceknown to be distributable are easily"easily" distributable - whether that's a "revolution" in your opinion probably depends on how much time you've spent debugging distributed code in a pre-Map/Reduce world.)

Xodarap
• 1.5k
• 10
• 16

Think of the following:

count = 0
for i = 1 to n:
output[i] = do_something(input[i])
count++


Clearly, this is breaking the problem into smaller pieces. But it's a pain to distribute, because count is shared between all the loops.

The map-reduce paradigm enforces certain constraints, among them that the functions must be idempotent (which is a fancy way of saying they can't have side effects, like using a shared count variable). It turns out that any code following these constraints will be to some degree distributable.

So the advancement here is not the creation of map or fold functions, but rather the observation that certain types of maps and folds are easier to distribute than others while still remaining useful in a variety of contexts.

(As you probably know, there are debates about whether this was really "discovered" by Google or had been known for a while. Whoever invented it though, it's reasonable to say that it's a non-trivial observation that many problems can meet the M/R constraints, and hence are easily distributable.)