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

Grad Student Seminar: Miheer Dewaskar

October 25, 2019 @ 3:30 pm - 4:30 pm

Miheer Dewaskar

UNC-Chapel Hill


Asymptotic analysis of the power of choice phenomenon

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. In this talk we will analyze the mean behavior of the balls and bins problem described above, and use concentration inequalities to show that, with high probability, the maximum load is (log log n)/log d +/- 1 when d > 1.

Share This Event

  • This event has passed.


October 25, 2019
3:30 pm - 4:30 pm
Event Category:


120 Hanes Hall
Hanes Hall
Chapel Hill, NC 27599 United States