  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.
