2020/02/18 by Sanders, Peter
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2002.07553
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 w, data volume m, and maximum object sizes m. We then show matching upper and lower bounds for executing a MapReduce calculation on the distributed-memory machine -- Θ(w/p+w+log p) work and Θ(m/p+m+log p) bottleneck communication volume using p processors.