The prefix routing approach is adopted by both Pastry and Tapestry. Pastry is the message routing infrastructure deployed in several applications including PAST [Druschel and Rowstron 2001], an archival (immutable) file storage system implemented as a distributed hash table with the API and Squirrel, a peerto- peer web caching service described. Pastry has a straightforward but effective design that makes it a good first example for us to study in detail. Tapestry is the basis for the OceanStore storage system, which we describe in . It has a more complex architecture than Pastry because it aims to support a wider range of locality approaches.

 Pastry

 All the nodes and objects that can be accessed through Pastry are assigned 128-bit GUIDs. For nodes, these are computed by applying a secure hash function to the public key with which each node is provided. For objects such as files, the GUID is computed by applying a secure hash function to the object’s name or to some part of the object’s stored state. The resulting GUIDs have the usual properties of secure hash values – that is, they are randomly distributed in the range 0 to 2128–1. They provide no clues as to the value from which they were computed, and clashes between GUIDs for different nodes or objects are extremely unlikely. (If a clash occurs, Pastry detects it and takes remedial action.) In a network with N participating nodes, the Pastry routing algorithm will correctly route a message addressed to any GUID in O(log N) steps. If the GUID identifies a node that is currently active, the message is delivered to that node; otherwise, the message is delivered to the active node whose GUID is numerically closest to it. Active nodes take responsibility for processing requests addressed to all objects in their numerical neighbourhood. Routing steps involve the use of an underlying transport protocol (normally UDP) to transfer the message to a Pastry node that is ‘closer’ to its destination. But note that the closeness referred to here is in an entirely artificial space – the space of GUIDs. The real transport of a message across the Internet between two Pastry nodes may require a substantial number of IP hops.