Probability Seminar: Miheer Dewaskar, UNC-Chapel Hill

Miheer Dewaskar
University of North Carolina at Chapel Hill

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 the absence of a central dispatcher, and in order to minimize 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 hashing, collision protocols and a host of other applications including large scale load balancing. 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.

Refreshments will be served at 3:45 in the 3rd floor lounge of Hanes Hall