Problem 3. A budget data center company offers a scalable dynamic load balancing

Question

Problem 3. A budget data center company offers a scalable dynamic load balancing system that supplies a new machine whenever a new job shows up, so that there are always n machines available to run n jobs. Unfortunately, one of the ways the company cuts cost is by not hiring programmers to replace the code from their previous randomized load balancing mechanism, so when the i-th job arrives, it is still assigned uniformly at random to one of the i available machines. This means that job 1 is always assigned to machine 1; job 2 is assigned with equal probability to machine 1 or 2; job 3 is assigned with equal probability to machine 1, 2, or 3; and so on. These choices are all independent If there are are n jobs, what is the expected load of the i-th machine? Hint Use an indicator random variable X,, for the event that machine i gets job j.] Solution. Problem 4 (Continued). The company claims that the maximum load is still not too bad. Justify this claim by showing that, with high probability, the most loaded machine after n jobs has arrived has load O(log n). Use the version of the Chernoff bound from Problem 2

Explanation / Answer

There are n machines 1, 2,3...n.

Expected load of ith machine = 1/i + 1/(i+1) +...+1/n

---------------------------------

Maximum load that can be taken by I machine = 1+1/2+..+1/n

Consider expansion of log (1-x) = -x-x^2/2-x^3/3-x^4/4.....-x^n/n

When x goes near 1, this becomes

-(1+1/2+1/3+...+1/n) = O(log n)

Job 1 Job 2 Job 3 … Job i … Jobn Expected load Machine 1 1    1/2 1/3 1/i 1/n 1+1/2+1/3+…+1/m 2 0    1/2 1/3 1/i 1/n (1/2+1/3+…+1/n 3 0    0    1/3 … 1/i … 1/n (1/3+1/4+…+1/n) … i 0    0    0    0    1/i 1/n (1/I+1/(I+1)+…+1/N … n 0    0    0    0    0    1/n 1/n

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.