20.1.1
Given relation R is distributed evenly,
20.1.2
20.2.1
The map function takes an input document d, goes through the document
character by character, and each time it encounters another word w, it
20.2.2
a) The map function takes a tuple t and emits the pair (v, i), where v
is the value under c and i is the id of the tuple t. The intermediate
result is a list of pairs (v1, i1),(v2, i2),….
The reduce function takes the list of pairs, eliminates pairs whose vi
values do not satisfy c, and produces the selection.
b) The map function takes a tuple t and emits the pair (v, i), where v
c) The map function takes the product of R and S. It emits the pair (v,
i), where v is the value under c and i is the id of the tuple t. The
intermediate result is a list of pairs (v1, i1),(v2, i2),….
e) The map function takes R and S. It emits the pair (t, 1), which t is
the tuple of t, for each R and S. The intermediate results are two
20.3.1
Define U to be the sum over all sites i of 10dui. That is, U is the cost
of sending one second’s worth of updates to one site other than the
site at which the update originated.
Now, consider the value of creating a copy of R at site i. On the
positive side, the queries generated at site i that used to have to be
answered remotely, at a cost of 10cqi, can now be answered for cqi, a
positive benefit of 9cqi.
20.4.1
i) sR
ii) sS
iii) pS + (sR – dR)
20.4.2
a)
Let R={A,B}, S={B,C,D}, T={B,E,F}, U={F,G,H}, V={G,I}, and W={H,J}.
b)
After eliminating ears of {A,B}, {B,C,D}, and {G,I}, there is no more
ears. Thus there is no way of reducing the hypergraph into a single
hyperedge.
c)
20.4.3
a) in 20.4.2
S := S R
T := T S
U := U T
c) in 20.4.2
R := R S
20.4.4
The total number of full reducers of Fig. 20.9 is
3 x 2 x 2 = 12
The first candidates of ear reductions are R, S, and T since U is not
20.4.5
True. Eliminating a hyperedge doesn’t introduce a new cycle in a
20.4.6
b)intersection and c)difference operations can be improved by the
semijoin. One relation in a different site only needs the duplicate
20.5.1
a) There is a component A at the home computer, and components B and C
at each of the banks. Component B receives the directive from A. B
b) It’s possible that it turns out B doesn’t have more than $10,000
after it signals C to deposit $10,000. B aborts T but C commits it
since there is no problem in C.
c) It’s possible that B updates its account subtracting $10,000 and
signals C to deposit $10,000 but C is down or disconnected from the
network. C doesn’t get the signal, thus no transaction occurs at C.
20.5.2
a) (0,1,P), (0,2,P), (1,0,R), (2,0,D), (0,1,A), (0,2,A)
b) In the first phase, the coordinator exchanges the messages (0, 1, P),
(1, 0, R) with site 1 and the messages (0, 2, P), (2, 0, R) with site 2.
These messages may occur in any of 2 * (3 choose 2) = 6 (since (0, 1,
c) The number of possible sequences is the same as b). There are (2, 0,
D) instead of (2, 0, R) and (0, 1, A) and (0, 2, A) instead of (0, 1,
C) and (0, 2, C) in this case.
d) In the phase 1, the coordinator sends the messages (0, 1, P) and (0,
20.5.3
f(n) = (2n choose n) * n
20.6.1
a) Suppose that s, x, and i are the numbers of local shared, exclusive,
and increment locks that a transaction needs to have a global lock of
that type.
s + i > n
For example, we could require that any type of lock requires a majority.
b) Suppose that s, x, and u are the numbers of local shared, exclusive,
and update locks that a transaction needs to have a global lock of that
type.
c) Suppose that s, x, is and ix are the numbers of local shared,
exclusive, intention to shared lock and intention to exclusive locks
that a transaction needs to have a global lock of that type.
2x > n
20.6.2
a) The 90% of the accesses that are read-only require no messages,
since there is a lock table and a copy at each site. The remaining 10%
of the accesses require exclusive locks. Thus, each requires three
b) In primary-copy locking, only the primary-copy site require no
20.7.1
a) N32
20.7.2
a) N1
Distance
1
2
4
8
16
32
Node
b) N48
Distance
1
2
4
8
16
32
Node
c) N56
Distance
1
2
4
8
16
32
Node
N1
N1
N1
N1
N8
N32
56 + 1 = 57
20.7.3
a) N1 searches for a key that hashes to 27.
N1 –> N38 -> N1
c) N51 searches for a key that hashes to 45.
N51 –> N14 -> N48 -> N51
N51 finds that 45 is not in either the successor’s range or
<Finger table of N51>
Distance
1
2
4
8
16
32
Node
N56
N56
N56
N1
N8
N14
51 + 1 = 52
<Finger table of N14>
Distance
1
2
4
8
16
32
Node
N21
N21
N21
N32
N32
N48
14 + 1 = 15
20.7.4
a) 41
Change predecessor and successor links:
1. N41 sets its successor to N42 and its predecessor to nil. The
Stabilize:
2. The predecessor of N42 is changed to N41.
b) 62
Change predecessor and successor links:
1. N62 sets its successor to N1 and its predecessor to nil. The
predecessor of N1 remains N56 for the moment.
Stabilize:
2. The predecessor of N1 is changed to N62.
20.7.5
Let Ni, Nj, and Np be a new node to be inserted between Ni and Np. Nj and
Np to be the successor and the predecessor of Ni respectively.
1. Change predecessor and successor links including predecessor’s
2. Stabilize:
a. The predecessor of Nj is changed to Ni.
b. The predecessor’s predecessor of Nj’s successor is changed to Ni.
c. All key-value pairs whose keys hash to p+1 through i are recorded as