恒速机上的MapReduce在线排序算法下界研究

摘要

本文研究源自于MapReduce模型系统的一类排序问题.给定两台恒速机和一批按列表到达的工件,每个工件包含两类任务:Map任务和Reduce任务.假设Map任务和Reduce任务都是不可中断的,Map任务可以并行处理,即可以任意分割成若干小的任务并在两台机器上同时处理,而Reduce任务只可以在单台机器上处理.一旦工件到达,必须为其指派机器和开工时间,目标是使得这批工件的最后完工时间最小.对|Mj|≥|Rj|的情形,我们证明了任意在线算法的竞争比不小于(1+1/2s+2).