Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

Dividing a problem to smaller ones until the individual problems can be solved independently and then combining them to answer the original question is known as the divide and conquer algorithm design technique. [See: Introduction to Algorithms by CLR]

Recently, this approach to solve computational problems especially in the domain of very large data sets has been referred to as MapReduce rather than divide and conquer.

My question is as follows: Is MapReduce anything more than a proprietary framework that relies on the divide and conquer approach, or are there details to it that make it unique in some respect?

share|improve this question

4 Answers 4

up vote 25 down vote accepted

If you're asking about the MapReduce architecture, then it is very much just a divide and conquer technique. However, any useful MapReduce architecture will have mountains of other infrastructure in place to efficiently "divide", "conquer", and finally "reduce" the problem set. With a large MapReduce deployment (1000's of compute nodes) these steps to partition the work, compute something, and then finally collect all results is non-trivial. Things like load balancing, dead node detection, saving interim state (for long running problems), are hard problems by themselves.

share|improve this answer
    
“to efficiently "divide", "conquer", and finally "reduce" the problem” – this is misleading: the “map” step doesn’t require a D&C solver (since the data is strictly independent), you can just distribute chunks of work using some kind of scheduler; the reduce step does require D&C. –  Konrad Rudolph Aug 5 '11 at 15:01
1  
The word "just" is misleading in this context. –  user1249 Aug 5 '11 at 18:10

MapReduce is not simply a divide and conquer technique, though it looks that way in many examples.

In the mapping step you can and frequently want to do a one-to-many relation. Thus you're not simply dividing into cases.

Between the map and reduce there is either (depending on implementation) a sort or a hashing step. The efficiency of this operation is extremely important for overall resource requirements. Its details are invisible to the application programmer, but this step is the heart of the framework.

The reduce operation is a type of merge. Which can be thought of as a conquer, but in practice tends to either be, "emit data for later usage" or "save data in a data store". (Note, if you have large data sets you really want everything to be distributed, including the input and final results. So a distributed key/value store makes sense both as a place to get the input and to store the output.)

share|improve this answer

MapReduce diverges from most divide and conquer systems in a fairly fundamental way, but one that's so simple that many people almost miss it. The real genius of it is in tagging the intermediate results.

In a typical (previous) divide and conquer system, you divide the work up serially, execute work packets in parallel, and then merge the results from that work serially again.

In MapReduce, you divide the work up serially, execute work packets in parallel, and tag the results to indicate which results go with which other results. The merging is then serial for all the results with the same tag, but can be executed in parallel for results that have different tags.

In more previous systems, the merge step became a bottleneck for all but the most truly trivial tasks. With MapReduce it can still be if the nature of the tasks requires that all merging be done serially. If, however, the task allows some degree of parallel merging of results, then MapReduce gives a simple way to take advantage of that possibility. Most other systems do one of two things: either execute all the merging serially just because it might be necessary for some tasks, or else statically define the parallel merging for a particular task. MapReduce gives you enough data at the merging step to automatically schedule as much in parallel as possible, while still ensuring (assuming you haven't made mistakes in the mapping step) that coherency is maintained.

Also note that in MapReduce, it's implicit that all of the steps can be recursive, so I might have an initial mapping step that breaks a big task up into 5 smaller tasks that can be executed in parallel -- but each of those might (in turn) get mapped out to a number of other smaller parallel tasks, and so on.

This leads to a tree structure on both the mapping and the reducing sides to quickly break a large task down into enough pieces to take advantage of many machines.

share|improve this answer

MapReduce is a framework for implementing divide-and-conquer algorithms in an extremely scalable way, by automatically distributing units-of-work to nodes in an arbitrarily large cluster of computers and automatically handling failures of individual nodes by redistributing the unit-of-work to another node.

It's not a super-sophisticated concept, but a very useful piece of infrastructure.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.