Skip to main content
Browse by:
GROUP

Effective March 10, 2020, all Duke-sponsored events over 50 people have been cancelled, rescheduled, postponed or virtualized.
Please check with the event contact regarding event status. For more information, please see https://coronavirus.duke.edu/events

Asymptotic analysis of the power of choice phenomenon for queuing models

Probability
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.