I have been reading about MapReduce for a while -- but what I can't understand is how someone would make a decision to use (or not use) MapReduce.

I mean, what are the problem patterns that signal that MapReduce could be used.

It's basically problems that are huge, but not hard. Travelling salesman depends crucially on the distance between any given pair of cities, so while it can be broken down into many parts, the partial results cannot be recombined so that the globally optimal solution emerges (well, probably not; if you know a way, please apply for your Fields medal now). 

On the other hand, counting frequencies of words in a gigantic corpus is trivially partitionable, and trivially recombinable (you just add up the vectors computed for the segments of the corpus), so map-reduce is the obvious solution.

In practice, more problems tend to be easily recombinable than not, so the decision whether to parallelize a task or not has more to do with how huge the task is, and less with how hard it is.
