This paper presents Pastry, a peer-to-peer routing substrate that routes to the numerically closes node in at most log₂(N) hops. As in Chord, the (128 bit) node ID space is viewed as a circle. However, nodes not only store pointers to their neighbors plus fingers to nodes located further in the ID space: here, each node maintains the pointers to nodes numerically close to itself (the leaf set), a routing table where it keeps track of the nodes whose ID share a prefix of a given length with its own ID, and finally a neighborhood set that contains the list of nodes close to the current node according to the proximity metric. Each node's routing table entries are chosen to be close to the current node, according to the proximity metric. A section of the paper briefly addresses tolerance to malicious faults and to network partitions. Basically, the authors state that randomness could be added to the choice of the next node at each routing step so that eventually bad nodes will be avoided. This scheme, however, seems to assume that few nodes in the network will behave incorrectly. Network partitions could be tolerated by using IP multicast to discover disconnected networks and eventually re-integrating them into the current overlay network.

This paper describes the GNUnet anonymity protocol (GAP), i.e. the routing protocol. GAP supports only two types of messages: requests (for a data block bennett04:gnunet-ecrs) and replies. The routing protocol is similar to mixes. Each node routes other nodes' packets (unless it is a request that can be answered by the node itself) and rewrites the source address of that packet. If a node also sends requests, an outside observer can only know that one of the messages sent by that node was actually initiated by that node. Therefore, the more packets a node routes, the more it can "hide" its own messages. Given that connections between every two node are ciphered and that nodes may delay for a random amount time messages that it routes, an outside observer cannot correlate the messages a node receives and the messages it sends. This actually requires that the node is at least connected with a node that is not under the adversary's control. Each node may tradeits own anonymity (not others') for improved overall routing efficiency by deciding not to rewrite the source address of every packet (Freenet does not provide this flexibility). As a consequence, routing may improve over time. Nodes that route replies may decide to store locally replies, hence improving data availability and (potentially) locality. Therefore, as data migrates and gets replicated, paths to a given piece of data change, making it harder to censor accesses to it. The main scalability problem of GAP is that each node must keep information about the origin of messages it routed on behalf of other nodes in order to be able to send them the reply. However, this problem is tempered by the fact that (i) under memory pressure and high network load, nodes have the option of not rewriting a message's source, and (ii) messages all have a time-to-live (TTL).

This paper deals with the algorithmic foundations of content-addressable networks and DHTs. Unlike in the CFS/Chord paper dabek01:cfs which considers a circle as the overlay network topology, Ratnasamy et al. generalize this design to a d-dimensional torus (for d=1, the torus is a circle). The torus forms a coordinate space that is dynamically partitioned among all nodes, where each node has 2.d neighbors. There exists a function that maps keys in the DHT to points in the space and each node is responsible for a "zone", i.e. a range of keys. Therefore, requests are routed towards the neighbor with coordinates closest to the destination. Each node entering the system randomly chooses a point within the coordinate space and sends a JOIN request to that point that is received by the occupant of the region where that point is. The occupant splits its zone into two and transfers the corresponding half of its key-value pairs to the new node; it then notifies its former neighbors about the topological change. Nodes periodically send update messages to their neighbors, containing their zone and neighbors; should one fail to do so for some time, it will be considered as unavailable and one of its neighbors will soon take over its zone. The authors then describe a number of improvements (mostly in terms of performance and fault-tolerance):

• increasing the number of dimensions of the coordinate space increases fault-tolerance (each node has more neighbors) and decreases the routing path length;
• using multiple coordinate spaces ("realities") reduces the path length and increases FT as well;
• round-trip time (RTT) weighted routing reduces the per-hop latency by accounting for inter-neighbor latency (nodes can use the latency information in addition to their distance to the destination to choose among neighbors);
• sharing a coordinate zone among several peers with redundancy improves fault-tolerance;
• using multiple hash functions which I consider as close to using multiple hash tables, i.e. probably not the most elegant way to improve FT and performance;
• using the latency information when building the network so that nodes physically close are closed in the coordinate space as well;
• choosing the most loaded zone when partitioning a zone when a new node joins;
• caching and replication.