2021/04/11 by Anders Aamand, Aamand, Anders, Jakob Bæk Tejs Knudsen +3 · 1 citation
Computer Science · #Algorithms and Data Compression #Caching and Content Delivery #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Peer-to-Peer Network Technologies
paper · pdf · doi:10.48550/arxiv.2104.05093
openalex publication_date 2021/04/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 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 balancing parameter c=1+ε, where ε∈ (0,1). With n and m the current numbers of balls and bins, we want no bin with load above C=\lceil c n/m\rceil, referred to as the capacity of the bins. We present a scheme where we can locate a ball checking 1+O(log 1/ε) 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/ε. These bounds are best possible when C=O(1) but for larger C, we can do much better: Let f=εC if C≤ log 1/ε, f=ε√(C)⋅ √(log(1/(ε√(C)))) if log 1/ε≤ C