Difference between revisions of "Open Problems:27"
m (1 revision) |
|||
| Line 1: | Line 1: | ||
| − | {{ | + | {{Header |
| − | + | |title=Modeling of Distributed Computation | |
| − | | | + | |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? | 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? | ||
Revision as of 05:22, 16 November 2012
| Suggested by | Paul Beame |
|---|---|
| Source | Kanpur 2009 |
| Short link | https://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. [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. [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?
