Connecting MapReduce Computations to Realistic Machine Models

Abstract

We explain how the popular, highly abstract MapReduce model of parallel computation (MRC) can be rooted in reality by explaining how it can be simulated on realistic distributed-memory parallel machine models like BSP. We first refine the model (MRC${}^{+}$) to include parameters for total work $w$, bottleneck work $\hat{w}$, data volume $m$, and maximum object sizes $\hat{m}$. We then show matching upper and lower bounds for executing a MapReduce calculation on the distributed-memory machine -- $\Theta (w/p+\hat{w}+\log p)$ work and $\Theta (m/p+\hat{m}+\log p)$ bottleneck communication volume using $p$ processors.