Question

I want solution is not written in cursive... It's too hard to recognize. Thanks.

Exercise 4.17: Suppose that we have n jobs to distribute among m processors. For simplicity, we assume that m divides n. A job takes 1 step with probability p and k > 1 steps with probability 1 - p. Use Chernoff bounds to determine upper and lower bounds (that hold with high probability) randomly assign exactly n/m jobs to each processor when all jobs will be completed if we on

Answer 1

Answer: Date: 4/6/2019 Let Xi be an indicator random variable such that Xi={1the i-th job takes k steps otherwise 0 and T be the completi on of all jobs. Define s=? i=1 to n{k-[Xi-1]+1 Xi-0]}-n+(k- 1)-? i=1 to nXi where [Xi-1] equals 1 if Xi-1 and 0 otherwise; similarly for [Xi-0]. Note that S is the time to complete all jobs using one machine. Therefore S/m T-S By applying Chemoff bound, you can find bounds for ? n to i-1Xi (and thus S) with high probability