Online makespan minimization for MapReduce scheduling on multiple parallel machines

Abstract

In this work, we investigate the online MapReduce processing problem on mm uniform parallel machines, aiming at minimizing the makespan. Each job consists of two sets of tasks, namely, the map tasks and the reduce tasks. A job’s map tasks can be arbitrarily split and processed on different machines simultaneously, while its reduce tasks can only be processed after all its map tasks have been completed. We assume that the reduce tasks are preemptive, but cannot be processed on different machines in parallel. We provide a new lower bound for this problem and present an online algorithm with a competitive ratio of 2−1m2-\frac{1}{m} (mm is the number of machines) when the speeds of the machines are 1.

Keywords

• mapreduce scheduling
• online algorithm
• competitive ratio
• parallel machines
• lower bound
• 90b35
• 68m20