TY - GEN
T1 - Improved bounds for distributed load balancing
AU - Assadi, Sepehr
AU - Bernstein, Aaron
AU - Langley, Zachary
N1 - Publisher Copyright:
© Sepehr Assadi, Aaron Bernstein, and Zachary Langley; licensed under Creative Commons License CC-BY 34th International Symposium on Distributed Computing (DISC 2020).
PY - 2020/10/1
Y1 - 2020/10/1
N2 - In the load balancing problem, the input is an n-vertex bipartite graph G = (C ∪ S, E) - where the two sides of the bipartite graph are referred to as the clients and the servers - and a positive weight for each client c ∈ C. The algorithm must assign each client c ∈ C to an adjacent server s ∈ S. The load of a server is then the weighted sum of all the clients assigned to it. The goal is to compute an assignment that minimizes some function of the server loads, typically either the maximum server load (i.e., the '∞-norm) or the 'p-norm of the server loads. This problem has a variety of applications and has been widely studied under several different names, including: scheduling with restricted assignment, semi-matching, and distributed backup placement. We study load balancing in the distributed setting. There are two existing results in the CONGEST model. Czygrinow et al. [DISC 2012] showed a 2-approximation for unweighted clients with round-complexity O(∆5), where ∆ is the maximum degree of the input graph. Halldórsson et al. [SPAA 2015] showed an O(log n/log log n)-approximation for unweighted clients and O(log2n/log log n)approximation for weighted clients with round-complexity polylog(n). In this paper, we show the first distributed algorithms to compute an O(1)-approximation to the load balancing problem in polylog(n) rounds: In the CONGEST model, we give an O(1)-approximation algorithm in polylog(n) rounds for unweighted clients. For weighted clients, the approximation ratio is O(log n). In the less constrained LOCAL model, we give an O(1)-approximation algorithm for weighted clients in polylog(n) rounds. Our approach also has implications for the standard sequential setting in which we obtain the first O(1)-approximation for this problem that runs in near-linear time. A 2-approximation is already known, but it requires solving a linear program and is hence much slower. Finally, we note that all of our results simultaneously approximate all 'p-norms, including the '∞-norm.
AB - In the load balancing problem, the input is an n-vertex bipartite graph G = (C ∪ S, E) - where the two sides of the bipartite graph are referred to as the clients and the servers - and a positive weight for each client c ∈ C. The algorithm must assign each client c ∈ C to an adjacent server s ∈ S. The load of a server is then the weighted sum of all the clients assigned to it. The goal is to compute an assignment that minimizes some function of the server loads, typically either the maximum server load (i.e., the '∞-norm) or the 'p-norm of the server loads. This problem has a variety of applications and has been widely studied under several different names, including: scheduling with restricted assignment, semi-matching, and distributed backup placement. We study load balancing in the distributed setting. There are two existing results in the CONGEST model. Czygrinow et al. [DISC 2012] showed a 2-approximation for unweighted clients with round-complexity O(∆5), where ∆ is the maximum degree of the input graph. Halldórsson et al. [SPAA 2015] showed an O(log n/log log n)-approximation for unweighted clients and O(log2n/log log n)approximation for weighted clients with round-complexity polylog(n). In this paper, we show the first distributed algorithms to compute an O(1)-approximation to the load balancing problem in polylog(n) rounds: In the CONGEST model, we give an O(1)-approximation algorithm in polylog(n) rounds for unweighted clients. For weighted clients, the approximation ratio is O(log n). In the less constrained LOCAL model, we give an O(1)-approximation algorithm for weighted clients in polylog(n) rounds. Our approach also has implications for the standard sequential setting in which we obtain the first O(1)-approximation for this problem that runs in near-linear time. A 2-approximation is already known, but it requires solving a linear program and is hence much slower. Finally, we note that all of our results simultaneously approximate all 'p-norms, including the '∞-norm.
KW - Distributed algorithms
KW - Load balancing
KW - Matching
KW - Semi-Matching
UR - http://www.scopus.com/inward/record.url?scp=85109569656&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85109569656&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.DISC.2020.1
DO - 10.4230/LIPIcs.DISC.2020.1
M3 - Conference contribution
AN - SCOPUS:85109569656
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 34th International Symposium on Distributed Computing, DISC 2020
A2 - Attiya, Hagit
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 34th International Symposium on Distributed Computing, DISC 2020
Y2 - 12 October 2020 through 16 October 2020
ER -