2018/02/11 by Ruijiu Mao, Mao, Ruijiu, Vaneet Aggarwal +3
Computer Science · #Cloud Computing and Resource Management #Data Structures and Algorithms (cs.DS) #Distributed #Distributed and Parallel Computing Systems #FOS: Computer and information sciences #Interconnection Networks and Systems #Parallel #and Cluster Computing (cs.DC) #cs.DC #cs.DS
paper · pdf · doi:10.48550/arxiv.1802.03700
Some of the results have been fixed, mainly involving the CoV. The changes compared to the previous version are minor
openalex publication_date 2018/02/11 · arxiv created 2018/02/23 · arxiv updated 2018/02/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 (2logm+1)(1+√(m)Δ)(1+mΔ)(3+Δ)/2 for zero-release times, and (2logm+1)(1+√(m)Δ)(1+mΔ)(2+Δ) for general release times, where Δ represents the upper bound of squared coefficient of variation of processing times, and m is the number of servers.