Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published October 2013 | Accepted Version
Journal Article Open

Joint Optimization of Overlapping Phases in MapReduce


MapReduce is a scalable parallel computing framework for big data processing. It exhibits multiple processing phases, and thus an efficient job scheduling mechanism is crucial for ensuring efficient resource utilization. There are a variety of scheduling challenges within the MapReduce architecture, and this paper studies the challenges that result from the overlapping of the "map" and "shuffle" phases. We propose a new, general model for this scheduling problem, and validate this model using cluster experiments. Further, we prove that scheduling to minimize average response time in this model is strongly NP-hard in the offline case and that no online algorithm can be constant-competitive. However, we provide two online algorithms that match the performance of the offline optimal when given a slightly faster service rate (i.e., in the resource augmentation framework). Finally, we validate the algorithms using a workload trace from a Google cluster and show that the algorithms are near optimal in practical settings.

Additional Information

© 2013 Elsevier B.V. Available online 28 August 2013.

Attached Files

Accepted Version - performance-mapreduce.pdf


Files (820.0 kB)
Name Size Download all
820.0 kB Preview Download

Additional details

August 19, 2023
October 24, 2023