3/26/08 (due 4/2/08)
Read 6.1-6.3. Think about (but don't hand in) Problem 3 in Section
6.1 (same problem in DAM2) and Problems 18 and 20 in Section 6.3
(DAM2: Section 6.3, problems 17 and 20)
Section Number Points Comments
6.1 2 2 DAM2: same problem
6.2 5(b),(d),(e) 3 DAM2: same problem
9 3 DAM2: 6.2, 8
16 3 DAM2: 6.2, 12
21(b) 3 DAM2: 6.2, 19(b)
6.3 3 3 DAM2: 6.3, 3
7(b) 3 DAM2: 6.3, 9(b) (Think about the note,
but you don't have to answer the question there)
8 3 DAM2: 6.3, 10
11 3 DAM2: 6.3, 12
15 4 DAM2: 6.3, 15
17 4 DAM2: 6.3, 16
24(b),(c),(e) 6 DAM2: 6.3, 7(a),(b),(d)
36 4 DAM2: 6.3, 38
Extra problem (also due to Jon Kleinberg)
[5 points] Consider a distributed computer system with a set S of n
independent processors, labeled 1, 2, ..., n. At any given point in
time, some subset of these processors will be available to perform tasks.
We want to avoid a situation in which at some point in time, a subset A
of S is available to perform a certain task; and later, when we return
to continue the task, a subset B of S is available, where B is disjoint
from A (that is, where B and A have no elements in common).
The problem here is that, since no processor in B also belongs to A,
there is no processor with memory of what happened previously in
processing the task. We'd like a situation where each pair of
``available sets'' is guaranteed to have at least one processor in
common. Such a processor can serve as a ``bridge'' between consecutive
groups that perform a common task, to maintain consistency. In the study
of distributed systems, such a collection of available sets is sometimes
called a quorum system. Formally, we say that a quorum system of
order n is a collections of subsets of {1, 2, ..., n} with the
property that every pair of sets in the collection has at least one
element in common. Let q(n) denote be the maximum size of a quorum
system of order n. Give a formula for q(n) in terms of n, and prove it
is correct. (That is, for every n, show that if your formula specifies
q(n) = q0, then there exists a quorum system of order n with
q0 sets, and there is no quorum system of order n with q0 + 1 sets.)
[It turns out that there's a neat answer to this question and, once you
see it, proving it is easy. The hard part is seeing it. You can
also try to proving an upper bound on q(n) even if you can't show that
there exists a quorum system of size q(n). I'd be interested in any
nontrivial upper and lower bounds.]