tag:blogger.com,1999:blog-6555947.post9004914080728463597..comments2024-03-14T01:32:43.610-06:00Comments on The Geomblog: Models for MapReduceSuresh Venkatasubramanianhttp://www.blogger.com/profile/15898357513326041822noreply@blogger.comBlogger12125tag:blogger.com,1999:blog-6555947.post-18075096168091337332011-11-02T11:07:08.589-06:002011-11-02T11:07:08.589-06:00As an example, take two PRAM primitives: list rank...<i>As an example, take two PRAM primitives: list ranking and prefix sums. Computing prefix sums in MR is easy you can do it in O(1) rounds. But list ranking seems to require \log n rounds, or does it? we have no proof...</i><br /><br />I think this is a good example of what I was asking for. In other words, MapReduce can motivate the question, but the model doesn't necessarily have to be about it explicitly.Suresh Venkatasubramanianhttps://www.blogger.com/profile/15898357513326041822noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-56803341236596684082011-11-02T09:47:52.425-06:002011-11-02T09:47:52.425-06:00Hi,
Jumping in a bit late here. A few comments:
G...Hi,<br />Jumping in a bit late here. A few comments:<br /><br /><i>Given the size of the data sets over which we run map-reduce algorithms, O(n^{2-epsilon}), if anything, looks overly generous. I made this point during Suri's presentation of the MRC framework in SODA. My take is that this was bringing unnecessary complication to allow for a case that would never happen. I would have capped the amount of resources at O( n polylog(n) )</i><br /><br />While I don't disagree that n^{2-\eps} is a bit generous, I think a further restriction is a case of premature optimization. Really this came out of three requirements:<br /><br />(1) Restrict the input on a per machine basis to be sublinear. <br />(2) Restrict the amount of parallelism to be sublinear as well. <br />(3) Allow for repetition of the data (i.e. don't insist on a partition). <br /><br />Now we did take a stance that sublinear should be substantial, i.e. beyond just shaving off a log, but I don't think this is where the complaint is coming from. <br /><br />To the broader point of <i>what is the limiting resource</i>:<br /><br />Maybe it's the amount of parallelism? On the one hand, you are forced to be parallel, just like in streaming you are forced to be sublinear in the input. On the other hand, you don't want to be overly parallel. That brings in additional coordination, communication, etc. So let's find algorithms that can exploit the middle ground. <br /><br />Phrasing it slightly differently: If I force you to parallelize, what is the range of parameters where you can remain work efficient?<br /><br />PRAMs give us many algorithms that are work efficient if you have O(\log n) rounds. But what if I insist on fewer? <br /><br />Here things appear to diverge. As an example, take two PRAM primitives: list ranking and prefix sums. Computing prefix sums in MR is easy you can do it in O(1) rounds. But list ranking seems to require \log n rounds, or does it? we have no proof...Sergeinoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-22520040590158145342011-11-01T23:57:50.902-06:002011-11-01T23:57:50.902-06:00@Yaroslav oops :)@Yaroslav oops :)Suresh Venkatasubramanianhttps://www.blogger.com/profile/15898357513326041822noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-45169581745680164532011-11-01T23:50:59.916-06:002011-11-01T23:50:59.916-06:00I see....PS top result for IANACT" gives &quo...I see....PS top result for IANACT" gives "I am not a cow tipper"Yaroslav Bulatovhttps://www.blogger.com/profile/06139256691290554110noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-31216691185514279542011-11-01T13:12:04.410-06:002011-11-01T13:12:04.410-06:00Again, IANACT, but there are many factors going in...Again, IANACT, but there are many factors going into designing a model, and an important one is identifying what the critical resource is. Practical considerations make the model predictions valuable of course, but often it's good to ignore it and let the "magic of mathematics" do its thing.Suresh Venkatasubramanianhttps://www.blogger.com/profile/15898357513326041822noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-938721646045190652011-11-01T12:59:10.098-06:002011-11-01T12:59:10.098-06:00@Suresh: isn't practical applicability how you...@Suresh: isn't practical applicability how you choose between different models of efficiency? Or is idea to pick the notion of efficiency which is the most interested from mathematical point of view?<br /><br />"Every machine talks to every machine equally fast" is the goal of a "fabric" interconnected cluster. There are probably physics reasons that make this technically false, but that's how it seems in practice. I've seen some work on optics based fabric -- essentially every computer in cluster can communicate with laser to any other computer directly through laser beam, this should further mitigate inter-cluster network congestionYaroslav Bulatovhttps://www.blogger.com/profile/06139256691290554110noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-38683113455369551162011-11-01T12:02:35.300-06:002011-11-01T12:02:35.300-06:00I've yet to hear a similar argument for MRC .
...<i>I've yet to hear a similar argument for MRC </i>.<br /><br />The subject of study is the processing of data collections larger than RAM on a single machine but small enough to fit in main memory across a distributed cluster or in NS. <br /><br />Data sizes smaller than that and we are in the realm of the RAM and I/O models, larger than that and we are talking data streams. This means we are talking about a range of interest of o(n^2) space/time not unlike the o(n) space assumption for data streams and the question becomes what can we compute in this model?<br /><br />Having said that, I do agree with the deeper message that good models should not be overly specific.<br /><br />I'm surprised you didn't take issue with the other overly specific restriction of some map-reduce frameworksa and models which is imposing orderly, discrete <key,value> passes on the data. <br /><br />People have already pushed Map-Reduce beyond that to more general computations both in theory and in practice.Alex Lopez-Ortiznoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-85099406214790268522011-11-01T10:51:52.370-06:002011-11-01T10:51:52.370-06:00@Yaroslav, my colleagues who work on petascale mac...@Yaroslav, my colleagues who work on petascale machines usually reject the claim that any machine can talk to any other machine equally fast. <br /><br />Having said that, I do think that if we had to focus on a single bottleneck, communication is the one we should focus on. I also think that theoreticians shouldn't get too distracted by the complaints of 'efficiency' levelled by practitioners, since the needs of a model involve theoretical structures as well.Suresh Venkatasubramanianhttps://www.blogger.com/profile/15898357513326041822noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-43353019044243026542011-11-01T10:47:17.264-06:002011-11-01T10:47:17.264-06:00@Alex, but my point is that such restrictions, whe...@Alex, but my point is that such restrictions, whether they be n^2 or n polylog, are judgements about efficiency that should not be introduced into the model unless they create large jumps in complexity or fundamentally address modelling issues. With streaming, the whole point of the model is to limit the ability to store the data, so o(n) memory makes sense. I've yet to hear a similar argument for MRC (I'm not saying there isn't one though)Suresh Venkatasubramanianhttps://www.blogger.com/profile/15898357513326041822noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-15816923643148786402011-11-01T08:52:12.244-06:002011-11-01T08:52:12.244-06:00There is a tradeoff between generality and simplic...There is a tradeoff between generality and simplicity of a mdel. For example you could make the same arguments against the standard Turing Machine model: why restrict ourselves to one tape instead of several?<br /><br />The answer is: for our purposes the one tape model as introduced by Turing is good enough. Of course to periodically revisit the choice of the model and see if still captures the behavior of the objects under study. <br /><br />Given the size of the data sets over which we run map-reduce algorithms, O(n^{2-epsilon}), if anything, looks overly generous. I made this point during Suri's presentation of the MRC framework in SODA. My take is that this was bringing unnecessary complication to allow for a case that would never happen. I would have capped the amount of resources at O( n polylog(n) ).Alex Lopez-Ortiznoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-2836801076353592972011-11-01T02:13:25.000-06:002011-11-01T02:13:25.000-06:00How about fixing memory/cpu requirement per machin...How about fixing memory/cpu requirement per machine, and modeling the number of machines required as a function of input size...is there a model that does this? Hard-disk storage is being gradually phased out in favor of SSDs nowadays, and that behaves a lot like RAM. Also, in a fabric-interconnected cluster, every machine can talk to every machine equally fast, so this could simplify modeling network resources.Yaroslav Bulatovhttps://www.blogger.com/profile/06139256691290554110noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-5362946364701880062011-10-31T15:27:25.238-06:002011-10-31T15:27:25.238-06:00I could not agree with you more. I think the curre...I could not agree with you more. I think the current models fail at abstracting out what is fundamentally "going on" with MapReduce. A good model should not only reflect the object being studied but should also give insight into the nature of that object.Asterixnoreply@blogger.com