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.