First,  the meaning of  n  is to be explained. Then, seemingly the result to be proved is a kind of limit theorem. Thus: which parameters tend to infinity,  M,  N  or  n?

Regards.

Please let me know if this reference/site is helpful to you:

http://cs-www.cs.yale.edu/homes/aspnes/papers/join-split.pdf

Dennis

Dennis Mazur

@Joachim Domsta, @Dennis Mazur

Hello, Prof. Thanks for replying.

My question is like:-

One throws m=n balls into n bins independently and uniformly at random, the maximum load (number of balls in any bin) is Φ(ln n/(ln*ln n)) with probability tending to 1 as n->∞.

Now instead of placing each ball in a single random bin, we choose d random bins for each ball, place it in the one that currently has fewest balls, and proceed in this manner sequentially for each ball. Clearly if d = n the maximum load will be optimal: ceil(m/n). But this requires global knowledge of the state of all bins. Today we will show that with d = 2 choices, the maximum load is a.a.s. at most ((ln*ln n)/ln 2) + Φ(1).

That is, having only one more choice than the basic model reduces the maximum load exponentially. 

@Dennis Mazur

Hello, Prof. the reference that you have suggested is not in my problem domain.