Date Added: Mar 2012
Distributed Hash Tables (DHTs) share storage and routing responsibility among all nodes in a peer-to-peer network. These networks have bounded path length unlike unstructured networks. Unfortunately, nodes can deny access to keys or misroute lookups. The authors address both of these problems through replica placement. They characterize binary tree-based routing DHTs and define MAXDISJOINT, a replica placement that creates route diversity for these DHTs. They prove that this placement creates disjoint routes and find the replication degree necessary to produce a desired number of disjoint routes. Using simulations of Pastry (a binary tree-based routing DHT), they evaluate the impact of MAXDISJOINT on routing robustness compared to other placements when nodes are compromised at random or in a contiguous run.