Asymptotic analysis of the power of choice phenomenon for queuing models
Suppose that n balls are to be sequentially placed into n bins with the objective of keeping the maximum load of the bins small. In absence of a central dispatcher, and in order to minimize the communication overhead, each incoming ball chooses d bins uniformly at random and goes into the bin with the smallest load among its d choices. The maximum bin load for d = 2 (or greater) is substantially smaller than that for d=1 : O(log log n) vs O(log n); this phenomenon is called the power of choice. The phenomenon is quite robust and has applications to large scale load balancing, hashing, collision protocols, etc. We will consider queuing models with load balancing undertaken using the above heuristic with the number of choices d \to \infty. Our aim is to develop mathematical techniques for both fluid limits and functional central limit theorems in various regimes of the model.