Online makespan minimization in MapReduce-like systems with complex reduce tasks

详细信息    查看全文

• 作者：Taibo Luo ; Yuqing Zhu ; Weili Wu ; Yinfeng Xu ; Ding-Zhu Du
• 关键词：MapReduce ; Big data ; On ; line scheduling
• 刊名：Optimization Letters
• 出版年：2017
• 出版时间：February 2017
• 年：2017
• 卷：11
• 期：2
• 页码：271-277
• 全文大小：
• 刊物类别：Mathematics and Statistics
• 刊物主题：Optimization; Operation Research/Decision Theory; Computational Intelligence; Numerical and Computational Physics, Simulation;
• 出版者：Springer Berlin Heidelberg
• ISSN：1862-4480
• 卷排序：11

文摘

In the MapReduce processing, since map tasks output key-value pairs, and reduce tasks take the pairs output by the map tasks and compute the final results. Therefore, reduce tasks are unknown until their map tasks are finished. Also, we assume that map tasks are preemptive and parallelizable, but reduce tasks are non-parallelizable. With these assumptions, we study the scheduling of minimizing makespan. Both preemptive and non-preemptive reduce tasks are considered. We prove that no matter if preemption is allowed or not, any algorithm has a competitive ratio at least \(2-\frac{1}{h}\), we then give two optimal algorithms for these two versions.