318 Hanes Hall, CB #3260 Chapel Hill, NC 27599-3260
919-962-1329
Loading Events

Probability Seminar: Miheer Dewaskar, UNC-Chapel Hill

January 30, 2020 @ 4:15 pm - 5:15 pm

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

Share This Event

  • This event has passed.

Details

Date:
January 30, 2020
Time:
4:15 pm - 5:15 pm
Event Category:

Venue