Yes that's sometimes an option, but very often the reduce isn't associative.

Ah, so that's the reason. Do you ever have the problem that the reduce computation, for a given key, is too big for one reduce worker and itself needs to be parallelized? Or does this boil down to the same thing as my previous question - i.e. if the reduce computation isn't associative, you couldn't parallelize it anyway, and if it is then you can just do partial reductions on M.

Yes that is often a problem and is probably my biggest criticism of mapreduce as a framework. Extreme reduce keys often have to be handled differently and in a way dependent on the nature of the problem. Mapreduce doesn't provide great tools for handling it, though I'm not even sure what abstraction you could build that would be comprehensive enough.