2026-07-22T19:10:15Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13618 2024-03-06T10:52:27Z ddc:004 open_access

Distributed Load Balancing: A New Framework and Improved Guarantees Ahmadian, Sara Liu, Allen Peng, Binghui Zadimoghaddam, Morteza Load balancing Distributed algorithms Inspired by applications on search engines and web servers, we consider a load balancing problem with a general convex objective function. In this problem, we are given a bipartite graph on a set of sources S and a set of workers W and the goal is to distribute the load from each source among its neighboring workers such that the total load of workers are as balanced as possible. We present a new distributed algorithm that works with any symmetric non-decreasing convex function for evaluating the balancedness of the workers' load. Our algorithm computes a nearly optimal allocation of loads in O(log n log² d/ε³) rounds where n is the number of nodes, d is the maximum degree, and ε is the desired precision. If the objective is to minimize the maximum load, we modify the algorithm to obtain a nearly optimal solution in O(log n log d/ε²) rounds. This improves a line of algorithms that require a polynomial number of rounds in n and d and appear to encounter a fundamental barrier that prevents them from obtaining poly-logarithmic runtime [Berenbrink et al., 2005; Berenbrink et al., 2009; Subramanian and Scherson, 1994; Rabani et al., 1998]. In our paper, we introduce a novel primal-dual approach with multiplicative weight updates that allows us to circumvent this barrier. Our algorithm is inspired by [Agrawal et al., 2018] and other distributed algorithms for optimizing linear objectives but introduces several new twists to deal with general convex objectives. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sara Ahmadian and Allen Liu and Binghui Peng and Morteza Zadimoghaddam 2021 Is Part Of LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2021.79 urn:nbn:de:0030-drops-136186 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.79 eng https://creativecommons.org/licenses/by/3.0/legalcode