Distributed Load Balancing on Unrelated Machines
2026-07-11 • Data Structures and Algorithms
Data Structures and Algorithms
AI summaryⓘ
The authors study how to balance a set of tasks across different machines in a network where each task can take different amounts of time on each machine. They provide a new algorithm that works in a limited communication setting (called the CONGEST model) and handles the general case where task sizes differ per machine, improving on previous work that only handled tasks of equal size. Their method finds solutions that are nearly optimal in a small number of communication rounds. A key part of their work is a new tool to efficiently solve mixed packing and covering linear programs within this model, advancing the capabilities beyond earlier results that only worked for simpler types of problems.
Distributed algorithmsCONGEST modelLoad balancingUnrelated machinesMixed packing-covering linear programsApproximation algorithmsPolylog roundsCommunication complexityFractional vs integral solutionsDistributed optimization
Authors
Aaron Bernstein, Anupam Gupta, Zhaozi Wang
Abstract
We study the well-known load balancing problem in the distributed CONGEST model of computation. We consider the unrelated machines setting, where each job $j$ specifies a size $s_{ij}$ for every machine $i$. We want to find an assignment $\varphi: J \to M$ minimizing the maximum machine load, where the load of a machine $i$ is the total size of the jobs assigned to it. In the CONGEST model, the state-of-the-art is an algorithm that runs in polylog rounds and returns a $(1+\varepsilon)$-approximate fractional solution from Ahmadian, Liu, Peng, and Zadimoghaddam (2021). However, this algorithm, as well as all previous CONGEST algorithms only solve a special case of load balancing, where each job has the same size on each machine. Our main contribution is an algorithm for general sizes $s_{ij}$. The algorithm computes a $(1+\varepsilon)$-approximate fractional solution or a $(2+\varepsilon)$-approximate integral solution in polylog rounds. The problem structure changes significantly once we allow arbitrary edge-sizes, so our techniques are very different from those used in previous algorithms for distributed load balancing. One ingredient of our result is a black-box tool of independent interest: a $(1+\varepsilon)$-approximation algorithm to arbitrary mixed packing-covering linear programs in the CONGEST model in polylog rounds. such algorithms were known in the more powerful parallel model, but previous polylog-round algorithms in the distributed CONGEST model only solved pure packing or pure covering problems. We improve upon a recent $O(D\,\mathrm{polylog})$-round CONGEST algorithm for mixed packing-covering, where $D$ is the diameter of the communication graph.