19.6. Sums of Random Variables 811
19.6.5 Randomized Load Balancing
Now let’s return to Fussbook and its load balancing problem. Specifically, we need
to determine a number,m, of servers that makes it very unlikely that any server is
overloaded by being assigned more than 600 seconds of work in a given interval.
To begin, let’s find the probability that the first server is overloaded. LettingTbe
the number of seconds of work assigned to the first server, this means we want an
upper bound on PrŒT 600ç. LetTibe the number of seconds that the first server
spends on theith task: thenTiis zero if the task is assigned to another machine,
and otherwiseTiis the length of the task. SoT D
Pn
iD 1 Tiis the total number of
seconds of work 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
assignment of a post to a server is independent of the time required to process the
post. The second condition is satisfied because we know that no post takes more
than 1 second to process; this is why we chose to measure work in seconds.
In all, there are 24,000 tasks, each with an expected length of 1/4 second. Since
tasks are assigned to themservers at random, the expected load on the first server
is:
ExŒTçD
24;000tasks1=4second per task
mservers
D6000=mseconds: (19.25)So if there are fewer than 10 servers, then the expected load on the first server is
greater than its capacity, and we can expect it to be overloaded. If there are exactly
10 servers, then the server is expected to run for6000=10D 600 seconds, which is
100% of its capacity.
Now we can use the Chernoff bound based on the number of servers to bound
the probability that the first server is overloaded. We have from (19.25)
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