On the Computational Complexity of MapReduce

Benjamin Fish (1) , Jeremy Kun (1) , Ádám Lelkes (1) , Lev Reyzin (1) , György Turán (1, 2)

1 UIC - Department of Mathematics, Statistics and Computer Science [Chicago]
2 MTA-SZTE Research Group on Artificial Intelligence

In this paper we study the MapReduce Class (MRC) defined by Karloff et al., which is a formal complexity-theoretic model of MapRe-duce. We show that constant-round MRC computations can decide regular languages and simulate sublogarithmic space-bounded Turing machines. In addition, we prove hierarchy theorems for MRC under certain complexity-theoretic assumptions. These theorems show that sufficiently increasing the number of rounds or the amount of time per processor strictly increases the computational power of MRC. Our work lays the foundation for further analysis relating MapReduce to established complexity classes. Our results also hold for Valiant's BSP model of parallel computation and the MPC model of Beame et al.

Domains: Distributed, Parallel, and Cluster Computing [cs.DC]

Benjamin Fish, Jeremy Kun, Ádám Lelkes, Lev Reyzin, György Turán. On the Computational Complexity of MapReduce. DISC 2015, Toshimitsu Masuzawa; Koichi Wada, Oct 2015, Tokyo, Japan. ⟨10.1007/978-3-662-48653-5_1⟩. ⟨hal-01199793⟩