Comparison of efficiency of object location in existing distributed (p2p) systems (n is the number of nodes): Insert/Delete Space Search Chord: O(log^2n) O(nlogn) O(logn) CAN: O(r) O(nr) O((r/4)n^(1/r)), where r is the number of dimensions used in a virtual space Pastry: O(log^2n) O(nlogn) O(logn) Tapestry: O(log^2n) O(nlogn) O(logn) Insert/Delete: Number of messages when a node joins or leaves the network. Space: How many neighbour nodes each node maintains in routing table. Search: Number of messages when an object lookup is performed 1. Chord -Chord constructs a distributed lookup service using a routing table of logarithmic size. -In Chord, nodes are arranged into a large virtual circle. -Each node of the circle maintains pointers to predecessor and successor nodes. Additionally, a logarithmic number of nodes are maintained which cross a greater distance within the circle. -Queries are forwarded to along until their reach their destination. -Given a key, Chord maps the key onto node -Consistent hashing (distributed hash table) 2. CAN -CAN places objects into a virtual space. -Each peer logically occupies a zone in a virtual space (n dimensional) -Content and queries (key and value pairs) are mapped into n dimensions using global hash funktions -Queries are routed along axes in this space until they reach their destination. -Consistent hashing (distributed hash table) 3. Tapestry -Location and routing architecture (Plaxton, Rajaraman and Richa) -Distributed data structure -Employs randomness to achieve both load distribution and routing locality 3. Gnutella -Bounded broadcast mechanism used for searching 4. FreeNet -Chaotic routing scheme where objects are published to a few nearest neighbors -Queries follow gradients generated by object pointers