CAN (ACIRI), Chord (MIT) and Tapestry/OceanStore (Berkeley) are decentralized (P2P) mechanisms designed to locate named objects (objects are uniquely identifiable through names = globally unique IDs). All systems have the same objectives:

• scalability with the number of objects 
• scalability with the number of nodes, where a node can host multiple objects
• support for dynamic environment: object are inserted and removed, nodes join and leave (self-organization)
• reliability

All systems have the same approach for lookup: index the search space for efficient lookup. In all cases the object names and nodes' labels are from the same namespace. In all cases, namespaces are totally ordered. The difference is in how they model the search space (which, I think, reduces to how they choose each node's neighbors):

• in CAN: as a coordinate space: queries are forwarded to the neighbor that's the closest to the destination.
• in Chord: as a ring (modulo 2^m). Nodes are "positioned" on this ring and have pointers towards other nodes. A request is forwarded to the neighbor whose ID is the smalest larger than the request.
• in Tapestry (initially Plaxton, in fact): as a mesh -- a set of overlapped search-optimized trees.

Measure	CAN	Chord	Tapestry	Plaxton mesh
Assumptions	- uses consistent hashing	- uses consistent hashing - unspecified namespace size. - names are hashed into m-bit identifiers. - nodes are (uniquely) labeled as m-bit identifiers. - names are stored on the corresponding nodes  - N is the number of nodes in system (N<2m) - implicit total ordering of the nodes (keys).	- N-sized namespace with IDs of base b	- Static network - N-sized namespace with IDs of base b - total ordering on all the nodes in the network
Search space modeled as	- multi-level coordinate space	- ring	- (Plaxton) mesh	- mesh
Look-up time	(d/4) * n1/d	O(log N)	O(logb N)	O(logb N)
Number of entries in routing table	2d (almost? constant)	O(log N)	b (not independent of N!)	b
Size of routing table	?	O(log N) ... = m * log N	b*logb N	b*logb N
Maintenance of routing table	- periodic refresh messages to (a constant number of) neighbors	- action only when changes occur
Node joins: cost	lookup time +  O(d) for updating routing tables	O(log2 N)		O(log N)
Node leaves: cost	lookup time +  O(d) for updating routing tables	O(log2 N)		O(log N)
Insert/Remove data	lookup time	- find the node with key K where data (k, value)  resides. O(log N)	- periodic refreshments messages/lack of ~
Fault handling	- neighbors detected missing heartbeats - constant number of neighbors have to update their routing tables - reliability ensured through replicas in different coordinate spaces (called realities).	- detect unresponsive neighbor during lookup operation. Replace it with its successor.	- detect missing heartbeats
Comments	Elegance from using its own lookup mechanism for every supported operation: insert/remove data, insert/remove node. Very meticulous presentation of design details, like simultaneous failure of multiple neighbors, load balancing, design improvements. Also, apparently very careful and complete performance results. (256K nodes!!! How? Simulations? Analytically?)	Elegance from using its own lookup mechanism for every supported operation: insert/remove data, insert/remove node	- very much based on Plaxton (not much originality)