TY - GEN
T1 - Efficient load-balancing through distributed token dropping
AU - Brandt, Sebastian
AU - Keller, Barbara
AU - Rybicki, Joel
AU - Suomela, Jukka
AU - Uitto, Jara
N1 - Funding Information:
We thank Orr Fischer, Juho Hirvonen, and Tuomo Lempiäinen for valuable discussions. This project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No. 840605.
Publisher Copyright:
© 2021 ACM.
PY - 2021/7/6
Y1 - 2021/7/6
N2 - We introduce a new graph problem, the token dropping game, and we show how to solve it efficiently in a distributed setting. We use the token dropping game as a tool to design an efficient distributed algorithm for stable orientations and more generally for locally optimal semi-matchings. The prior work by Czygrinow et al. (DISC 2012) finds a stable orientation in O(^5) rounds in graphs of maximum degree , while we improve it to O(^4) and also prove a lower bound of ω(). For the more general problem of locally optimal semi-matchings, the prior upper bound is O(S^5) and our new algorithm runs in O(C · S^4) rounds, which is an improvement for C = o(S); here C and S are the maximum degrees of customers and servers, respectively.
AB - We introduce a new graph problem, the token dropping game, and we show how to solve it efficiently in a distributed setting. We use the token dropping game as a tool to design an efficient distributed algorithm for stable orientations and more generally for locally optimal semi-matchings. The prior work by Czygrinow et al. (DISC 2012) finds a stable orientation in O(^5) rounds in graphs of maximum degree , while we improve it to O(^4) and also prove a lower bound of ω(). For the more general problem of locally optimal semi-matchings, the prior upper bound is O(S^5) and our new algorithm runs in O(C · S^4) rounds, which is an improvement for C = o(S); here C and S are the maximum degrees of customers and servers, respectively.
KW - Distributed graph algorithms
KW - Load balancing
KW - Semi-matching
KW - Stable orientations
UR - http://www.scopus.com/inward/record.url?scp=85109563939&partnerID=8YFLogxK
U2 - 10.1145/3409964.3461785
DO - 10.1145/3409964.3461785
M3 - Conference article in proceedings
AN - SCOPUS:85109563939
T3 - Annual ACM Symposium on Parallelism in Algorithms and Architectures
SP - 129
EP - 139
BT - SPAA 2021 - Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures
PB - ACM
T2 - Annual ACM Symposium on Parallelism in Algorithms and Architectures
Y2 - 6 July 2021 through 8 July 2021
ER -