So the map worker saves map results to its local disk, and eventually a reduce worker does an RPC call to copy that data over the network so it can perform the reduce. What is the advantage of doing this over having the map worker do the reduce part itself?
Concurrency (single CPU context switching) is "easy". Parallel programming (multiple tasks on multiple CPUs) is _hard_. I'm currently studying the internals of parallel programming, I am amazed by how much magic MapReduce abstracts away.
I have found the best resource for map reduce algorithms to be "Data-Intensive Text Processing with MapReduce" by Chris Dyer and Jimmy Lin - a short and very useful book that characterizes map reduce problems and their solutions.
The article says that Fibonacci can't be parallelized. But I seem to recall that there is a true data-parallel way of doing Fibonacci - one of those virtuoso tricks where something that seems intrinsically sequential gets transformed into a parallel computation. Does anyone know what I'm talking about?<p>Edit: to be clear, I don't mean the obvious but useless trick where you can compute F(n-1) and F(n-2) recursively in parallel, which is just redoing most of the work. I mean a way to model the problem as operations on data-parallel vectors.
Cool, I actually attended a talk about MapReduce hosted by Google a few weeks ago. Sadly, I have to say that this page explains it better than their engineer did, though.