Difference between revisions of "Open Problems:27"

From Open Problems in Sublinear Algorithms
Jump to: navigation, search
(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...")
 
m (1 revision)
(No difference)

Revision as of 05:33, 8 November 2012

Proposed by Paul Beame
Source Kanpur 2009
Short link 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. [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?