Balanced Allocations with Heterogeneous Bins: The Power of Memory
Dimitrios Los, Thomas Sauerwald, John Sylvester · Society for Industrial and Applied Mathematics eBooks · 2023
We consider the allocation of m balls (jobs) into n bins (servers). In the standard TWO-CHOICE process, at each step t = 1, 2,…, m we first sample two bins uniformly at random and place a ball in the least loaded bin. It is well-known that for any m n, this results in a gap (difference between the maximum and average load) of log2 log n + θ(1) (with high probability). In this work, we consider the MEMORY process [27] where instead of two choices, we only sample one bin per step but we have access to a cache which can store the location of one bin. Mitzenmacher, Prabhakar and Shah [23] showed that in the lightly loaded case (m = n), the MEMORY process achieves a gap of