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.