Approximated Two Choices in Randomized Load Balancing

摘要

This paper studies the maximum load in the approximated d-choice balls-and-bins game where the current load of each bin is available only approximately. In the model of this game, we have r thresholds T_1, ... , T_r (0 < T_1 < · · · < T_r) for an integer r (≥ 1). For each ball, we select d bins and put the ball into the bin of the lowest range, i.e., the bin of load i such that T_k ≤ i ≤ T_(k+1)-1 and no other selected bin has height less than T_k. If there are two or more bins in the lowest range (i.e., their height is between T_k and T_(k+1) -1), then we assume that those bins cannot be distinguished and so one of them is selected uniformly at random. We then estimate the maximum load for n balls and n bins in this game.