Abstract
The MapReduce 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 NPHard 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 LPbased algorithm provides strong performance guarantees. Our second algorithm exploits a surprisingly simple mapping to the special case of one machine per cluster. This mappingbased algorithm is combinatorial and extremely fast. These are the first constant factor approximations for this problem.
BibTeX  Entry
@InProceedings{murray_et_al:LIPIcs:2016:6410,
author = {Riley Murray and Megan Chao and Samir Khuller},
title = {{Scheduling Distributed Clusters of Parallel Machines: PrimalDual and LPbased Approximation Algorithms}},
booktitle = {24th Annual European Symposium on Algorithms (ESA 2016)},
pages = {68:168:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770156},
ISSN = {18688969},
year = {2016},
volume = {57},
editor = {Piotr Sankowski and Christos Zaroliagis},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6410},
URN = {urn:nbn:de:0030drops64104},
doi = {10.4230/LIPIcs.ESA.2016.68},
annote = {Keywords: approximation algorithms, distributed computing, machine scheduling, LP relaxations, primaldual algorithms}
}
Keywords: 

approximation algorithms, distributed computing, machine scheduling, LP relaxations, primaldual algorithms 
Seminar: 

24th Annual European Symposium on Algorithms (ESA 2016) 
Issue Date: 

2016 
Date of publication: 

18.08.2016 