Optimal online algorithms for MapReduce scheduling on two uniform machines

Yiwei Jiang, Ping Zhou, T. C.E. Cheng, Min Ji

Research output: Journal article publicationJournal articleAcademic researchpeer-review

4 Citations (Scopus)

Abstract

We study online scheduling on two uniform machines in the MapReduce system. Each job consists of two sets of tasks, namely the map tasks and reduce tasks. A job’s reduce tasks can only be processed after all its map tasks are finished. The map tasks are fractional, i.e., they can be arbitrarily split and processed on different machines in parallel. Our goal is to find a schedule that minimizes the makespan. We consider two variants of the problem, namely the cases involving preemptive reduce tasks and non-preemptive reduce tasks. We provide lower bounds for both variants. For preemptive reduce tasks, we present an optimal online algorithm with a competitive ratio of s2+2s+5+1-s2, where s≥ 1 is the ratio between the speeds of the two machines. For non-preemptive reduce tasks, we show that the LS-like algorithm is optimal and its competitive ratio is 2s+1s+1 if s<1+52 and s+1s if s≥1+52.

Original languageEnglish
Pages (from-to)1663-1676
Number of pages14
JournalOptimization Letters
Volume13
Issue number7
DOIs
Publication statusPublished - 1 Oct 2019

Keywords

  • Big data
  • Competitive ratio
  • MapReduce scheduling
  • Online algorithm

ASJC Scopus subject areas

  • Control and Optimization

Cite this