Mathematics for Computer Science

18.7. Sums of Random Variables 639

and otherwiseTiis the length of the task. SoT D

Pn
iD 1 Tiis the total length of
tasks assigned to the first server, wherenD24;000.
The Chernoff bound is applicable only if theTiare mutually independent and
take on values in the rangeŒ0;1ç. The first condition is satisfied if we assume that
task lengths and assignments are independent. And the second condition is satisfied
because processing even the most interminable harangue takes at most 1 second.
In all, there are 24,000 tasks, each with an expected length of 1/4 second. Since
tasks are assigned to computers at random, the expected load on the first server is:

ExŒTçD

24;000tasks
1=4second per task

mmachines

D6000=mseconds: (18.24)

For example, if there are fewer than 10 machines, then the expected load on the
first server is greater than its capacity, and we can expect it to be overloded. If there
are exactly 10 machines, then the server is expected to run for6000=10D 600
seconds, which is 100% of its capacity.
Now we can use the Chernoff bound to upper bound the probability that the first
server is overloaded. We have from (18.24)

600 DcExŒTç wherecWWDm=10;

so by the Chernoff bound

PrŒT 600çDPrŒT cExŒTççe.cln.c/cC1/
6000=m;

The probability thatsomeserver is overloaded is at mostmtimes the probability
that the first server is overloaded, by the Union Bound in Section 16.4.2. So

PrŒsome server is overloadedç

Xm

iD 1

PrŒserveriis overloadedç

DmPrŒthe first server is overloadedç

me.cln.c/cC1/
6000=m;

wherecDm=10. Some values of this upper bound are tabulated below:

m D 11 W 0:784:::

m D 12 W 0:000999:::

m D 13 W 0:0000000760:::

These values suggest that a system withmD 11 machines might suffer immediate
overload,mD 12 machines could fail in a few days, butmD 13 should be fine for
a century or two!