Topics in Database Systems: Data Management in Peer-to-Peer Systems
      		   Fall Semester 2006
----------------------------------------------------------------------


			ASSIGNMENT 2
	       	      Due: Nov 2, 2006
                 (CAN, CHORD, BATON Basics)

CAN paper, Sections 1 and 2
CHORD paper, Sections 1, 3 and 4
BATON paper, Sections 1, 3 (except 3.3, 3.4 and 3.5) and 4 (except 4.5)

In groups of up to three.

1. What is the average complexity of node join, node leave and lookup 
for CHORD, CAN, and BATON. 
Under which assumptions does this hold?
Draw a plot for each of the above operations, where the x-axis is the 
number of nodes and the y-axis is the expected number of hops. 
Assume: number of nodes = 1000 up to 100.000 with a step of 10.000.  
For CAN, assume d = 2,3,4,5,6,10 dimensions.
Comment on the expected relative performance of the three overlays.

2. Similarly, what is the average space complexity (number of entries) 
per node for CHORD, CAN and BATON? 
Under which assumptions does this hold?
Show the content of the data structure (routing table) that is 
maintained at each node.
Again, draw a plot where the x-axis is the number of nodes and the 
y-axis is the expected space (storage) per node.
Assume: number of nodes = 1000 up to 100.000 with a step of 10.000.  
For CAN, assume d = 2,3,4,5,6,10 dimensions.
Comment on the expected relative space requirements of the three 
overlays.


3. 

a. How would a 1-dimensional CAN look like?

b. In Theorem 2 of the CHORD paper, how/where is the assumption that
node and keys are random used? If this not the case, does O(log N) hold?

c. In the BATON paper, where/how are Theorems 1 and 2 used?