Topics in Database Systems: Data Management in Peer-to-Peer Systems
 		Spring Semester 2005
----------------------------------------------------------------------


   			ASSIGNMENT 4 
	               Routing Indexes
	       	      Due: March 29, 2005
                   Groups of up to 3 students


1. Assume that a new connection between two nodes A and D
is created. Also, assume that the exponentially aggregated 
RIs (ERIs) of both A and D are known. How should D update 
its own ERI to take into account the new connection?

2. Assume that the "cycle detection and recovery" solution 
is used. What is the maximum number that a node can be visited 
during an update? Explain. Assume Hop-count RIs with horizon D.

3. 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 
(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.