Balanced Allocations with the Choice of Noise
Balanced Allocations with the Choice of Noise
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 randomly chosen bins, compare their two loads and then place a ball in the least loaded bin. It is well-known that for any …