Editing Open Problems:26
Warning: You are not logged in. Your IP address will be publicly visible if you make any edits. If you log in or create an account, your edits will be attributed to your username, along with other benefits.
The edit can be undone.
Please check the comparison below to verify that this is what you want to do, and then save the changes below to finish undoing the edit.
| Latest revision | Your text | ||
| Line 1: | Line 1: | ||
| β | {{ | + | {{DISPLAYTITLE:Problem 26: Equivalence of Two MapReduce Models}} |
| β | | | + | {{Infobox |
| β | | | + | |label1 = Proposed by |
| + | |data1 = Paul Beame | ||
| + | |label2 = Source | ||
| + | |data2 = [[Workshops:Kanpur_2009|Kanpur 2009]] | ||
| + | |label3 = Short link | ||
| + | |data3 = http://sublinear.info/26 | ||
}} | }} | ||
The original MapReduce paper {{cite|DeanG-04}} gives two distributed models. First it only says that | The original MapReduce paper {{cite|DeanG-04}} gives two distributed models. First it only says that | ||
intermediate key/value pairs with the same key are combined and sent as batch jobs to workers. | intermediate key/value pairs with the same key are combined and sent as batch jobs to workers. | ||
Then in Section 4.2, it additionally guarantees that the batch jobs received by a single worker are sorted according to the corresponding key values. There are algorithms that rely on this additional feature of MapReduce. Are these two models equivalent? For decision problems in the complexity world, we know strong time-space trade-offs for sorting, but no similar lower bounds are known for distinctness. | Then in Section 4.2, it additionally guarantees that the batch jobs received by a single worker are sorted according to the corresponding key values. There are algorithms that rely on this additional feature of MapReduce. Are these two models equivalent? For decision problems in the complexity world, we know strong time-space trade-offs for sorting, but no similar lower bounds are known for distinctness. | ||
