Papers for

distributed systems architects

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Constant factor approximation improves coflow scheduling in parallel networks

Constant-Factor Approximation for Non-Splitting Coflow Scheduling in Heterogeneous Parallel Networks via Iterative Relaxation

Abstract: Coflows capture the collective communication requirements of data-parallel applications, and scheduling them well is essential to the performance of modern data centers. We study non-splitting coflow scheduling in a heterogeneous parallel network whose $m$ network cores may be Electronic Packet Switches (EPS), not-all-stop Optical Circuit Switches (OCS), or all-stop OCS, where every flow must be transmitted entirely through a single core. Previous approximation algorithms for this setting have guarantees that grow linearly with the number of cores $m$ or with the maximum flow degree $τ$ of a port, and therefore become weak as data centers deploy more cores. The source of this dependence is the rounding step: rounding each flow to the core holding its largest fractional value can inflate the load of a port by a factor of $m$. We replace this step with an iterative relaxation rounding scheme that handles the input-port and output-port capacity constraints simultaneously. For minimizing the makespan, this yields approximation ratios of $\min\{τ, 3\}$, $2\min\{τ, 3\}$, and $4\min\{τ, 3\}$ for pure EPS, pure not-all-stop OCS, and pure all-stop OCS networks, respectively. For minimizing the total weighted coflow completion time, we obtain approximation ratios of $8\min\{τ, 4\}$, $16\min\{τ, 4\}$, and $32\min\{τ, 4\}$ for the same three architectures. In a hybrid network, the guarantee is governed by the weakest architecture present, so the overall ratios are at most $4\min\{τ,3\}\le 12$ and $32\min\{τ,4\}\le 128$, respectively. Unlike all previous guarantees for non-splitting coflow scheduling in heterogeneous parallel networks, these bounds are absolute constants that do not grow with the number of cores $m$ or with the flow degree $τ$. We also show that the integrality gap of the underlying linear program is at least $2$.

Thu 29 OctData Structures and Algorithms
The gist
Managing how data moves inside big data centers is tricky because many pieces of information need to be sent together as groups called coflows. The authors found a better way to schedule these groups across different network types without breaking them up, which helps keep data moving smoothly. Their method guarantees steady performance regardless of how many parts the network has, improving over old methods that got worse as networks grew. They use a new mathematical approach that handles network limits more effectively for different setups.
Open → 2610.39564v1