Grad Student Seminar: Miheer Dewaskar

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.