Load Balancing Question:maximum number of balls in a bin? 2X}-丹 Something is not right... balls =100,bins =100 balls =2000,bins =100 40 lhn山a 20 小w.oww 0 60 80 100 20 40 60 80 100 balls =600,bins =100 balls =5000,bins =100 20 100 10 Aar tbb s0klLuhuu 0 20 40 60 80 100 20 40 80 100
Load Balancing Question: maximum number of balls in a bin? Something is not right…
Load Balancing Question:maximum number of balls in a bin? When m=Θ(n): the max load is with high probability. When m =(nlog n): the max load is ()with high probability. with high probability (w.h.p.): We say an event happens with high probability(in n) if it happens with probability at least 1-1/n
Load Balancing with high probability (w.h.p.): We say an event happens with high probability (in n) if it happens with probability at least 1-1/n. Question: maximum number of balls in a bin?
Load Balancing When m=©(m): the max load is O logn log log n with high probability 13x≥0s20x≥0≤结 i=1 So we needP(X;≥t)≤ x≥≤（四）（月）（四）() =() InIn n esl let t=3In(n)/Inln(n) for sufficiently large n 31n2 n In n (elnlnlnn-InInn) ==e3nn+oa0）≤e-2h=
Load Balancing let m=n let t = 3ln(n)/lnln(n) for sufficiently large n
Load Balancing When m (nlogn): the max load is(with high probability P3:X≥0∑PX≥≤月 i=1 So we need P(Xi≥t)≤之 x≥≤(）()s()'() -()》= let t 4m/n 41g(n) 1
Load Balancing let m=nlg(n) let t = 4m/n = 4lg(n)
Load Balancing "m balls are thrown into n bins uniformly and independently at random" “uniformly at random choose h:[m]→[n" Question:maximum number of balls in a bin(maxh()? When m=Θ(n): the max load is with high probability When m =(nlog n): the max load is (with high probability
Load Balancing Question: maximum number of balls in a bin (max{|h -1 (i)|})? “m balls are thrown into n bins uniformly and independently at random” “uniformly at random choose h: [m]→[n]