Scheduling distributed clusters of parallel machines: Primal-dual and LP-based approximation algorithms

Riley Murray, Megan Chao, Samir Khuller

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

Abstract

The Map-Reduce computing framework rose to prominence with datasets of such size that dozens of machines on a single cluster were needed for individual jobs. As datasets approach the exabyte scale, a single job may need distributed processing not only on multiple machines, but on multiple clusters. We consider a scheduling problem to minimize weighted average completion time of n jobs on m distributed clusters of parallel machines. In keeping with the scale of the problems motivating this work, we assume that (1) each job is divided into m "subjobs" and (2) distinct subjobs of a given job may be processed concurrently. When each cluster is a single machine, this is the NP-Hard concurrent open shop problem. A clear limitation of such a model is that a serial processing assumption sidesteps the issue of how different tasks of a given subjob might be processed in parallel. Our algorithms explicitly model clusters as pools of resources and effectively overcome this issue. Under a variety of parameter settings, we develop two constant factor approximation algorithms for this problem. The first algorithm uses an LP relaxation tailored to this problem from prior work. This LP-based algorithm provides strong performance guarantees. Our second algorithm exploits a surprisingly simple mapping to the special case of one machine per cluster. This mapping-based algorithm is combinatorial and extremely fast. These are the first constant factor approximations for this problem.

Original languageEnglish (US)
Title of host publication24th Annual European Symposium on Algorithms, ESA 2016
EditorsChristos Zaroliagis, Piotr Sankowski
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959770156
DOIs
StatePublished - Aug 1 2016
Event24th Annual European Symposium on Algorithms, ESA 2016 - Aarhus, Denmark
Duration: Aug 22 2016Aug 24 2016

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume57
ISSN (Print)1868-8969

Conference

Conference24th Annual European Symposium on Algorithms, ESA 2016
Country/TerritoryDenmark
CityAarhus
Period8/22/168/24/16

Keywords

  • Approximation algorithms
  • Distributed computing
  • LP relaxations
  • Machine scheduling
  • Primal-dual algorithms

ASJC Scopus subject areas

  • Software

Fingerprint

Dive into the research topics of 'Scheduling distributed clusters of parallel machines: Primal-dual and LP-based approximation algorithms'. Together they form a unique fingerprint.

Cite this