Open Problems:27 - Revision history

Krzysztof Onak: updated header

2013-03-07T01:50:28Z

updated header

Krzysztof Onak at 05:22, 16 November 2012

2012-11-16T05:22:44Z

Krzysztof Onak: 1 revision

2012-11-08T05:33:51Z

1 revision

Krzysztof Onak: Created page with "{{DISPLAYTITLE:Problem 27: Modeling of Distributed Computation}} {{Infobox |label1 = Proposed by |data1 = Paul Beame |label2 = Source |data2 = [[Workshops:Kanpur_2009|Kanpur 2..."

2012-10-19T14:58:47Z

Created page with "{{DISPLAYTITLE:Problem 27: Modeling of Distributed Computation}} {{Infobox |label1 = Proposed by |data1 = Paul Beame |label2 = Source |data2 = [[Workshops:Kanpur_2009|Kanpur 2..."

New page

{{DISPLAYTITLE:Problem 27: Modeling of Distributed Computation}}
{{Infobox
|label1 = Proposed by
|data1 = Paul Beame
|label2 = Source
|data2 = [[Workshops:Kanpur_2009|Kanpur 2009]]
|label3 = Short link
|data3 = http://sublinear.info/27
}}
MapReduce has recently inspired two distributed models of computation in the theory community. One is the MUD model of Feldman et al. {{cite|FeldmanMSSS-10}}. In this model they assume that every worker has at most a polylogarithmic amount of space available, which in total gives at most $\tilde O(n)$ space, where $n$ is the input size (in the order of at least terabytes). The other model of computation, due to Karloff et al. {{cite|KarloffSV-10}}, assumes that each of $n^{1-\epsilon}$ workers has at most $n^{1-\epsilon}$ space, where $\epsilon$ is a fixed positive constant. This totals to $n^{2-2\epsilon}$ space in the entire system. Can one design an interesting and practical model that only uses $n^{1+o(1)}$ space/resources?

@@ Line 1: / Line 1: @@
 {{Header
 |source=kanpur09
 |who=Paul Beame
 }}
 MapReduce has recently inspired two distributed models of computation in the theory community. One is the MUD model of Feldman et al. {{cite|FeldmanMSSS-10}}. In this model they assume that every worker has at most a polylogarithmic amount of space available, which in total gives at most $\tilde O(n)$ space, where $n$ is the input size (in the order of at least terabytes). The other model of computation, due to Karloff et al. {{cite|KarloffSV-10}}, assumes that each of $n^{1-\epsilon}$ workers has at most $n^{1-\epsilon}$ space, where $\epsilon$ is a fixed positive constant. This totals to $n^{2-2\epsilon}$ space in the entire system. Can one design an interesting and practical model that only uses $n^{1+o(1)}$ space/resources?

← Older revision	Revision as of 05:33, 8 November 2012
(No difference)