Performance Bounds for Priority-Based Stochastic Coflow Scheduling
Olivier Brun, Balakrishna Prabhu · IEEE Transactions on Parallel and Distributed Systems · 2026
We consider the coflow scheduling problem in the non-clairvoyant setting assuming flow sizes are random variables that follow some probability distribution. The goal is to minimize the weighted average completion time of coflows in expectation. We first obtain inequalities for this problem that are valid for all non-anticipative order-based rate-allocation policies and define a polyhedral relaxation of the performance space of such scheduling policies. This relaxation is used to analyze the performance of a simple priority policy in which the priority order is computed by Sincronia from expected flow sizes instead of their unknown actual values. We establish an upper bound on the approximation ratio of this priority policy with respect to the optimal priority policy for arbitrary probability distributions of flow sizes (with finite first and second moments). Tighter upper bounds are obtained for some specific distributions. Extensive numerical results suggest that performance of the proposed policy is much better than the upper bound.