Abstract
Conference Title: IEEE INFOCOM 2018 - IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS) Conference Start Date: 2018, April 15 Conference End Date: 2018, April 19 Conference Location: Honolulu, HI, USA Co-flows model a modern scheduling setting that is commonly found in a variety of applications in distributed and cloud computing. A stochastic co-flow task contains a set of parallel flows with randomly distributed sizes. Further, many applications require non-preemptive scheduling of co-flow tasks. This paper gives an approximation algorithm for stochastic non-preemptive co-flow scheduling. The proposed approach uses a time-indexed linear relaxation, and uses its solution to come up with a feasible schedule. This algorithm is shown to achieve a competitive ratio of (2 log +1)(1 + √Δ)(1+√Δ)(3 + Δ)/2 for zero-release times, and (2 log +1)(1 + √Δ)(1+√Δ)(2 + Δ) for general release times, where A represents the upper bound of squared coefficient of variation of processing times, and m is the number of servers.