4/2/07 (due 4/9/07)
Read 6.4-6.6. Think about (but don't hand in):
- 6.4, 33 (DAM2: 6.4, 13)
- Supplementary Problems, Problems 10, 11 (DAM2: Supplementary problems 3, 4)
Section Number Points Comments
6.3 9(b),(d) 4 DAM2: 6.3, 11(b),(d)
6.4 7(b),(d),(f) 3 DAM2, 6.4, 17(b),(d),(f)
8(b) 3 DAM2: 6.4, 4(b); Explain your answer
25 4 DAM2, 6.4, 26
28(b) 3 DAM2, 6.4, 30(b)
38(b) 3 DAM2, 6.4, 40
40 4 DAM2, 6.4, 38
6.5 7 4 DAM2, 6.5, 6
18 3 DAM2, 6.5, 18
34 4 DAM2, 6.5, 34. Write this up carefully
Supp. 22(b),(d),(f) 6 DAM2, Supp. 13(b,)(d),(f)
More problems from Jon Kleinberg:
(1) [5 points] Suppose that we have n identical computing servers, and n
jobs that need to be performed. However, because we need to route the
jobs quickly, with limited knowledge of the global state of the system,
we simply assign each job independently and uniformly at random to one
of the servers. That is, the jobs arrive in sequence, and each is
assigned uniformly at random to one of the servers, independent of the
assignment of previous jobs. Determine the probability that each server
is assigned exactly one job, by giving a formula for this quantity in
terms of n. In particular, describe the underlying sample space, the
event in question, and its probability. (You do not need to write out
the entire sample space or the event; it is enough to give a precise
mathematical formulation of it.) Also, show that this probability
converges to 0 as n increases.
(2) [5 points] A biomedical lab runs a cluster of machines that measure
and analyze data, and due to the sensitivity of the data, they need to
back it up every night at a secure offsite location. They've set up the
following automated system for doing this, involving four computers:
a Data Aggregator, a Relay Server, a Firewall Server, and an Offsite
Backup. By 11:00 PM every night, the results from all the day's
experiments reside on the Data Aggregator as a single large data
file. At 11:00 PM the Data Aggregator opens a connection to the
Relay Server to send it this data. At 11:15 PM, the Relay Server opens a
connection to the Firewall Server, and sends the data to it. At 11:30
PM, the Data Aggregator connects to the Firewall Server and sends a
duplicate copy of the data. (This is designed to provide some extra
redundancy in the backup, just in case.) Finally, at 11:45 PM, the
Firewall Server connects to the Offsite Backup and sends the data to it
(either the original or backup copy, if it has both -- it doesn't matter
which). If successful, each of these individual transmissions
lasts at most 15 minutes (and so the final transmission is done by
midnight). Now, there's some probability that each of these connections
fails, in which case the data doesn't get transmitted across that
particular connection. Suppose that the connection from the Data
Aggregator to the Relay Server fails with probability .1, the connection
from the Relay Server to the Firewall Server fails with probability .1,
the connection from the Data Aggregator to the Firewall Server fails
with probability .05, and the connection from the Firewall Server to the
Offsite Backup fails with probability .02. Assume that the successes
of each of these network connections are mutually independent as events.
What is the probability that a copy of the data file containing the
day's results successfully ends up at the Offsite Backup at midnight?
Provide an explanation for your answer.