Skip to main content
Browse by:

Until further notice, in-person public events have been canceled. Event listings include how to access online content.
Please check before coming to campus.

Asymptotic analysis of the power of choice phenomenon for queuing models

Icon calendar
Thursday, January 30, 2020
Icon time
4:15 pm - 5:15 pm
Icon speaker
Minheer Dewaskar (UNC, Statistics and Operations Research)
Icon series
Probability Seminar

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.