Online makespan minimization in MapReduce-like systems with unsplit map tasks

This paper studies an online over-list model of the makespan minimization in MapReduce-like systems with unsplit map tasks. In this paper, we assume that each job has k map tasks. We study two cases: the first is that each job has only one reduce task which cannot be divided; the second is that each job has one reduce task which can be divided into a series of reduce task parts based on its input. For the first case, we propose a \left(2-\frac{1}{h}\right)-competitive algorithm, and prove the algorithm is optimal, where h is the number of machines. For the second case, we prove that any algorithm has a competitive ratio at least 2- \frac{1}{\beta h}, where \beta is the minimax ratio between the processing time of those reduce task parts from reduce task R_J which are assigned in machine i and the processing time of the reduce task R_J for arbitrary i and j, \beta\leq \frac{\lceil\frac{k}{2}\rceil}{k-1}. We then present an optimal algorithm.