תקציר
We study a very natural local protocol for a file transfer problem. Consider a scenario where several files, which may have varied sizes and get created over a period of time, are to be transferred between pairs of hosts in a distributed environment. Our protocol assumes that while executing the file transfers, an individual host does not use any global knowledge; and simply subdivides its I/O resources equally among all the active file transfers at that host at any point in time. This protocol is motivated by its simplicity of use and its applications to scheduling map-reduce workloads. Here we study the problem of deciding the start times of individual file transfers to optimize QoS metrics like average completion time or MakeSpan. To begin with, we show that these problems are NP-hard. We next argue that the ability of scheduling multiple concurrent file transfers at a host makes our protocol stronger than previously studied protocols that schedule a sequence of matchings, in which no two active file transfers share a host at any time. We then generalize the approach of Queyranne and Sviridenko (J. Algorithms 45:202-212, 2002) and Gandhi et al. (ACM Trans. Algorithms 4(1), 2008) that relates the MakeSpan and completion time objectives and present constant factor approximation algorithms.
שפה מקורית | אנגלית |
---|---|
עמודים (מ-עד) | 613-636 |
מספר עמודים | 24 |
כתב עת | Theory of Computing Systems |
כרך | 55 |
מספר גיליון | 3 |
מזהי עצם דיגיטלי (DOIs) | |
סטטוס פרסום | פורסם - אוק׳ 2014 |
פורסם באופן חיצוני | כן |
הערה ביבליוגרפית
Funding Information:M.T. Hajiaghayi is supported in part by NSF CAREER award 1053605 and Google Faculty Research Award. Part of this work was done while the authors were meeting at DIMACS. We would like to thank DIMACS for hospitality. G. Kortsarz is supported in part by NSF grant number 0829959.