Tapestry is an overlay infrastructure for fault-tolerant wide-area location and routing. It provides location-independent routing of messages directly to the closest copy of an object or service using only point-to-point links and without centralized resources. The routing and directory information within Tapestry is purely soft state and easily repaired. Tapestry is self-administering, fault-tolerant, and resilient under load. It is a fundamental component of the OceanStore system. Tapestry is designed to handle dynamic environments where data and services are mobile and replicated widely for availability, durability, and locality. It uses a combination of redundancy, statistical behavior, and self-organization to achieve fault tolerance and resilience. Tapestry employs randomness to achieve both load distribution and routing locality. It is based on the Plaxton distributed search technique, augmented with additional mechanisms to provide availability, scalability, and adaptation in the presence of failures and attacks. Tapestry's architecture includes a neighbor map that allows messages to locate objects and route to them across an arbitrarily-sized network. Each node maintains a backpointer list that points to nodes where it is referred to as a neighbor. The neighbor map is organized into routing levels, and each level contains entries that point to a set of nodes closest in network distance that matches the suffix for that level. Tapestry handles faults by using soft state to maintain cached content for graceful fault recovery, rather than providing reliability guarantees for hard state. It also uses surrogate routing to incrementally compute a unique root node for each object. This allows Tapestry to handle a wide array of failures from mundane to Byzantine, possibly by sending multiple messages along different paths to ensure a high-probability of delivery. Tapestry's dynamic algorithms allow nodes to integrate into the network dynamically. The algorithm for dynamic node insertion involves populating the neighbor map by routing to the new node ID and copying and optimizing neighbor maps along each hop from the router. The new node then informs the relevant nodes of its entry into the Tapestry, so that they may update their neighbor maps with it. Tapestry also supports mobile objects by explicitly republishing and deleting location pointers. This allows the system to maintain consistency of object location pointers even as objects move between servers. The system uses epoch numbers as a primitive versioning mechanism for location pointer updates. Tapestry's performance is evaluated through simulations that demonstrate the benefits of the design and how it performs under adverse conditions. The results show that Tapestry location servers show graceful degradation in both throughput and response time as ambient network traffic increases. Tapestry routing incurs a small overhead compared to IP routing.Tapestry is an overlay infrastructure for fault-tolerant wide-area location and routing. It provides location-independent routing of messages directly to the closest copy of an object or service using only point-to-point links and without centralized resources. The routing and directory information within Tapestry is purely soft state and easily repaired. Tapestry is self-administering, fault-tolerant, and resilient under load. It is a fundamental component of the OceanStore system. Tapestry is designed to handle dynamic environments where data and services are mobile and replicated widely for availability, durability, and locality. It uses a combination of redundancy, statistical behavior, and self-organization to achieve fault tolerance and resilience. Tapestry employs randomness to achieve both load distribution and routing locality. It is based on the Plaxton distributed search technique, augmented with additional mechanisms to provide availability, scalability, and adaptation in the presence of failures and attacks. Tapestry's architecture includes a neighbor map that allows messages to locate objects and route to them across an arbitrarily-sized network. Each node maintains a backpointer list that points to nodes where it is referred to as a neighbor. The neighbor map is organized into routing levels, and each level contains entries that point to a set of nodes closest in network distance that matches the suffix for that level. Tapestry handles faults by using soft state to maintain cached content for graceful fault recovery, rather than providing reliability guarantees for hard state. It also uses surrogate routing to incrementally compute a unique root node for each object. This allows Tapestry to handle a wide array of failures from mundane to Byzantine, possibly by sending multiple messages along different paths to ensure a high-probability of delivery. Tapestry's dynamic algorithms allow nodes to integrate into the network dynamically. The algorithm for dynamic node insertion involves populating the neighbor map by routing to the new node ID and copying and optimizing neighbor maps along each hop from the router. The new node then informs the relevant nodes of its entry into the Tapestry, so that they may update their neighbor maps with it. Tapestry also supports mobile objects by explicitly republishing and deleting location pointers. This allows the system to maintain consistency of object location pointers even as objects move between servers. The system uses epoch numbers as a primitive versioning mechanism for location pointer updates. Tapestry's performance is evaluated through simulations that demonstrate the benefits of the design and how it performs under adverse conditions. The results show that Tapestry location servers show graceful degradation in both throughput and response time as ambient network traffic increases. Tapestry routing incurs a small overhead compared to IP routing.