Scholarlink

<p>This study investigates machine covering problems on some uniform machines in the MapReduce system. The aim is to maximize the minimum machine completion time. Each job comprises both map tasks and reduce tasks. The map tasks of a job can be freely partitioned and scheduled to different machines for simultaneous processing, whereas reduce tasks can only proceed after all corresponding map tasks have been finished. The study involves both the preemptive and non-preemptive variants of the reduce tasks for the given problem. For the preemptive version of reduce tasks, we introduce optimal algorithms to scenarios involving two and three machines. For the non-preemptive version of reduce tasks, we design an approximation algorithm that guarantees a worse-case ratio of <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(\frac{2s+1}{s+1}\)</EquationSource> </InlineEquation> specifically for the two-machine case, where <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(s\ge 1\)</EquationSource> </InlineEquation> denotes the speed ratio between the two machines.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Machine covering problem in MapReduce systems with a small number of machines

  • 期刊论文

  • 发表日期：

    2026年2月2日

查看全文
  • Quanchang Zheng

摘要

This study investigates machine covering problems on some uniform machines in the MapReduce system. The aim is to maximize the minimum machine completion time. Each job comprises both map tasks and reduce tasks. The map tasks of a job can be freely partitioned and scheduled to different machines for simultaneous processing, whereas reduce tasks can only proceed after all corresponding map tasks have been finished. The study involves both the preemptive and non-preemptive variants of the reduce tasks for the given problem. For the preemptive version of reduce tasks, we introduce optimal algorithms to scenarios involving two and three machines. For the non-preemptive version of reduce tasks, we design an approximation algorithm that guarantees a worse-case ratio of \(\frac{2s+1}{s+1}\) specifically for the two-machine case, where \(s\ge 1\) denotes the speed ratio between the two machines.