Anzeige
Erschienen in:
2015 | OriginalPaper | Buchkapitel
On the Computational Complexity of MapReduce
verfasst von : Benjamin Fish, Jeremy Kun, Ádám D. Lelkes, Lev Reyzin, György Turán
Erschienen in: Distributed Computing
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
In this paper we study the MapReduce Class (MRC) defined by Karloff et al., which is a formal complexity-theoretic model of MapReduce. 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.