Load balancing with dynamic set of balls and bins
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Standard
Load balancing with dynamic set of balls and bins. / Aamand, Anders; Knudsen, Jakob Bæk Tejs; Thorup, Mikkel.
STOC 2021 - Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing. ed. / Samir Khuller; Virginia Vassilevska Williams. Association for Computing Machinery, Inc, 2021. p. 1262-1275 (Proceedings of the Annual ACM Symposium on Theory of Computing).Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - GEN
T1 - Load balancing with dynamic set of balls and bins
AU - Aamand, Anders
AU - Knudsen, Jakob Bæk Tejs
AU - Thorup, Mikkel
N1 - Publisher Copyright: © 2021 ACM.
PY - 2021
Y1 - 2021
N2 - In dynamic load balancing, we wish to distribute balls into bins in an environment where both balls and bins can be added and removed. We want to minimize the maximum load of any bin but we also want to minimize the number of balls and bins that are affected when adding or removing a ball or a bin. We want a hashing-style solution where we given the ID of a ball can find its bin efficiently. We are given a user-specified balancing parameter c=1+?, where ?e (0,1). Let n and m be the current number of balls and bins. Then we want no bin with load above C= c n/m, referred to as the capacity of the bins. We present a scheme where we can locate a ball checking 1+O(log1/?) bins in expectation. When inserting or deleting a ball, we expect to move O(1/?) balls, and when inserting or deleting a bin, we expect to move O(C/?) balls. Previous bounds were off by a factor 1/?. The above bounds are best possible when C=O(1) but for larger C, we can do much better: We define f=? C when C? log1/?, f=?C· ?log(1/(?C)) when log1/? C<1/2?2, and f=1 when C? 1/2?2. We show that we expect to move O(1/f) balls when inserting or deleting a ball, and O(C/f) balls when inserting or deleting a bin. Moreover, when C? log1/?, we can search a ball checking only O(1) bins in expectation. For the bounds with larger C, we first have to resolve a much simpler probabilistic problem. Place n balls in m bins of capacity C, one ball at the time. Each ball picks a uniformly random non-full bin. We show that in expectation and with high probability, the fraction of non-full bins is (f). Then the expected number of bins that a new ball would have to visit to find one that is not full is (1/f). As it turns out, this is also the complexity of an insertion in our more complicated scheme where both balls and bins can be added and removed.
AB - In dynamic load balancing, we wish to distribute balls into bins in an environment where both balls and bins can be added and removed. We want to minimize the maximum load of any bin but we also want to minimize the number of balls and bins that are affected when adding or removing a ball or a bin. We want a hashing-style solution where we given the ID of a ball can find its bin efficiently. We are given a user-specified balancing parameter c=1+?, where ?e (0,1). Let n and m be the current number of balls and bins. Then we want no bin with load above C= c n/m, referred to as the capacity of the bins. We present a scheme where we can locate a ball checking 1+O(log1/?) bins in expectation. When inserting or deleting a ball, we expect to move O(1/?) balls, and when inserting or deleting a bin, we expect to move O(C/?) balls. Previous bounds were off by a factor 1/?. The above bounds are best possible when C=O(1) but for larger C, we can do much better: We define f=? C when C? log1/?, f=?C· ?log(1/(?C)) when log1/? C<1/2?2, and f=1 when C? 1/2?2. We show that we expect to move O(1/f) balls when inserting or deleting a ball, and O(C/f) balls when inserting or deleting a bin. Moreover, when C? log1/?, we can search a ball checking only O(1) bins in expectation. For the bounds with larger C, we first have to resolve a much simpler probabilistic problem. Place n balls in m bins of capacity C, one ball at the time. Each ball picks a uniformly random non-full bin. We show that in expectation and with high probability, the fraction of non-full bins is (f). Then the expected number of bins that a new ball would have to visit to find one that is not full is (1/f). As it turns out, this is also the complexity of an insertion in our more complicated scheme where both balls and bins can be added and removed.
KW - balls in bins
KW - consistent hashing
KW - dynamic load balancing
UR - http://www.scopus.com/inward/record.url?scp=85108173386&partnerID=8YFLogxK
U2 - 10.1145/3406325.3451107
DO - 10.1145/3406325.3451107
M3 - Article in proceedings
AN - SCOPUS:85108173386
T3 - Proceedings of the Annual ACM Symposium on Theory of Computing
SP - 1262
EP - 1275
BT - STOC 2021 - Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing
A2 - Khuller, Samir
A2 - Williams, Virginia Vassilevska
PB - Association for Computing Machinery, Inc
T2 - 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021
Y2 - 21 June 2021 through 25 June 2021
ER -
ID: 299207050