Complexity measures for map-reduce, and comparison to parallel computing. Manuscript http: // www. stanford. edu/ ~ ashishg/ papers/ mapreducecomplexity. pdf

The programming paradigm Map-Reduce [3] and its main open-source implementation, Hadoop [1], have had an enormous impact on large scale data processing. Our goal in this expository writeup is two-fold: first, we want to present some complexity measures that allow us to talk about Map-Reduce algorithms formally, and second, we want to point out why this model is actually different from other models of parallel programming, most notably the PRAM (Parallel Random Access Memory) model. We are looking for complexity measures that are detailed enough to make fine-grained distinction between different algorithms, but which also abstract away many of the implementation details. 1 An overview of Map-Reduce Map-Reduce is commonly used to refer to both a programming model for Bulk Synchronous Parallel Pro-cessing [7], as well as a computational infrastructure for implementing this programming model. From the infrastructure point of view, a Map-Reduce job has three phases: While many good descriptions of Map-Reduce exist [3, 5], we still would like to present a description since one of the phases (shuffle) is typically given less attention, and this phase is going to be crucial in our complexity measures and in the distinction that we draw with PRAM. Map: In this phase, a User Defined Function (UDF), also called Map, is executed on each record in a give