Topics in Database Systems: Data Management in Peer-to-Peer Systems Spring Semester 2005 ---------------------------------------------------------------------- ASSIGNMENT 3: CAN and CHORD review questions Due: March 22, 2005 Goups of up to 3 students 1. CAN uses two methods for topology-aware routing: (a) topologically-sensitive construction of the CAN overlay and (b) RTT-based routing. Can any of these methods be applied to CHORD? If not, why not? If yes, how? 2. In section 2.3 of the CAN paper, it is stated that: "If the zone of one of the neighbors can be merged with the departing node's zone to produce a valid single zone, then this done." Give a condition (or an algorithm) for testing when this can happen. 3. List the different replication strategies for metadata (key, value) items proposed in the CAN and CHORD papers. 4. Compare zone overloading in CAN with virtual nodes in CHORD. Do they serve the same purpose? 5. Assume a CAN with d dimensions, h hash functions and r realities. What is the average number of paths between any two points? 6. What is the minimum requirement for routing in CHORD to work? 7. Does the addition of virtual nodes in CHORD increase the path length? Does it increase the number of control messages (routing messges) a node receives from other nodes?