Distributed load balancing: a new framework and improved guarantees
summary
Distributed algorithm balances loads on a bipartite source–worker graph in the CONGEST model, producing a 1+ε approximation for general convex objectives by iteratively testing feasibility via proportional allocation (a multiplicative‑weights style subroutine) and then solving matching subproblems to enforce target capacities. The method yields polylogarithmic round bounds — roughly O((log N)(log^2 D)/ε^3) rounds for general convex costs and about O((log N)(log D)/ε^2) for the maximum‑load objective — and constructs certificates proving near‑optimality.
AI-written summary · about
chapters (13)
- 0:00Introduction
- 0:30Problem setup
- 1:17Objective
- 3:02Related work
- 4:45Results
- 5:32Previous algorithms
- 6:50Concrete example
- 9:43General convex objectives
- 11:36Proportional allocation
- 13:13Analysis
- 15:00Key observation
- 15:54Full algorithm
- 18:11Summary
related talks
19mLook Before, Before You Leap: Online Vector Load Balancing with Few Reassignments
29mFirst Order Methods for Distributed Network Optimization
25mAvoiding Overload in Distributed Systems
17mSolving Max-Min Fair Resource Allocations Quickly on Large Graphs
51mExploiting Similarity in Federated Learning
01h 20mAn Introduction to Distributed, Massively Parallel, and Local Computation Algorithms
30mConsensus-Based Distributed Online Prediction and Optimization
25mDistCache: Provable Load Balancing for Large-Scale Storage Systems with Distributed...