Timeline for What is the novelty in MapReduce?

Current License: CC BY-SA 3.0

17 events
when toggle format what by license comment
Aug 13, 2012 at 20:29 comment added Mike Samuel @ex0du5, Fair enough. I thought ""Map/reduce does not break new ground in theory of computation." True." was clear enough but I've rewritten the list of contributions.
Aug 13, 2012 at 20:27 history edited Mike Samuel CC BY-SA 3.0
clarified claims in response comments
Aug 13, 2012 at 20:06 comment added ex0du5 @MikeSamuel: I don't think I'm condemning it at all. I was writing against this answer, not the paper. This answer specifically states: "It does show that particular simpler operations are practical for a particular class of problem." and then gives 4 "contributions" that the paper makes. None of this was novel, and this was not the first (or even the best) paper stating these facts. The question asked by Raphael was specifically on whether there was novelty in the MapReduce, so backing claims of positive contribution looks to me like this gives the wrong answer.
Aug 11, 2012 at 16:17 comment added Mike Samuel @ex0du5, I think you may be condemning it for claims it doesn't make. "Many systems have provided restricted programming models and used the restrictions to parallelize the computation automatically. ... MapReduce can be considered a simplification and distillation of some of these models based on our experience with large real-world computations. ... In contrast, most of the parallel processing systems have only been implemented on smaller scales and leave the details of handling machine failures to the programmer." It cites papers by Rabin and Valiant on that, but not the Liskov paper.
Aug 11, 2012 at 16:02 comment added ex0du5 @MikeSamuel: well, the 1979 paper I linked had search as it's example. Star graph search was one of the common algorithms looked at in studying pi calculus and similar parallel models of computing. I don't think there was anything novel, even describing the operations or bandwidths. Its just frustrating seeing the work of many ignored for what was basically a fluff piece.
Aug 11, 2012 at 14:55 comment added Mike Samuel @ex0du5, would you disagree with my answer less if the contributions only included 3 and 4 - specific implementation choices and optimizations; and benchmarks of large text search indices.
Aug 10, 2012 at 20:46 comment added ex0du5 No one in the community ever thought map reduce was in any way a contribution. It's like many modern software patents, an obvious already widely used and talked about idea that was given some marketing money and a new name. It's sad to see anyone pretending there was a contribution here. There are thousands of IEEE and ACM articles that disagree.
Aug 10, 2012 at 20:43 comment added ex0du5 I actually think this answer is pretty horrible and had to downvote. I'm not even sure why anyone would upvote. The paper's listed contributions are actually nothing that wasn't already well known (and published) under other names. In fact SETI@Home began in 1999 long before the given paper, a well-known example of the exact same architecture that was wide spread in distributed programming. Heck, look at dl.acm.org/citation.cfm?id=806567 an article from 1979 on primitives of DP and look at the example algorithm given in the back. It's map/reduce airline reservation... (cont)
Aug 10, 2012 at 18:36 vote accept Raphael
Aug 10, 2012 at 15:13 history edited Mike Samuel CC BY-SA 3.0
added 78 characters in body
Aug 5, 2012 at 11:24 comment added Raphael Huh, true. I interpreted "A worker node may do this again in turn, leading to a multi-level tree structure." this way, but that does of course not imply that the same happens on every level.
Aug 4, 2012 at 20:54 comment added Mike Samuel @Raphael, I don't think M/R is divide & conquer in the sense you link to. It does not involve the repeated application of an algorithm to a smaller subset of the original input. It's a pipeline where pipeline stages are alternating map and reduce operations.
Aug 4, 2012 at 8:58 comment added Raphael Well, they call the original paper "seminal" so I expect something new. I don't get your first paragraph: clearly there are plenty of algorithmic techniques that are not divide & conquer. If MapReduce is "only" an efficient implementation of d&c for a specific problem set, it's certainly nothing seminal or patent-worthy in algorithmics (imho). That does not say it's not a good system. Note that my critique is less with MapReduce itself (I guess it's good for what it's made for) than with its reception by the community.
Aug 3, 2012 at 16:24 history edited Mike Samuel CC BY-SA 3.0
added 79 characters in body
Aug 3, 2012 at 15:53 history edited Mike Samuel CC BY-SA 3.0
added 14 characters in body
Aug 3, 2012 at 15:41 history edited Mike Samuel CC BY-SA 3.0
added 471 characters in body
Aug 3, 2012 at 15:14 history answered Mike Samuel CC BY-SA 3.0