Topics in Database Systems: Data Management in Peer-to-Peer Systems
Fall Semester 2006
----------------------------------------------------------------------
ASSIGNMENT 6
Due: Dec 7, 2005
Reading Assignment
------------------
Read the replication part of the Lv et al paper.
Read up to sec 1.4 of the Demers et al paper.
Take a look at the Cohen's et al paper.
(If you have not read Crespo et al paper, you should now!)
1. Term Project
Look at http://www.cs.uoi.gr/~pitoura/courses/p2p05/term-project.html
for details regarding the structure of the 1-page report.
(team of up to 2 students)
2. The replication theory we studied assumes "random probes".
(i) Is this a realistic assumption for the case of (a) power-law
graphs, (b) random graphs, and (c) grids?
Explain.
(ii) For the graphs (if any) that you believe that are mot
modelled well with random probes, how do you expect proportional,
square-root and uniform replication to perform?
3. (routing indexes)
Assume a p2p system with a tree topology of h levels
(of height h) and fan-out F. Also, assume that the same
F is used to compute the ERI. Let the uniform distribution
be used for the location of documents. The authors claim
(Crespo et. al, sec 7.2, 3rd par) that "ERI uses nodes until
the exponentially decayed value of an index entry reaches a minimum".
Show for the topology above how this value behaves.
Explain.